Randint Overflow : Comment générer de très grands nombres premier en python

Bonjour à tous,

Je suis actuellement en train de préparer un TIPE de cryptographie, principalement sur le codage RSA, mais je suis confronté à un problème.

En effet, je ne peux pas générer de nombres supérieurs à 1e308 (ce qui est déjà grand je vous le concède), car python me lève l'exception : "OverflowError: cannot convert float infinity to integer". Cependant, mon algorithme de Miller Rabin est bien loin de ses limites et reste un peu sur sa faim.

De ce fait, je voudrais savoir s'il existe un moyen de surpasser cet overflow, soit par une astuce que je ne connais pas, ou bien en téléchargeant un module plus puissant que random (si ça existe).

Voila, c’est pas primordial pour mon TIPE mais sa m’intéresse de savoir si je peux allez encore plus loin dans la génération d'entiers premiers.

Enfin, j'utilise python 3.3 (sous spyder) avec le module Random.

Merci beaucoup pour votre aide et pour vos réponses

Denis

PS : Python n'a aucun mal à me stocker des nombres de plus de 2000 chiffres, donc le problème vient bel et bien de randint (randrange possède la même limite).

Bonjour,

Avez-vous pris connaissance de ce qui se dit sur random et la cryptographie ici : https://docs.python.org/3/library/random.html ?

@+.

Bonjour,

Ta méthode est bonne (randint + Miller-Rabin), mais il y a une petit erreur: 1e308 est un nombre flottant.

Voilà comment on peut générer un nombre au hasard de 500 chiffres:

Code:

---

1 2 3

print(randint(10**500, 10**501-1))   602840927750645230812994914056080334614243416900514212712006926411872651583159559004108529460024934143403846213506465685992091942656287632053898494593258869587909641136147832710667852121177467398397077520646041471769789567631421069358710110074801391039073924535764748682408982558055881987991215337620910490527687382145503491321396124654502842215920318602340435292297399907453332259424240587231864981658035389854784123966071077859588337211968704233931583382060442859386700500940204208060626056605276105

---

Avec un peu de calcul binaire, on peut aussi générer un nombre entier au hasard de x bits de long (512, 1024, 2048, etc...)

Bonsoir,

Merci beaucoup Tyrtamos, j'ai essayé et en effet ça fonctionne tout de suite mieux :) En effet, j'avais pas fait attention que 1e308 était un flottants.

Tarball69, j'avais en effet vu cette page, mais je n'y avait pas trouvé ce que je cherchais (je le reconnais j'ai survolé plus que lu ;) ). Par ailleurs, pour ce qui est de la sécurité des tirages pseudos aléatoires, je comptait m'y pencher plus tard, j'ai d'autre bug à corriger avant, et je préfère utiliser randint car pour l'instant je ne suis pas en mesure de justifier précisément en quoi l'autre méthode est favorable. Toutefois, je m'y consacrerais car cela m’intéresse tout de même.

Encore merci à vous deux pour vos réponses rapides et claires

Denis

Bonjour,

Pour la recherche d'un nombre premier au hasard, le fait que random n'ai pas une sécurité suffisante pour la cryptographie n'est pas grave, puisque tous les nombres sont testés par Miller-Rabin. Par contre, il ne faut pas oublier d'appeler random.seed() après l'importation de random, sinon on aura toujours la même série aléatoire à chaque lancement du programme.

Le jour où tu cherches un générateur de nombre pseudo-aléatoire reconnu pour la cryptographie, regarde du côté de blum blum shub (http://fr.wikipedia.org/wiki/Blum_Blum_Shub). Il est assez facile à programmer en Python, et je me suis un peu amusé avec (http://python.jpvweb.com/mesrecettes...id=genalea_bbs).