Discussion :

[DeathMixer]

Bonjour a tous,

J'ai un projet en Algorithmique à programmer en C++ avec la bibliothèque NTL (http://www.shoup.net/ntl/) pour manipuler des grands nombres.

Je ne vais pas rentrer dans les détails de ce projet, puisqu'il est compliqué à expliquer clairement (il s'agit de cryptographie sur les Courbes Elliptiques pour ceux d'entre vous que ca intéresse)... Bref, mon problème ne se situe pas à ce niveau.
Mon plus grand problème (pour l'instant mon seul ) se situe au niveau de la programmation en C++.

Je me retrouve en effet à devoir gérer un ensemble ordonné d'éléments d'un corps fini (que je vois comme un vecteur de k éléments, qui sont des entiers modulo p)
que j'aimerai pouvoir classer uniquement par rapport à leur premier élément (qui est donc un entier de type ZZ dans NTL, qui sont tout simplement des entiers de taille arbitraire, pour lesquels il existe une relation d'ordre <)

J'ai tout naturellement pensé à std::set puisque je dois etre capable de :
- insérer un nouvel élément si il n'apparait pas déjà dans la liste
- déterminer si un élément appartient à cette liste

et tout ca en temps le plus rapide possible (idealement une complexite en O(log n), où n : taille de la liste

J' ai déjà une version naive qui crée un vecteur et augmente sa taille lorque l'élément à classer n'apparait pas dans ce vecteur.
Mais la recherche, encore plus naive, consiste a parcourir les éléments un par un, en partant du début pour voir si l'élément apparait ou pas.
Ce n'est clairement pas efficace pour des vecteur de taille > 512.
Or tout l'interet de la chose est d'etre capable de travailler avec de telle taille de vecteur ...




Voici la partie de mon code correspondante, mais je ne pense pas qu'elle sera d'une grande aide ...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
struct compareZpE     // fonction de comparaison des elements d un corps fini
{
	bool operator()(ZZ_pE a, ZZ_pE b)
	{
		return rep(coeff(rep(a), 0)) < rep(coeff(rep(b), 0));
	}
};
 
 
std::set<ZZ_pE, compareZpE> Add_Chain2( void )
{
	std::set<ZZ_pE, compareZpE> s1;
	ZZ_pE x, y, z, t;
 
// tirage d'éléments aléatoires (défini dans NTL.lib) d'un corps fini
	random(x); random(y); random(z); random(t);
 
 
	cout<<"x =  "<<x<<"\n";
	cout<<"y =  "<<y<<"\n";
	cout<<"z =  "<<z<<"\n";
	cout<<"t =  "<<t<<"\n";
	s1.insert(x); s1.insert(y); s1.insert(z);
	cout<<"est ce 't' appartient a l ensemble ?  "<<(s1.find(t) != 0);
 
	return s1;
}

J'espère que les quelques considérations mathématiques que j'ai mentionnées plus haut, ne découragerons pas toute personne susceptible de m'aider ...

Merci d'avance



PS : je précise quand même qu'il s'agit là de mon tout premier projet en C++, j'ai déjà utilisé la bibliothèque NTL mais mes fonctions n'étaient typiquement que du C, auquel j'ai intégré les classes NTL....
Donc pouvez vous SVP, m'expliquer comment résoudre ce problème de la facon le plus claire qui soit. Merci.

[befalimpertinent]

set parait approprier. Quel est le problème avec ton code ? Il compile ?
A part

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

s1.find(t) != 0

qui devrait plutôt être

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

s1.find(t) != s1.end()//trouvé

[DeathMixer]

Oui en effet, ca fonctionne correctement...

Espérons que maintenant je vais pouvoir l'utiliser dans une fonction plus complexe !!

Merci beaucoup pour ta réponse...