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 564 fois - Téléchargée 396 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

cs_JCDjcd
Messages postés
1138
Date d'inscription
mardi 10 juin 2003
Statut
Membre
Dernière intervention
25 janvier 2009
2 -
Pour quoi tu utilise la librairie NTL, ici tu n'a en fait rien fait de nouveau. Mois en premiere j'ai fais une TPE sur le RSA, et j'ai du aussi faire l'algorithme de Miller-Rabin, mais j'ai programmer moi meme les "PowerMod" & Co.

Programmer "PowerMod" est tres interessante, car il fuat que ce soit rapide avec des puissance tres grande. L'algotrihme utilisé est plus interrseant en soit, que le teste de primalite de Miller-Rabin.
D'aileurs je vien d'aller voir dans la librairie NTL, qu'il utilise cet algorithme.


c'est koi ce "int isprime(ZZ n, int nb_test 20)" ????20 dans la declaration de la fonction ! Bon sinon tu peux dire la probabilite d'erreur, qui est de (1/4)^20 ici, donc tres negligeable (enfin je crois que c'est ca, a verifier ...)
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
if(!(n%2)) return 0; // divisible par 2

tu peux faire n&1 je pense, j'ai lu ça il y a peu sur cppfrance. le principe c'est de vérifier juste le dernier bit, puisqu'il vaut 1 s'il est activé, et s'il n'est pas activé on a forcément un nb paire. c plus rapide de faire des opérations sur les bits qu'un modulo :-)
(faut qd même vérifier que c bien x&1...)

jvais me renseigner sur miller-rabin (euh, c'est deux types en fait?)
sibi12
Messages postés
337
Date d'inscription
jeudi 19 décembre 2002
Statut
Membre
Dernière intervention
15 avril 2006
-
kirua >
Oui, Miller et Rabin sont 2 personnes differentes.

Miller-Rabin est le test de primalité le plus rapide sur de grand nombre. Il lui faut en argument un nombre aléatoire avec lequel il effectue toute une série d'opération (voir plus haut).

on l'utilise énormémént en cryptographie même si ce test n'est pas decisif.c'est à dire que si le test est negatif, le nombre n'est pas premier sinon il ne donne qu'une probabilité que ce nombre soit premier.

en répetant ce test plusieur fois avec un nombre premier et comme argument un nombre aléatoire différent a chaque fois, on tend très vite vers une probabilité égale à un

Un algo interressant également est celui des 3 indiens mais il est assez difficile à coder...

@+
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
ouais j'ai lu l'article ds le science et vie hors série sur les nb premiers, mais c t y a un moment. ils parlaient des 3 indiens.
ils parlaient d'un algo de 11 (ou 13 sans plus) lignes, mais rien que la première condition (sur une ligne) demanderait plusieurs dizaines de lignes en C++ :-/
MetalDwarf
Messages postés
241
Date d'inscription
mardi 29 octobre 2002
Statut
Membre
Dernière intervention
23 janvier 2006
-
Pour repondre a JCDjcd c est vrai qu il n y a pas grand chose de nouveau dans ce code mais j ai decouvert l algorithme de Miller-Rabin il y a peu parce que je cherchais a voir si de tres grands nombres etaient premiers et j ai trouve interessant de le mettre ici.
Pour ce qui est de la gestion des grands nombres j ai une idee de la methode, surtout pour le PowerMod (exponentiation modulaire rapide...) car j ai lu un article qui traite des difficultes d implementation de RSA, et donc de cet algo mais je n ai pas eu le temps de le programmer. En plus NTL fait ca bien mieux (et BEAUCOUP mieux que maple 8...) et ca permet de voir sommairement comment marche cette bibliotheque.

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.