Was ist ein möglicher Anwendungsfall von BigIntegers .isProbablePrime ()?

84

Die MethodeBigInteger.isProbablePrime() ist ziemlich seltsam; Aus der Dokumentation geht hervor, ob eine Zahl eine Primzahl mit der Wahrscheinlichkeit ist 1 - 1 / 2^arg, wo argsich das ganzzahlige Argument befindet.

Es ist schon ziemlich lange im JDK vorhanden, was bedeutet, dass es Verwendungszwecke haben muss. Meine begrenzten Kenntnisse in Informatik und Algorithmen (und Mathematik) zeigen mir, dass es nicht wirklich sinnvoll ist zu wissen, ob eine Zahl "wahrscheinlich" eine Primzahl ist, aber nicht genau eine Primzahl.

Was ist also ein mögliches Szenario, in dem man diese Methode verwenden möchte? Kryptographie?

fge
quelle
6
Auch Miller-Rabin-Primalitätstest . Der Hauptvorteil ist die Geschwindigkeit . Wenn Sie beispielsweise nach Faktoren suchen möchten, können Sie einen solchen Test durchführen, um den Factoring-Prozess zu beschleunigen. Sie können den "wahrscheinlich" Teil davon ziemlich niedrig halten, und es ist in der Praxis nützlich. Aber ich stimme zu, dass es ein bisschen wackelig und komisch ist, wie Schwimmer.
Keyser
2
@ maxx777 das ist eine Selbstverständlichkeit - ich frage nach einem tatsächlichen Anwendungsfall
fge
4
Ich möchte wirklich, dass die Downvoter die Gründe für die Downvotes erklären, bitte
am
17
"Es ist schon ziemlich lange im JDK vorhanden, was bedeutet, dass es Verwendungszwecke haben muss." - oder es wurde aus einem nutzlosen Grund hinzugefügt und dann nicht entfernt, weil nie etwas entfernt wird.
user253751

Antworten:

67

Ja, diese Methode kann in der Kryptographie verwendet werden. Bei der RSA-Verschlüsselung werden große Primzahlen gefunden, manchmal in der Größenordnung von 1024 Bit (ca. 300 Stellen). Die Sicherheit von RSA hängt von der Tatsache ab, dass das Faktorisieren einer Zahl, die aus zwei dieser Primzahlen besteht, die miteinander multipliziert werden, äußerst schwierig und zeitaufwändig ist. Aber damit es funktioniert, müssen sie erstklassig sein.

Es stellt sich heraus, dass es auch schwierig ist, diese Primzahlen zu beweisen. Der Miller-Rabin-Primalitätstest , einer der von verwendeten Primalitätstests isProbablePrime, erkennt jedoch entweder, dass eine Zahl zusammengesetzt ist, oder gibt keine Schlussfolgerung. Diese nTestlaufzeiten ermöglicht es Ihnen , zu dem Schluss , dass es eine 1 in 2 n Chancen , dass diese Zahl wirklich Verbund ist. Wenn Sie diese 100Zeiten ausführen, ergibt sich das akzeptable Risiko von 1 zu 2 100, dass diese Zahl zusammengesetzt ist.

rgettman
quelle
3
@ Mr.777 Ich habe Rabin-Miller ein- oder zweimal gesehen, aber Miller-Rabin zehnmal. Ich bin mir nicht sicher, ob es einen offiziellen Namen gibt.
Keyser
3
@ Mr.777 Auf der Wikipedia-Seite, die ich oben verlinkt habe, steht zuerst "Miller-Rabin", aber beide Namen werden anerkannt: "Der Miller-Rabin-Primalitätstest oder der Rabin-Miller-Primalitätstest".
Rgettman
5
Die Umsetzung von isProbablyPrimeist (soweit ich das beurteilen kann) völlig deterministisch. Wie würde das Ausführen der Testzeiten ndie Wahrscheinlichkeit eines korrekten Ergebnisses verbessern? (Selbst wenn es ein Element der Zufälligkeit wäre, müsste die Zufälligkeit mehrerer Anrufe unabhängig sein, um das Risiko in der von Ihnen beschriebenen Weise zu beeinflussen.)
Ted Hopp
11
@TedHopp Die Implementierung verwendet einen Zufallsgenerator, und jede Runde mit neuen Zufallszahlen bietet eine 3/4 Chance, einen Verbund zu erkennen. Der Standardgenerator ist SecureRandom mit starken Zufallsgarantien.
andere Typ
4
Es kann schwierig sein, aber denken Sie daran, dass PRIMES in P ist. Der AKS-Test ist möglicherweise langsamer als Miller-Rabin, aber es gibt keinen exponentiellen Unterschied oder ein Polynom zwischen ihnen. Sie können Miller-Rabin verwenden, um eine Reihe wahrscheinlicher Primzahlen zu finden, und AKS verwenden, um definitiv zu beweisen, dass es sich um Primzahlen handelt.
Bakuriu
20

