TESTE SI UN TRES GRAND NOMBRE (PLUSIEURS MILLIERS DE CHIFFRES) EST PREMIER AVEC

Messages postés
1138
Date d'inscription
mardi 10 juin 2003
Statut
Membre
Dernière intervention
25 janvier 2009
- - Dernière réponse : tagwin
Messages postés
3
Date d'inscription
jeudi 15 janvier 2004
Statut
Membre
Dernière intervention
1 mai 2007
- 1 mai 2007 à 13:43
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/21009-teste-si-un-tres-grand-nombre-plusieurs-milliers-de-chiffres-est-premier-avec-ntl-et-miller-rabin

Afficher la suite 
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.
Super_Mat
Messages postés
37
Date d'inscription
jeudi 2 septembre 2004
Statut
Membre
Dernière intervention
31 août 2005
-
Dans ton code, tu dis :

tmp = n - 1
q = tmp

while(!(q % 2)) // on cherche t, nb de fois que 2 divise n

Or, t nb de fois que 2 divise q, c-a-d t nb de fois que 2 divise tmp, c-a-d t = nb de fois que 2 divise n- 1

Or, n != n-1 donc il y a une faute soit dans le code, soit dans le commentaire.

Tu pourais vérifier ?
MetalDwarf
Messages postés
241
Date d'inscription
mardi 29 octobre 2002
Statut
Membre
Dernière intervention
23 janvier 2006
-
L erreur est dans le commentaire bien evidemment. Je voulais dire (n-1) et non n. C est assez clair parce qu on cherche a savoir si n est premier, et si il est premier et different de 2 alors il n est pas divisible par 2. Par contre pour (n-1) on a un nombre pair, donc qui est divisible (au moins une fois) par 2.
Je suis desole pour cette erreur.

Par contre pour l implementation je crois qu elle est correcte, car ce programme me donne les meme resultats que Maple.
cs_ricezio
Messages postés
2
Date d'inscription
mardi 5 octobre 2004
Statut
Membre
Dernière intervention
25 janvier 2005
-
Je voudrais savoir:

power(num,2,3217); // 2^3217 - 1 est premier...
num--;

Ca sert a quoi ? je comprend pas trop !

Merci d'avance
Super_Mat
Messages postés
37
Date d'inscription
jeudi 2 septembre 2004
Statut
Membre
Dernière intervention
31 août 2005
-
Si tu lis bien, l'entrée de l'utilisateur est en commentaire, donc bloquée dans ce programme. Donc, le nombre qui est passé en paramètre est défini par le programme lui-même juste pour un essai.

power(num,2,3217);
num--;

calcule (2^3217)-1 .

Il calcule ce nombre car c'est un nombre très connu des mathématiciens : c'est un nombre de Mersenne (qui a l'avantage d'être grand : 969 chiffres) qui est premier. Donc normalement, le programme va répondre que ce nombre est premier.
MetalDwarf
Messages postés
241
Date d'inscription
mardi 29 octobre 2002
Statut
Membre
Dernière intervention
23 janvier 2006
-
Oui c est un des tests que j ai fait pour verifier la bonne implementation de l algorithme. D ailleurs pour la petite histoire j ai trouve ce nombre en utilisant maple sur un ordinateur en cours d info. Une simple petite boucle avec un test de primaute et c est parti (un petit conseil... prevoir du temps libre quand meme).

Et pour devancer une question potentielle, pour connaitre le nombre de chiffres d un nombre en base 10, il faut prendre la partie entiere plus 1 de log(nombre) avec log le logarithme decimal.
scelw
Messages postés
117
Date d'inscription
mercredi 3 septembre 2003
Statut
Membre
Dernière intervention
17 février 2007
-
est-ce que ça n'irait pas plus vite si au lieu de diviser le nombre par deux, on regardait juste son dernier chiffre pour voir s'il est pair ou impair ? c'est possible d'utiliser des fonctions comme right() avec des nombres ZZ ?

et est-ce qu'on pourrait pas aussi rajouter une condition (toujours dans le but de gagner du temps d'exécution) pour éliminer les nombres dont la somme des chiffres fait 9 (et qui dans ce cas là sont divisibles par 9)? De même, avec les chiffres terminés par 5 (qui sont divisibles par 5) ?

est-ce que ceci est réalisable avec NTL ??

