Erzeugen Sie wirklich große Primzahlen

StackOverflow https://stackoverflow.com/questions/1146274

Frage

Ich spiele herum und versuche eine Implementierung von RSA zu schreiben. Das Problem ist, dass ich an der Generierung der massiven Primzahlen festgefahren bin, die an der Generierung eines Schlüsselpaars beteiligt sind. Könnte jemand mich auf einen schnellen Weg verweisen, um riesige Primzahlen/wahrscheinliche Primzahlen zu erzeugen?

War es hilfreich?

Lösung

Sie generieren nicht genau Primzahlen. Sie generieren zufällig eine große ungerade Zahl und testen Sie dann, ob diese Zahl Prime ist, wenn nicht eine weitere zufällig generiert. Es gibt einige Gesetze von Primzahlen, die im Grunde genommen feststellen, dass Ihre Wahrscheinlichkeit, über zufällige Versuche eine Primzahl zu "treffen", (2/ln n) lautet.

Wenn Sie beispielsweise eine zufällige Primzahl von 512-Bit wünschen, finden Sie einen in 2/(512*ln (2)).

Es gibt mehrere Möglichkeiten, zu testen, ob eine Zahl Prime ist. Einer ist der "Miller-Rabin-Test" ist der "Miller-Rabin". Wie in einer anderen Antwort auf diese Frage angegeben.

Außerdem hat OpenSSL ein schönes Dienstprogramm zum Testen auf Primzahlen:

$ openssl prime 119054759245460753
1A6F7AC39A53511 is not prime

Andere Tipps

Schauen Sie sich an, wie TrueCrypt macht es. Schauen Sie sich auch einen Blick auf Rabin-Miller zum Testen großer Pseudoprimes.

Sie haben nicht erwähnt, welche Sprache Sie verwenden. Einige haben eine Methode, um dies eingebaut zu machen. Zum Beispiel ist dies in Java so einfach wie das Anruf NextProbablePrime () auf einem Bigintier.

Die vorherige Antwort ist falsch: 2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 = 509 * 59.

Ich denke, das Poster erinnert den (echten) Beweis, dass es eine unzählige Anzahl von Primzahlen gibt.

Mono hat eine BiginTeger -Klasse, die Open Source ist, ebenso wie Java. Sie könnten sich diese ansehen. Sie sind wahrscheinlich tragbar :) G'luck

Es gibt einen Algorithmus aufgrund von U. maurer, der zufällige nachweisbare Primzahlen (im Gegensatz zu statistisch hochprobierbaren) Primzahlen erzeugt, die fast einheitlich über den Satz aller Primzahlen einer speziellen Größe verteilt sind. Ich habe eine Python -Implementierung davon, die ziemlich effizient ist:http://s13.zetaboards.com/crypto/topic/7234475/1/

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top