Wenn der Test sagt, dass eine ganze Zahl keine Primzahl ist , können Sie sicher glauben, dass 100%.

Es ist nur die andere Seite der Frage, wenn der Test Ihnen sagt, dass eine ganze Zahl "eine wahrscheinliche Primzahl" ist, dass Sie Zweifel haben können. Durch Wiederholen des Tests mit variierenden "Basen" kann die Wahrscheinlichkeit, dass es fälschlicherweise gelingt, eine Primzahl (die eine starke Pseudo-Primzahl in Bezug auf mehrere Basen ist) fälschlicherweise zu "imitieren", so gering wie gewünscht gemacht werden.

Der Nutzen des Tests liegt in seiner Geschwindigkeit und Einfachheit. Man wäre nicht unbedingt zufrieden mit dem Status der "wahrscheinlichen Primzahl" als endgültige Antwort, aber man würde definitiv vermeiden, Zeit mit fast allen zusammengesetzten Zahlen zu verschwenden, indem man diese Routine verwendet, bevor man die großen Kanonen der Primalitätstests einführt .

Der Vergleich mit der Schwierigkeit, ganze Zahlen zu berücksichtigen, ist so etwas wie ein roter Hering. Es ist bekannt, dass die Primalität einer ganzen Zahl in Polynomzeit bestimmt werden kann, und es gibt tatsächlich einen Beweis dafür, dass eine Erweiterung des Miller-Rabin-Tests auf ausreichend viele Basen endgültig ist (beim Erkennen von Primzahlen im Gegensatz zu wahrscheinlichen Primzahlen), aber dies geht von der verallgemeinerten Riemann-Hypothese aus, ist also nicht ganz so sicher wie der (teurere) AKS-Primalitätstest .

Hardmath
quelle
4
Es ist erwähnenswert, dass AKS erst im August 2002 entdeckt wurde, während diese Methode seit Februar 2002 in JDK ist
James_pic
3
Nein, warte, das ist seit Februar 1997 im JDK (ich habe mir die probablePrimeMethode angesehen, nicht die isProbablePrimeMethode)
James_pic
1
In der Tat signalisiert der Titel von Agrawal, Kayal und Saxenas 2002 veröffentlichtem Artikel "PRIMES is in P" den ersten bedingungslosen Beweis für die Komplexität von Polynomen (in Bitlängen von n ) für deterministische (allgemeine ganzzahlige) Primalitätstests. Miller (1975) hatte gezeigt, dass unter der Annahme von GRH die Primalität einer ganzen Zahl in Schritten proportional zur vierten Potenz der Bitlänge deterministisch getestet werden kann, ein viel besserer Exponent als derzeit für AKS oder seine Varianten bekannt.
Hardmath
Während AKS asymptotisch schneller ist, wären Methoden wie ECPP für "kryptografische" oder "industrielle" Primzahlen viel effizienter.
Brett Hale
2
AKS ist wahnsinnig langsam und wird für keine Zahl, die in geologischer Zeit berechnet werden kann, viel schneller als APR-CL sein, geschweige denn für Menschen. APR-CL und ECPP gab es bereits 1997. Wie Brett erwähnt, ist ECPP eine gute Wahl, wenn wir einen Beweis wollen. All dies ist im Vergleich zu wahrscheinlichen Primmethoden (z. B. MR, BPSW, Frobenius) langsam.
DanaJ
19