merci!
sibi12
Messages postés
337
Date d'inscription
jeudi 19 décembre 2002
Statut
Membre
Dernière intervention
15 avril 2006
-
Je pense que tu devrai regarder la représentation binaire des nombres. diviser par 2 reviens a faire un decalage vers la droite ce qui est on ne peux plus rapide et verifier qu'un nombre est pair est encore plus rapide vu qu'il s'agit de regarder le bit le plus faible.

pour faire ce que tu dis il faut convertir tes nombres en chaine ce qui est assez lourd.
scelw
Messages postés
117
Date d'inscription
mercredi 3 septembre 2003
Statut
Membre
Dernière intervention
17 février 2007
-
je comprends pour les nombres pairs... mais pour les nombres divisibles par 9 ? et par 5 ? dans ces deux cas précis, n'est-il pas intéressant d'essayer de les éliminer avant d'effectuer le test de Miller-Rabin proprement dit ?
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
en fait, si tu testes (avant Miller Rabin) la divisibilité par les nombres premiers inférieurs à un certain nombre (mettons 2000), tu couvres déjà bcp de nombres, puisque la probabilité pour un entier d'être formé par un des plus petits nombres premiers est très grande. ça t'évite des bricolage avec les testes "humains" de divisibilité (par 9, 4, 8, 2, 3, 6, 5, 10 ...). D'autant plus que parmis ces tests ne sont utils que 2, 3 et 3 (les autres sont composés).

