Generazione Really Big numeri primi

Question

Sono suonare in giro e cercando di scrivere un'implementazione di RSA. Il problema è che mi sono bloccato sulla generazione di massicce numeri primi che sono coinvolti nella generazione di una coppia di chiavi. Qualcuno mi potrebbe puntare a un modo veloce per generare enormi numeri primi / numeri primi probabili?

Answer 1

Non generare numeri primi esattamente. Si genera un gran numero dispari in modo casuale, quindi verificare se quel numero è primo, se non crea un altro uno a caso. Ci sono alcune leggi di numeri primi che affermano in sostanza che le probabilità di "colpire" un primo via tentativi casuali è (2 / ln n)

Ad esempio, se si desidera un numero primo casuale di 512 bit, si trova uno in 2 / (512 * ln (2)) Quindi, circa 1 su ogni 177 dei numeri si tenta sarà primo.

Ci sono diversi modi per testare se un numero è primo, un buon uno è il "Miller-Rabin test" come indicato in un altro risposta a questa domanda .

Inoltre, OpenSSL ha un bel programma di utilità per verificare i numeri primi:

$ openssl prime 119054759245460753
1A6F7AC39A53511 is not prime

Answer 2

Date un'occhiata a come TrueCrypt lo fa. Inoltre, dare un'occhiata a Rabin-Miller per analisi su larga pseudoprimi.

Answer 3

Non hai parlato che lingua si sta utilizzando. Alcuni hanno un metodo di fare questo costruito in. Ad esempio, in Java questo è facile come chiamare nextProbablePrime () su un BigInteger.

Answer 4

La risposta precedente è corretta: 2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 = 509 * 59

.

Credo che il poster è misremembering la (vera) la prova che ci sono sono un numero incalcolabile di numeri primi.

Answer 5

Mono ha una classe BigInteger che è open source come fa java. Si potrebbe dare un'occhiata a quelli. Sono probabilmente portatile :) g'luck

Answer 6

C'è un algoritmo a causa di U. Maurer che genera dimostrabili casuale (in contrasto con statisticamente altamente probabile) numeri primi che sono quasi uniformemente distribuiti su l'insieme di tutti i numeri primi di un formato speciale. Ho un'implementazione di Python di esso che è abbastanza efficiente a: http://s13.zetaboards.com/Crypto/topic/7234475/1/