Der Standardanwendungsfall für BigInteger.isProbablePrime(int)ist die Kryptographie. Insbesondere erfordern bestimmte kryptografische Algorithmen wie RSA zufällig ausgewählte große Primzahlen. Wichtig ist jedoch, dass diese Algorithmen nicht wirklich erfordern, dass diese Zahlen als Primzahl garantiert werden - sie müssen nur mit einer sehr hohen Wahrscheinlichkeit Primzahl sein.

Wie hoch ist sehr hoch? Nun, in einer Kryptoanwendung würde man normalerweise .isProbablePrime()mit einem Argument irgendwo zwischen 128 und 256 aufrufen. Somit ist die Wahrscheinlichkeit, dass eine Nicht-Primzahl einen solchen Test besteht, geringer als eine von 2 128 oder 2 256 .

Lassen Sie uns das ins rechte Licht rücken: Wenn Sie 10 Milliarden Computer hätten, von denen jeder 10 Milliarden wahrscheinliche Primzahlen pro Sekunde erzeugt (was auf jeder modernen CPU weniger als einen Taktzyklus pro Zahl bedeuten würde), und die Primalität dieser Zahlen wurde mit .isProbablePrime(128)Ihnen getestet Ich würde im Durchschnitt erwarten, dass alle 100 Milliarden Jahre eine Nicht-Primzahl einmal eintritt .

Das heißt, das wäre der Fall, wenn diese 10 Milliarden Computer Hunderte von Milliarden von Jahren laufen könnten, ohne dass Hardwarefehler auftreten. Obwohl in der Praxis ist es viel wahrscheinlicher , für eine zufällige die kosmische Strahlung auf den Computer schlägt genau zum richtigen Zeitpunkt und Ort des Rückgabewertes auf Flip von .isProbablePrime(128)von false auf true, ohne andere nachweisbaren Effekte verursacht, als es für ein nicht ist -Prime-Nummer, um den probabilistischen Primalitätstest bei dieser Sicherheitsstufe tatsächlich zu bestehen.

Das gleiche Risiko von zufälligen kosmischen Strahlen und anderen Hardwarefehlern gilt natürlich auch für deterministische Primalitätstests wie AKS . In der Praxis weisen daher selbst diese Tests aufgrund zufälliger Hardwarefehler eine (sehr kleine) falsch positive Grundlinienrate auf (ganz zu schweigen von allen anderen möglichen Fehlerquellen, wie z. B. Implementierungsfehlern).

Da ist es einfach , die intrinsische falsch - positive Rate des schieben Miller-Rabin-Tests durch verwendet .isProbablePrime()weit unter diesem Basisrate, einfach durch den Test ausreichend viele Male wiederholen, und da auch wiederholt , so oft ist der Miller-Rabin - Test noch In der Praxis viel schneller als die bekanntesten deterministischen Primalitätstests wie AKS, bleibt es der Standard-Primalitätstest für kryptografische Anwendungen.

(Selbst wenn Sie versehentlich ein starkes Pseudoprime als einen der Faktoren Ihres RSA-Moduls ausgewählt haben, würde dies im Allgemeinen nicht zu einem katastrophalen Ausfall führen. Typischerweise sind solche Pseudoprimes Produkte von zwei (oder selten mehr) Primzahlen von ungefähr Die Hälfte der Länge, was bedeutet, dass Sie am Ende einen Multi-Prime-RSA-Schlüssel erhalten . Solange keiner der Faktoren zu klein war (und wenn dies der Fall wäre, hätte der Primalitätstest sie abfangen sollen), wird der RSA-Algorithmus dies tun funktionieren immer noch einwandfrei, und der Schlüssel sollte, obwohl er gegen bestimmte Arten von Angriffen etwas schwächer ist als normale RSA-Schlüssel gleicher Länge, dennoch einigermaßen sicher sein, wenn Sie nicht unnötig an der Schlüssellänge sparen.)