Générer les nombres premiers entre 2 et 2000 ça va très très vite (crible d'ératosthène), et ça ne prend pas des masses de place (Pi(2000) vaut pas grand chose, je sais pas combien mais ça doit aller)
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
2, 3, et 5, pardon.
MetalDwarf
Messages postés
241
Date d'inscription
mardi 29 octobre 2002
Statut
Membre
Dernière intervention
23 janvier 2006
-
Oui ca permet d accelerer l algorithme car tu elimine deja un tres grand nombre de possibilites si tu enleves tous ces nombres.
C est d ailleurs comme ca que les generateurs aleatoires de nombres premiers utilises dans les logiciels de crypatge (par exemple) fonctionnent.
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
ah, si tu as des infos sur la génération de grands nombres premiers je suis prenneur. Parce que à part tester un intervalle d'entiers... enfin, il y a bien cette "règle" comme quoi les nombres de la forme 6k + 1 et 6k - 1 sont souvent premiers, mais je me demande si ça ne vaut pas que pour les "petits" entiers (5, 7, 11, 13, 17, 19, 23, 29, 31, 37...). De toute façon si toutes les clefs étaient de cette forme ce serait plus facile à casser, donc c'est peu probablement comme ça qu'ils font. Tu as des infos? Je parle pas du crible d'ératosthène, parce que au-delà de 10 000 000 000 (et faut déjà vachement bien s'y prendre!) on a plus de mémoire...
sibi12
Messages postés
337
Date d'inscription
jeudi 19 décembre 2002
Statut
Membre
Dernière intervention
15 avril 2006
-
Une source comme celle ci a eu pas mal de commentaire et on parle de pas mal de chose qui tourne autour : http://www.vbfrance.com/code.aspx?ID=27662

hormis le code on parle de mersenne, fermat et d'autres
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
Ben Mersenne je veux bien mais c'est toujours le même problème. Si tous les documents RSA sont protégés par une clef multiple de deux nb de Mersenne, ça casse toute la protection :/

je vais lire les commentaires, mci.
Super_Mat
Messages postés
37
Date d'inscription
jeudi 2 septembre 2004
Statut
Membre
Dernière intervention
31 août 2005
-
Je ne suis pas sûr que si le RSA était construit à partir de Mersennes premiers ca se casserrait facilement.

A mon avis, le mieux est de partir d'un fermat, vérifier sa primalité et hop !
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
ben, logiquement il y a bcp moins de nombres de Mersenne premiers que des nombres premiers ^^ Donc ipso facto la protection est énormément réduite, étant donné que la protection de RSA réside dans la difficulté à factoriser une partie de la clef publique...
Super_Mat
Messages postés
37
Date d'inscription
jeudi 2 septembre 2004
Statut
Membre
Dernière intervention
31 août 2005
-
Donc la seule façon de procéder pour que les premiers ne soient pas sélectionnés est :

1 - prendre un entier au hazard
2 - s'il n'est pas premier, aller à 1
3 - utiliser ce nombre


En se basant sur le fait que 2 est rapide, et donc que le fait de boucler un nombre indéterminé de fois n'est pas conséquent.

Exact ?
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
ben c'est ma question: est-ce qu'il y a plus intelligent?? et mon idée de départ était plutôt de prendre un nombre au hasard, et s'il n'est pas premier de faire Nb++ et de tester celui-là... On évite une trop grosse par de chance (puisque potentiellement en prennant chaque fois au hasard ça peut prendre un temps infini, alors que comme on peut prouver (facilement) qu'il existe une infinité de nombre premiers, ou que tu te places au départ dans le corps des entiers, en faisant chaque fois +1 tu tomberas sur un premier à coup sûr en un nombre fini d'essais.
MetalDwarf
Messages postés
241
Date d'inscription
mardi 29 octobre 2002
Statut
Membre
Dernière intervention
23 janvier 2006
-
D apres ce que je sais et ce que j ai vu, c est effectivement comme ca que ca fonctionne. En tout cas c est comme ca que ca fonctionne dans la classe Biginteger de java qui peut etre utilisee pour tout ce qu on veut (en effet il faut lui passer en argument un generateur aleatoire donc avec un "bon" generateur aletaoire elle est "acceptable" pour du RSA par ex).

Un nombre de la longueur voulue est genere de facon aleatoire, et ensuite on teste si il est premier ou non avec d abord un crible simple (verifier la divisibilite par 2,3,5,7,11,...) puis par un algorithme probabiliste comme Miller-Rabin.

Je ne pense pas qu il existe de methode plus intelligente de recherche de grand nombre premier, car sinon la securite du systeme RSA (mais aussi DSA et d autres) serait affaiblie...

Mais si il s agit "simplement" de trouver un grand nombre premier "pour la beaute du geste" chercher un nombre de Mersenne doit etre payant.
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
"Mais si il s agit "simplement" de trouver un grand nombre premier "pour la beaute du geste" chercher un nombre de Mersenne doit etre payant."

Et même rémunérateur! Il y a des sommes énormes à gagner pour les gens qui trouvent des nombres premiers plus grands que tous ceux déjà trouvés. Il y a même un programme du style Seti@home qui fait ça, et les 4-5 derniers vainqueurs d'une prime utilisaient ce programme. Je sais plus comment il s'appelle...
MetalDwarf
Messages postés
241
Date d'inscription
mardi 29 octobre 2002
Statut
Membre
Dernière intervention
23 janvier 2006
-
Pour plus d informations sur la generation de nombres premiers en Java voici un patch envoye au projet gcj (compilateur java faisant partie du projet GNU).
La syntaxe est un peu bizarre car c est un fichier patch, mais c est lisible:

http://gcc.gnu.org/ml/java-patches/2000-q1/msg00120.html
scelw
Messages postés
117
Date d'inscription
mercredi 3 septembre 2003
Statut
Membre
Dernière intervention
17 février 2007
-
Il s'agit d'une question à propos du test de Miller-Rabin.
(>> http://cryptosec.lautre.net/article.php3?id_article= 12 ... à lire pour comprendre la suite! )
C'est l'un des tests les plus rapides qui existent au monde. Mais il possède un "goulot d'étranglement" qui limite malgré tout sa vitesse d'exécution dès lors que l'on veut tester des nombres de très grande taille (plus d'un million de chiffres) : le calcul de y = a^r mod n (voir lien donné ci-dessus).
Ma question est : pour diminuer sensiblement le temps d'exécution de ce test, serait-il possible de choisir a dans l'intervalle ]1 ; (n-1)/2[ , voire ]1 ; (n-1)/(10^1000)[ ??
Quelles répercussions sur le résultat ? La probabilité d'avoir un nombre premier est-elle fortement modifiée?
MetalDwarf
Messages postés
241
Date d'inscription
mardi 29 octobre 2002
Statut
Membre
Dernière intervention
23 janvier 2006
-
a mon avis si personne ne l'a fait, il y a bien une raison...
Super_Mat
Messages postés
37
Date d'inscription
jeudi 2 septembre 2004
Statut
Membre
Dernière intervention
31 août 2005
-
A priori, on peut limiter le domaine de a, mais on prend alors un risque plus grand de pseudo-primalité : en effet, la propriété est absolue (donc on peut dire si n est premier ou pas) si on fait le test pour tout a dans [1,n]. En pratique, on se prend quelques a au hasard.

En limitant davantage le domaine de a, la probabilité qu'un nombre pseudo-premier soit découvert augmente car il n'y a aucune chance de scanner certains a (au contraire de [1,n] où tous les a potentiels sont susceptibles d'être scannés)
scelw
Messages postés
117
Date d'inscription
mercredi 3 septembre 2003
Statut
Membre
Dernière intervention
17 février 2007
-
merci pour tes infos super_mat. ça me permet de voir plus clair dans les grandes lignes de l'algo...

est-ce qu'on peut limiter r aussi? car c'est surtout l'exposant qui augmente de manière exponentielle le temps des calculs... je sais que r est déduis du nombre de fois que 2 est multiple de (n-1). mais n'y aurait-il pas moyen de "truquer" cela sans pour autant rendre le test complétement invalide?
Super_Mat
Messages postés
37
Date d'inscription
jeudi 2 septembre 2004
Statut
Membre
Dernière intervention
31 août 2005
-
Non, on ne peut pas jouer sur r sinon cela fausse complétement les résultats.

Mais a^b % c n'est pas si gourmand que ca en calcul ! Evidemment, si on fait

x = a^b;
x = x % c;

Ca peut prendre beaucoup de temps. Mais la fonction d'exponentiation modulaire est bcp plus rapide.
scelw
Messages postés
117
Date d'inscription
mercredi 3 septembre 2003
Statut
Membre
Dernière intervention
17 février 2007
-
personnellement j'utilise la fonction powermod() de la la librairie NTL de Victor Shoup (www.shoup.net/ntl).
Est-ce que vous pourriez me dire si cette fonction utilise l'exponentiation modulaire? Car moi, ça met vraiment beaucoup de temps quand même... Il faut dire que je travaille avec des nombres d'un million de chiffres environ... (d'où mon besoin d'optimiser/accélerer le test de Miller-Rabin).

merci!
Super_Mat
Messages postés
37
Date d'inscription
jeudi 2 septembre 2004
Statut
Membre
Dernière intervention
31 août 2005
-
Assurément, NTL fait une exponentiation modulaire avec powermod.

Mais c'est normal d'avoir une certaine lenteur avec des millions de chiffres. Aujourd'hui, on considère normal de tester la primalité de nombres de 150,200 chiffres. A partir de 1000 chiffres, on considère qu'il n'existe pas de méthode pratique, c'est à dire fournissant un résultat rapidement.

Mais évidement, avec une machine rapide ca reste possible. Pour avoir des résultats plus rapide, il vaut mieux utiliser le test des trois Indiens dont on parle souvent, mais il est dur à implémenter (je vais essayer un de ces 4)

Ce qui est important, c'est de prendre a sur tout le domaine et d'avoir un générateur pseudo-aléatoire efficace.
scelw
Messages postés
117
Date d'inscription
mercredi 3 septembre 2003
Statut
Membre
Dernière intervention
17 février 2007
-
oui g déjà entendu parler de la découverte des trois indiens. pourquoi est-ce que cet algo est dur à implémenter?

"Ce qui est important, c'est de prendre a sur tout le domaine" ??? tu m'as dit plus haut qu'on pouvait limiter le domaine d'où a est tiré aléatoirement... ?

quelle est cette allusion à un générateur pseudo-aléatoire efficace? je ne comprends. je n'ai jamais utilisé un tel générateur.
Super_Mat
Messages postés
37
Date d'inscription
jeudi 2 septembre 2004
Statut
Membre
Dernière intervention
31 août 2005
-
J'ai dit que c'était possible (le programme ne plantera pas) mais cela trahi le théorème qui se cache derrière l'algorithme, à savoir "pour tout a = {2,...,n} etc"

Deja en ne prenant que quelques a sur ce domaine, on a des risques de se tromper, mais en plus en en prenant dans un ensemble inclu strictement dans le domaine, c'est encore moins bien. L'algorithme ne vaut alors plus rien du tout, et en tout cas le nombre de pseudo-premier va grandir très rapidement.

En ce qui concerne les pseudo-aléatoires, on les appelle pseudo car en réalité un ordinateur "de base" ne sait pas créer un nombre réellement aléatoire. a est pris pseudo-aléatoirement entre 2 et n à cette ligne :

a = RandomBnd(tmp-1) + 2; // nb aleatoire entre 2 et n

Il faut que l'ordinateur puisse trouver rapidement ce nombre aléatoire, sinon la vitesse de calcul tombe en chute libre ! D'où le problème de ma bibliothèque GN où toutes les fonctions aléa sont à revoir. Il faut de plus que ce générateur fournisse des résultats le plus aléatoires possible car s'il existe une corrélation forte entre les différents a, le test n'est plus équilibré statistiquement. (la probabilité est perturbée)
scelw
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??
Super_Mat
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
scelw
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
scelw
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
tagwin
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