Teste si un tres grand nombre (plusieurs milliers de chiffres) est premier avec ntl et miller-rabin

Soyez le premier à donner votre avis sur cette source.

Vue 16 679 fois - Téléchargée 400 fois

Description

Juste une petite implementation de l'algorithme de Miller-Rabin en C++ avec NTL. NTL est une bibliotheque C++ qui permet de manipuler de tres grand nombres (je ne sais meme pas si il y a une limite) et de faire des operations dessus (les operrateurs ont ete redefinis et bien d autres encore...).
L'algorithme de Miller-Rabin est un algorithme probabiliste, qui ne permet pas de prouver qu un nombre est premier ou compose mais de le dire avec une TRES faible incertitude. Il est utilise dans tous les systemes ayant besoin de GRANDS nombres premiers (RSA par exemple...).

Pour le compiler il faut NTL qui se trouve ici : www.shoup.net/ntl
Cette librairie se compile sans mal sous Linux ou VC++.

Source / Exemple :


/* Ce programme donne un "avis" sur la primalite

  • d'un nombre meme tres grand en utilisant l'algorithme
  • de Miller-Rabin et la bibliotheque NTL (www.shoup.net/ntl)
*
  • Compile sous Linux avec g++ -lntl isprime.cpp -o isprime
  • Devrait passer sous windows avec la librairie NTL
  • /
#include <NTL/ZZ.h> #include <iostream> /* 1er argument : le nombre a tester 2e argument : le nombre de tours de boucles a effectuer + il est grand + la fiabilite est grande mais + le temps de calcul aussi! */ int isprime(ZZ n, int nb_test = 20) { ZZ q,p,a,b; ZZ tmp = n-1; int t = 0; int e = 0; if(!(n%2)) return 0; // divisible par 2 q = tmp; while(!(q % 2)) // on cherche t, nb de fois que 2 divise n { t++; q = q / 2; } for(int i=0;i<nb_test;i++) { a = RandomBnd(tmp-1) + 2; // nb aleatoire entre 2 et n e = 0; b = PowerMod(a, q, n); // b = a^q mod n if(b!=1) { while((b!=1) && (b!=(n-1)) && (e<(t-1))) { e = e + 1; b = SqrMod(b, n); // b = a^2 mod n } if(b!=tmp) return 0; // compose } } return 1; // peut-etre premier } int main(int argc, char **argv) { ZZ num; // cout << "Entrez un nombre a tester :"; // cin >> num; power(num,2,3217); // 2^3217 - 1 est premier... num--; if(isprime(num)) cout << "\nPeut-etre premier.\n"; else cout << "\nCompose\n"; cout << num << "\n"; }

Conclusion :


Ce programme a ete teste sous Linux mais doit fonctionner sous windows (j ai teste un autre programme avec la NTL sous windows).

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Messages postés
3
Date d'inscription
jeudi 15 janvier 2004
Statut
Membre
Dernière intervention
1 mai 2007

Bonjour "MetalDwarf", je voudrais juste savoir un petit détail stp sur l'installation de la bibliotheque NTL C++ sous windows, je dois la compiler ou comment dois je faire??

merci
Messages postés
117
Date d'inscription
mercredi 3 septembre 2003
Statut
Membre
Dernière intervention
17 février 2007

J'ai trouvé une méthode pour compresser encore le temps d'exécution du test de Miller-Rabin (test probabiliste et non déterministe mais qui a l'avantage d'être le plus rapide, d'être généraliste (les nombres à tester n'ont pas besoin d'être d'une forme particulière) et très fiable). Dans un post plus haut, j'ai identifié le goulot d'étranglement du test (le point qui consomme le plus de temps d'exécution) comme étant la ligne de calcul "y = a^r mod n". Or plutôt que de choisir a non pas entre 1 et n - 1 (au risque de tomber sur de très grands a), mais entre 1 et ln n (ce qui est un intervalle déjà beaucoup plus restreint, surtout pour de grands n).

Voir le très intéressant débat suivant (qui porte exactement sur cette question) : http://les-mathematiques.u-strasbg.fr/phorum/read.php?f=2&i=128589&t=128589
Messages postés
117
Date d'inscription
mercredi 3 septembre 2003
Statut
Membre
Dernière intervention
17 février 2007

je n'ai pas ICQ mais je serai intéressé par "davantage de conversation"... MSN Messenger c'est possible ? mon adresse est : jojo29118@hotmail.com
Messages postés
37
Date d'inscription
jeudi 2 septembre 2004
Statut
Membre
Dernière intervention
31 août 2005

L'algorithme parait simple, mais quand on regarde de près, on a

SI a , alors b ;

et la condition a peut avoir 20,30 lignes de conditions à vérifier ;-)

Si tu veux davantage de conversation, mon num ICQ : 281-692-688
Messages postés
117
Date d'inscription
mercredi 3 septembre 2003
Statut
Membre
Dernière intervention
17 février 2007

D'accord, merci bien...

Pourquoi est-ce que l'algo des trois indiens est dur à implémenter??
Afficher les 40 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.