Ilmari Karonen
quelle
Das Fehlerproblem ist ein Grund, warum AKS nicht tatsächlich verwendet wird (die erstaunlich langsame Geschwindigkeit ist die andere), und ECPP ist häufiger. Wie Sie bemerken, sind Implementierungsfehler in den Algorithmen durchaus möglich, daher ist es hilfreich, ein Zertifikat mit unabhängigem Code überprüfen zu lassen.
Danaj
8

Ein möglicher Anwendungsfall besteht darin, die Primalität einer bestimmten Zahl zu testen (bei einem Test, der an sich viele Verwendungszwecke hat). Der isProbablePrimeAlgorithmus läuft viel schneller als ein exakter Algorithmus. Wenn also die Zahl fehlschlägt isProbablePrime, muss man nicht auf die Kosten des teureren Algorithmus gehen.

Ted Hopp
quelle
Also, ist das dann aus praktischen Gründen? Und aufgrund der Tatsache, dass die Primfaktorisierung ein NP-Problem ist?
fge
@fge - Ja, der von mir vorgeschlagene Anwendungsfall dient der praktischen Anwendbarkeit. Ich weiß nicht, dass dies bei der Primfaktorisierung hilft, was ein wesentlich schwierigeres Problem ist als das Testen der Primalität. Für letztere gibt es einen Polynom-Zeit-Algorithmus: den AKS-Primalitätstest .
Ted Hopp
5
@fge: Faktorisierung ist in der Tat in NP, aber ich vermute, Sie meinten "NP-vollständig", was Faktorisierung nicht bekannt ist. Im Gegenteil, es wird stark vermutet, dass es nicht NP-hart ist.
Hmakholm verließ Monica
6

Das Finden wahrscheinlicher Primzahlen ist ein wichtiges Problem in der Kryptographie. Es stellt sich heraus, dass eine vernünftige Strategie zum Finden einer wahrscheinlichen k-Bit-Primzahl darin besteht, wiederholt eine zufällige k-Bit-Zahl auszuwählen und sie mit einer Methode wie der wahrscheinlichen Primalität zu testen isProbablePrime().

Weitere Informationen finden Sie in Abschnitt 4.4.1 des Handbuchs für angewandte Kryptographie .

Siehe auch Zur Erzeugung wahrscheinlicher Primzahlen durch inkrementelle Suche von Brandt und Damgård.

NPE
quelle
5

Algorithmen wie die RSA-Schlüsselgenerierung hängen davon ab, ob eine Zahl eine Primzahl ist oder nicht.

isProbablePrimeZum Zeitpunkt der Aufnahme der Methode in das JDK (Februar 1997) gab es jedoch keine nachgewiesene Möglichkeit, deterministisch zu entscheiden, ob eine Zahl in angemessener Zeit eine Primzahl war. Der zu dieser Zeit bekannteste Ansatz war der Miller-Rabin-Algorithmus - ein probabilistischer Algorithmus, der manchmal falsch positive Ergebnisse liefert (dh Nicht-Primzahlen als Primzahlen meldet), aber auf Kosten der Wahrscheinlichkeit von falsch positiven Ergebnissen angepasst werden kann von bescheidenen Erhöhungen der Laufzeit.

Seitdem wurden Algorithmen entdeckt, die deterministisch entscheiden können, ob eine Zahl relativ schnell eine Primzahl ist, wie beispielsweise der im August 2002 entdeckte AKS-Algorithmus. Es ist jedoch zu beachten, dass diese Algorithmen immer noch nicht so schnell sind wie Miller-Rabin.

Eine vielleicht bessere Frage ist, warum isPrimedem JDK seit 2002 keine Methode hinzugefügt wurde.

James_pic
quelle
Danke für die historische Perspektive! Sieht so aus, als wäre @immibis mit seinem Kommentar zu "im JDK, aber nie entfernt" auf dem richtigen Weg? :)
fge
1
Ich weiß, dass Java bekanntermaßen niemals Inhalte aus der Standardbibliothek entfernt, aber ich bin nicht sicher, ob sie diese entfernen würden, selbst wenn sie könnten. Bei einigen Anwendungen ist es gut genug, 99,999999999% sicher zu sein, dass etwas gut genug ist, und es ist viel schneller als 100% sicher.
James_pic