Discussion :

[Timias]

Bonjour,

Je suis actuellement en train d'essayer de reproduire un système de chiffrement RSA, et je dois donc générer 2 nombres premiers distincts (de grande taille). Mon code pour générer ces valeurs (p et q) est le suivant (j'utilise la fonction random.randrange, avec un pas de 2 pour générer uniquement des nombres impairs) :

Code :

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

1
2
3
4
5
6
7
8
 
p=randrange(borneInf, borneSup, 2)
q=randrange(borneInf, borneSup, 2)
while not estPremierMillerRabin(p,25):
	p=randrange(borneInf, borneSup, 2)
while (not estPremierMillerRabin(q,25) or q==p):
	q=randrange(borneInf, borneSup, 2)
return (p,q)

J'utilise donc le test de primalité de Miller-Rabin (avec 25 itérations) pour vérifier la primalité de ces nombres (avec une forte probabilité).

En Python 2.7, mon code trouve deux valeurs de nombres premiers très rapidement, même pour de très grandes valeurs (sur 512 bits par exemple). Cependant, je suis passé en Python 3.5, et je constate que mon code fonctionne mais de façon beaucoup plus lente : il met énormément de temps à générer un nombre qui passe le test de Miller-Rabin (il met 5 minutes à générer des nombres qui fonctionnent, ce qu'il faisait en 10 secondes pour la même taille). Je suis donc obligé de réduire la taille de mes clés, ce qui accélère la recherche de nombre premiers, pouvoir avoir un temps d'exécution raisonnable.

Connaissez-vous l'origine de cette différence dans la génération de nombres aléatoires en Python3 ?

Merci d'avance !

[fred1599]

Bonjour,

(il met 5 minutes à générer des nombres qui fonctionnent, ce qu'il faisait en 10 secondes pour la même taille)

Il ne peut pas y avoir une telle différence d'exécution sur un même algorithme entre les deux versions de python.

[tyrtamos]

Bonjour,

J'avais remarqué ça aussi, mais je ne sais pas pourquoi.

Cependant, le temps obtenu est très variable puisqu'il est basé sur la "chance" d'obtenir le bon nombre rapidement à partir d'un tirage au hasard. Et il faut, bien sûr, faire le seed() de random sans lequel la séquence pseudo-aléatoire est toujours la même à chaque exécution.

Par exemple sur 5 essais:
- pour un nombre premier de 512bits, j'obtiens un temps qui peut varier de 0.2s à 4.5 s.
- pour un nombre premier de 1024 bits, j'obtiens un temps qui peut varier de 2s à 1mn15s
- pour un nombre premier de 2048 bits, j'obtiens un temps qui peut varier de 1mn à 6mn

Ce sont des nombres énormes! Pour 1024 bits, le nombre fait environ 300 chiffres. Par exemple:

Code :

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

1
2
3
4
5
167401362849382042583948096175192218444714227011114960490055158328050183058156781455880338260497561293501566992296608875670221386122395737696403816169925243091613758916645928785837317042718836952836686920539307357180138455674323546775242966701044817267770959278689307084971399510565356283050347602270211305971
93135579506474718086734601732510815332782579331485126313835874443407453028918304554639494587855728117665216496157710783356704265795174629264981117642569853682778900285164255549240354794895935660947548111296080762445361500933498343315912594088827972581200848987112331221768124751432714124867573086543292306579
137119271650544188032501376625535777877692214743485758720627731427297986772859370795879852156176310799915810673807355793879670726164684643678266135619741912039633297342872701169136660328338743144419264725176205077218268836425810652833200444493193250292344992082081709070782031717120050891174591458082737446311
151041784305814556393989171956390776150611927838393985833885167174220004103995532634514426860757583327417990776867044407198741367054929897069998571180434523746303879639552704047975854477246306067861234074459580396060364878436981602568734713004224179889282874336427137934786090356229488615109548687288150027829
161277604233631111768780475868482747657953225712504684528581127542739367110273017935639971922893827918358684741930811687967771121477791442852933928077948872842946224791232843047251755000413827125101140895586169980087697919445690512920670605613421386612808920975058300343108470145663543411486983498519065039777

Ce qui fera un nombre p*q pour RSA de 600 chiffres! Compte tenu du problème, c'est tout de même un résultat étonnant: qui a dit que Python était lent?

[Sve@r]

Code python :

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

1
2
3
4
5
6
7
p=randrange(borneInf, borneSup, 2)
q=randrange(borneInf, borneSup, 2)
while not estPremierMillerRabin(p,25):
	p=randrange(borneInf, borneSup, 2)
while (not estPremierMillerRabin(q,25) or q==p):
	q=randrange(borneInf, borneSup, 2)
return (p,q)

Code python :

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

1
2
3
4
5
6
7
8
while True:
	p=randrange(borneInf, borneSup, 2)
	if estPremierMillerRabin(p, 25): break
while True:
	q=randrange(borneInf, borneSup, 2)
	if q != p and estPremierMillerRabin(q, 25): break
 
return (p,q)

Ca ne devrait rien trop changer à la vitesse (un peu tout de même dû au test de différence entre "p" et "q" plus rapide avant le test de primalité de "q" plus lent) mais ça allège le code en évitant de répéter les instructions p=randrange(borneInf, borneSup, 2).


Maintenant pour comparer la vitesse entre P2 et P3, il manque des informations et surtout, comme l'a dit tyrtamos, il nous manque de savoir si tu utilises le même seed dans les deux versions (pour avoir une génération de nombres identique)...

[Timias]

Bonjour à tous,

Merci pour vos réponses ! En effet j'utilise bien la fonction seed() pour générer des séquences différentes à chaque fois.
J'ai bien conscience du caractère aléatoire de l'algorithme, ce qui peut expliquer certaines variations dans le temps d'exécution.
Je n'ai pas fait de mesures exactes, c'est juste un constat général du fait que cette partie du code étant exécuté quasi-instantanément en 2.7, met maintenant plusieurs minutes à s'exécuter en python 3.5. J'ai retrouvé les mêmes ordres de grandeur pour une dizaine d'essais dans chaque version, je pensais donc qu'il pouvait y avoir une explication technologique, plutôt que de la simple malchance.

Merci en tout cas pour vos pistes de recherches !