Générateur de grands nombres premiers (bis)

Soyez le premier à donner votre avis sur cette source.

Vue 6 532 fois - Téléchargée 814 fois

Description

Ce code permet de générer de très grands nombres premier (de 256 bits et plus). Le programme utilisé est un test probabiliste (le nombre est premier avec une certaine marge d'erreur). Cependant, en augmentant le nombre d'itération on peut avoir une marge d'erreur inférieure à 1/10^20.
2 tests de primalité sont proposés : test de Solovay et Strassen ainsi que Miller-Rabin.
Les nombres sont codés en utilisant une classe qui permet de gérer dynamiquement des nombres d'une très grande taille (aucune limite fixée)
Enfin, le programme peut générer les paramètres pour les clés de l'algorithme de cryptage RSA à partir des nombres premiers trouvés.

Codes Sources

A voir également

Ajouter un commentaire Commentaires
Messages postés
2070
Date d'inscription
mardi 22 avril 2003
Statut
Membre
Dernière intervention
3 juillet 2006
8
Je ne peux pas trop te renseigner la dessus, je ne maitrise pas trop le sujet (moins calé en math/algo qu'en C/C++). A mon avis ça doit pas trop influencer mais normalement le calcul de a^r mod n doit être assez optimisé déjà.
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 ...[bà 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?
Messages postés
241
Date d'inscription
mardi 29 octobre 2002
Statut
Membre
Dernière intervention
23 janvier 2006

ces fonctions sont deja inluses dans NTL, dans la classe ZZ (celle des grands entiers).
l operateur % est defini si mes souvenirs sont exacts, / aussi.
et pour les puissances il y a power(), ou meme powermod si tu veux calculer a^n mod n...
Voila!!
Messages postés
1
Date d'inscription
lundi 1 mars 2004
Statut
Membre
Dernière intervention
1 mars 2004

Suis aussi trés intérréssé d'avoir une réponse à la question de "scelw" concernant GMP, moi j'utilise NTL (dérivé de GMP si j'ai bien compris) mais les temps de réponses sont incomparables, beaucoup plus rapide sous GMP, le hic, c'est que je suis incapable d'utilisé GMP sous Windows (GMP prévu pour tourné sous Linux...que je ne connais pas...pas encore...)

J'ai besoin des fonctions puissance (a^n, avec des a tres grand environ 50-100 Millions), division, et modulo

Merci pour un ptit conseil
Messages postés
117
Date d'inscription
mercredi 3 septembre 2003
Statut
Membre
Dernière intervention
17 février 2007

si l'on manipule des nombres d'1 million de chiffres, qu'est-ce qui se passe ? ralentissement ? overflow ?

et connaissez-vous la librairie GMP ? c'est presque la même chose non ? y a-t-il une différence ?
Afficher les 10 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.