Génération vraiment grand nombres premiers

Question

Je joue autour et essayer d'écrire une implémentation de RSA. Le problème est que je suis coincé 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 pointer vers un moyen rapide de générer d'énormes nombres premiers / nombres premiers probables?

Answer 1

Vous ne génèrent pas des nombres premiers exactement. Vous pouvez générer un grand nombre impair au hasard, puis tester si ce nombre est premier, sinon générer un autre au hasard. Il y a quelques lois des nombres premiers qui indiquent essentiellement que vos chances de « frapper » une prime par hasard essais est (2 / ln n)

Par exemple, si vous voulez un nombre premier aléatoire 512 bits, vous trouverez un à 2 / (512 * ln (2)) Donc, à peu près 1 sur chaque 177 des chiffres que vous essayez sera premier.

Il y a plusieurs façons de tester si un nombre est premier, un bon est le « test de Miller-Rabin » comme indiqué dans un autre répondre à cette question .

En outre, OpenSSL a une belle utilité pour tester les nombres premiers:

$ openssl prime 119054759245460753
1A6F7AC39A53511 is not prime

Answer 2

Jetez un oeil à la façon dont TrueCrypt t-il. De plus, jetez un oeil à Rabin-Miller pour tester un grand pseudopremiers.

Answer 3

Vous n'avez pas mentionné quelle langue que vous utilisez. Certains ont une méthode de le faire construit. Par exemple, en Java c'est aussi facile que d'appeler nextProbablePrime () sur un BigInteger.

Answer 4

La réponse précédente est incorrecte: 2 * 3 * 5 * 7 * 11 * 13 + 1 = 30 031 = 509 * 59

.

Je pense que l'affiche est misremembering (réel) la preuve qu'il y a sont un nombre incalculable de nombres premiers.

Answer 5

Mono a une classe BigInteger qui est open source tout comme java. Vous pouvez jeter un oeil à ceux-ci. Ils sont probablement portable :) g'luck

Answer 6

Il y a un algorithme en raison de U. Maurer qui génère démontrable aléatoire (contrairement à statistiquement hautement probable) des nombres premiers qui sont presque uniformément répartis sur l'ensemble de tous les nombres premiers d'une taille spéciale. J'ai une implémentation Python de ce qui est assez efficace à: http://s13.zetaboards.com/Crypto/topic/7234475/1/