Je joue et essaie d'écrire une implémentation de RSA. Le problème est que je suis bloqué sur la génération des nombres premiers massifs qui sont impliqués dans la génération d'une paire de clés. Quelqu'un pourrait-il me diriger vers un moyen rapide de générer d'énormes primes/primes probables?Générer des nombres premiers VRAIMENT grands
Vous ne générez pas de nombres premiers exactement. Vous générez un grand nombre impair aléatoirement, puis testez si ce nombre est premier, sinon générez un autre au hasard. Il y a certaines lois des nombres premiers qui stipulent que vos chances de "frapper" un premier via des essais aléatoires est (2/ln n)
Par exemple, si vous voulez un nombre premier aléatoire de 512 bits, vous trouverez one in 2/(512 * ln (2)) Donc, environ 1 sur 177 des nombres que vous essayez seront premiers.
Il existe plusieurs façons de tester si un nombre est premier, un bon est le "test Miller-Rabin" comme indiqué ci-dessus.
En outre, OpenSSL a une belle utilité pour tester les nombres premiers:
$ openssl prime 119054759245460753
1A6F7AC39A53511 is not prime
Jetez un coup d'œil à la façon dont TrueCrypt le fait. En outre, jetez un oeil à Rabin-Miller pour tester de grands pseudoprimes.
Pourquoi supposez-vous que TrueCrypt génère des nombres premiers? Pour autant que je sache, il n'utilise que du crypto symétrique. – CodesInChaos
Vous n'avez pas mentionné la langue que vous utilisez. Certains ont une méthode de faire cela intégré. Par exemple, dans Java, c'est aussi simple que d'appeler nextProbablePrime() sur un BigInteger.
J'utilise Objective-C – computergeek6
Selon la façon dont cette fonctionnalité est implémentée, vous pouvez compromettre votre choix de clé si l'espace de recherche est réduit. – Stephen
La réponse précédente est incorrecte: 2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 = 509 * 59.
Je pense que l'affiche est misremembering (réel) la preuve qu'il ya sont un nombre incalculable de nombres premiers.
En fait, il n'y a qu'un nombre dénombrable (mais infini) de nombres premiers. En outre, l'autre affiche (dont le message semble être supprimé maintenant) ne se méprend pas sur la construction à partir de la preuve (c'est vraiment comme ça que ça se passe) mais elle en abuse plutôt. – oggy
En effet. Rappelez-vous que les entiers sont dénombrables, ça va "1, 2, ...". Ainsi sont les nombres premiers et rationnels; ce sont les nombres réels qui ne sont pas dénombrables. – jrockway
Mono a une classe BigInteger qui est open source, tout comme java. Vous pourriez jeter un coup d'oeil à ceux-ci. Ils sont probablement portables :) g'luck
Il y a un algorithme en raison de U. Maurer qui génère des nombres premiers prouvables aléatoires (contrairement à très probable statistiquement) qui sont presque uniformément distribué sur l'ensemble de tous les nombres premiers d'une taille spéciale. J'ai une implémentation Python qui est assez efficace à: http://s13.zetaboards.com/Crypto/topic/7234475/1/
Merci. Cela explique beaucoup de problèmes que j'avais. – computergeek6
vous pouvez également générer des nombres premiers dans openssl: 'openssl premier -generate -bits 512' – mykhal