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

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?

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 ⁿ 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.

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 .

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 ¹²⁸ oder 2 ²⁵⁶ .

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.)

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.

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.

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.