Generieren genau Primzahl mit Java
Ich bin mir bewusst, der die Funktion BigInteger.probablePrime(int bitLength, Random rnd), die Ausgänge wahrscheinlich prime Anzahl von bit Länge. Ich will eine ECHTE Primzahl in Java. Gibt es eine FOSS-Bibliothek zu tun, also mit annehmbarer Leistung? Vielen Dank im Voraus!
EDIT:
Ich bin auf der Suche auf 1024 & 2048-bit-Primzahlen.
Sind Sie sicher, dass Sie brauchen echte Primzahlen? In den meisten Fällen relativ prime ist gut genug. Die meisten RSA-Schlüssel generiert werden, mit relativ prime zahlen.
Sie wahrscheinlich tun nicht schreiben wollen, jede Kryptographie-Zeug, wenn Sie nicht verstehen, dass es mehr wahrscheinlich, dass Sie bekommen, vom Blitz getroffen an dem Tag, Sie gewann die nationale Lotterie als es wahrscheinlich ist, dass probablePrime bekommt man eine nicht-Primzahl (wenn Sie richtig genannt). Es ist alles über Wahrscheinlichkeiten 🙂
Sie wahrscheinlich tun nicht schreiben wollen, jede Kryptographie-Zeug, wenn Sie nicht verstehen, dass es mehr wahrscheinlich, dass Sie bekommen, vom Blitz getroffen an dem Tag, Sie gewann die nationale Lotterie als es wahrscheinlich ist, dass probablePrime bekommt man eine nicht-Primzahl (wenn Sie richtig genannt). Es ist alles über Wahrscheinlichkeiten 🙂
InformationsquelleAutor Viet | 2010-05-21
Du musst angemeldet sein, um einen Kommentar abzugeben.
edit: Oder, wenn Sie nicht Vertrauen die isProbablePrime groß genug sein, Sicherheit, verwenden Sie die BigInteger-Konstruktor
BigInteger(int bitLength, int certainty, Random rnd)
, können Sie tune Ihre Sicherheit-Schwelle:Probabilistische tests, die für kryptografische Zwecke verwendet werden garantiert, um gebunden die Wahrscheinlichkeit von false-positives-es ist nicht so, es gibt einige gotcha zahlen, die vorhanden sind, schleichen Sie durch, es ist nur eine Frage der wie tief Sie wollen, dass die Wahrscheinlichkeit zu sein. Wenn Sie nicht Vertrauen Sie die Java-Klasse BigInteger, diese zu verwenden, (es wäre schön, wenn Sie dokumentiert, welcher test verwendet wurde), verwenden Sie das Rabin-Miller test.
+1 - es sollte jedoch angemerkt werden, dass der Schlimmste Fall von AKS ist
O((logN)^12)
. Das ist schnell im Vergleich mit factorizing besterN
, aber nicht schnell, in absoluten zahlen.+1 vielen Dank! Mehr Sicherheit sicherlich erhöht die Sicherheit.
"Mehr Sicherheit sicherlich die Sicherheit erhöht" - können Sie ziemlich sicher sein, aber nicht absolut sicher. 😉
InformationsquelleAutor Jason S
Gibt es einige Methoden zur Erzeugung von sehr großen Primzahlen mit akzeptabler Leistung, aber nicht mit ausreichender Dichte für die meisten anderen Zwecke nutzen, als sich in das Guiness-Buch der Rekorde.
Sehen Sie es so: die Wahrscheinlichkeit, dass eine Zahl zurückgegeben, die von
probablePrime()
ist nicht prim ist niedriger als die Wahrscheinlichkeit, dass Sie und alle die Sie kennen erste Treffer durch Beleuchtung. Zweimal. An einem einzigen Tag.Einfach nicht darum kümmern.
Ich nehme an, Sie wollen zu implementieren, die eine RSA-Algorithmus? Sogar die offizielle Implementierungen von diesen verwenden müssen, wahrscheinlich Primzahlen.
die kryptographischen Gemeinschaft verwendet wahrscheinlich prime tests zu erzeugen kryptographisch sichere zufällige Primzahlen.
So "wahrscheinlich" ist untertrieben, aber Sie wollte nicht, um den Namen der Methode
almostAlwaysButOnceInABlueMoonNotPrime()
... 😉Dann nutzen Sie probablePrime(). Das ist was für. Niemand in der ganzen weiten Welt kennt eine bessere Methode. Und wenn Sie es Taten, es würde höchstwahrscheinlich bedeuten, dass prime-basierten Kryptographie nutzlos geworden.
InformationsquelleAutor Michael Borgwardt
Konnte man auch mit dem Konstruktor von
BigInteger
zu erzeugen eine echte prime:Die Zeit zum ausführen der proportional ist zu der Sicherheit, aber auf meinem Core i7 ist es kein problem.
InformationsquelleAutor Bart van Doormaal
Machen eine Methode, und wickeln Sie es.
Wie denken Sie, isPrime funktioniert? Wahrscheinlich ist es der gleiche test, dass probablePrime verwendet, um zu bestimmen, ob die Zufallszahl eine Primzahl ist.
Interessanterweise ist diese Antwort (von 5 Jahren) hat die gleichen grundlegenden Eigenschaften wie die Antwort akzeptieren. Eine wahrscheinliche Primzahl und weiter zu testen, bis Sie sicher sind, dass es composite.
Ich Stimme mit @Silver, wie können wir schreiben das isPrime Methode?
Es gibt zahlreiche Möglichkeiten, zu bestimmen, ob eine Zahl eine Primzahl ist oder nicht, von denen alle über den Rahmen der Frage.
InformationsquelleAutor corsiKa
Ist die Wahrscheinlichkeit, dass ein
BigInteger
zurückgegeben MethodeprobablePrime()
ist composite nicht überschreiten 2^-100.InformationsquelleAutor Corona Luo