So erstellen Sie eine große Primzahl | Quanta-Magazin

Primzahlen sind knifflige Dinge. In der Schule lernen wir, dass es sich um Zahlen handelt, die keine anderen Faktoren als 1 und sich selbst haben, und dass Mathematiker seit Tausenden von Jahren wissen, dass es unendlich viele davon gibt. Eines auf Befehl zu erstellen, scheint nicht schwierig zu sein.

Aber es ist. Die Konstruktion beliebig großer Primzahlen ist bemerkenswert kompliziert. Grundsätzlich stehen Ihnen zwei Rechenmöglichkeiten zur Verfügung, beide mit Nachteilen. Sie könnten den Zufall nutzen und durch Raten eine finden, aber die Methode ist inkonsistent – ​​Sie laufen Gefahr, jedes Mal eine andere Primzahl zu erzeugen. Oder Sie könnten einen zuverlässigeren, deterministischen Algorithmus verwenden, allerdings mit hohem Rechenaufwand.

Im Mai ein Team von Informatikern zeigte dass eine Art hybrider Ansatz auch funktionieren könnte. Sie veröffentlichten einen Algorithmus, der zufällige und deterministische Ansätze effektiv kombiniert, um eine Primzahl einer bestimmten Länge auszugeben, mit hoher Wahrscheinlichkeit, dieselbe Zahl zu liefern, selbst wenn der Algorithmus viele Male ausgeführt wird. Der Algorithmus verbindet Zufälligkeit und Komplexität auf interessante Weise und könnte auch für die Kryptographie nützlich sein, wo einige Kodierungsschemata auf der Konstruktion großer Primzahlen basieren.

„Sie legten eine Reihe von Versuchen vor, bei denen jeder versuchte, eine Primzahl unterschiedlicher Länge zu konstruieren, und zeigten, dass einer der Versuche funktionierte“, sagte er Roei Tell, ein theoretischer Informatiker am Institute for Advanced Study, der nicht an der Arbeit beteiligt war. „Es handelt sich um eine Konstruktion, die eine deterministisch gewählte Primzahl ausgibt, es einem aber ermöglicht, Münzen zu werfen und dabei zufällige Entscheidungen zu treffen.“

Die Herausforderung, ein effizientes Rezept für Primzahlen zu entwickeln, hat tiefe Wurzeln. „Wir wissen wirklich nicht viel darüber, wie Primzahlen verteilt sind oder über Lücken in Primzahlen“, sagte Ofer Grossman, der pseudozufällige Algorithmen untersucht. Und wenn wir nicht wissen, wo sie zu finden sind, gibt es keine einfache Möglichkeit, eine Primzahl von Grund auf zu generieren.

Im Laufe der Zeit entwickelten Forscher die oben genannten Ansätze. Der einfachste Weg ist einfach zu raten. Wenn Sie beispielsweise eine Primzahl mit 1,000 Ziffern wünschen, können Sie zufällig eine Zahl mit 1,000 Ziffern auswählen und diese dann überprüfen. „Wenn es nicht erstklassig ist, probieren Sie einfach ein anderes aus, und dann noch eins und so weiter, bis Sie eines finden“, sagte er Raul Santhanam, Informatiker an der Universität Oxford und Mitautor der neuen Arbeit. „Da es viele Primzahlen gibt, liefert Ihnen dieser Algorithmus nach einer relativ kleinen Anzahl von Iterationen eine Zahl, die mit hoher Wahrscheinlichkeit eine Primzahl ist.“ Aber die Verwendung von Zufälligkeit bedeute, dass man wahrscheinlich jedes Mal eine andere Zahl erhalte, sagte er. Das könnte ein Problem sein, wenn Sie Konsistenz benötigen – wenn Sie beispielsweise eine kryptografische Sicherheitsmethode verwenden, die von der Verfügbarkeit großer Primzahlen abhängt.

Der andere Ansatz besteht darin, einen deterministischen Algorithmus zu verwenden. Sie könnten einen Ausgangspunkt wählen und damit beginnen, Zahlen nacheinander auf Primzahl zu testen. Irgendwann sind Sie dazu bestimmt, einen zu finden, und Ihr Algorithmus gibt stets den ersten aus, den Sie finden. Aber es könnte eine Weile dauern: Wenn Sie eine Primzahl mit 1,000 Stellen suchen, sogar eine Rechnung mit 2⁵⁰⁰ Schritte – die viel länger dauern würden als das Alter des Universums – reichen nicht aus, um den Erfolg zu garantieren.

Im Jahr 2009 wollte der Mathematiker und Fields-Medaillengewinner Terence Tao es besser machen. Er forderte Mathematiker auf, einen deterministischen Algorithmus zu entwickeln, um innerhalb einer Rechenzeit eine Primzahl einer bestimmten Größe zu finden.

Diese Zeitgrenze wird als Polynomzeit bezeichnet. Ein Algorithmus löst ein Problem in Polynomzeit, wenn die Anzahl der Schritte, die er benötigt, nicht mehr als eine Polynomfunktion von ist n, die Größe der Eingabe. (Eine Polynomfunktion umfasst Terme, deren Variablen auf positive ganzzahlige Potenzen erhöht sind, z. B n² oder 4n³.) Im Kontext der Primzahlkonstruktion n bezieht sich auf die Anzahl der Ziffern in der gewünschten Primzahl. Rechnerisch gesehen kostet das nicht viel: Als einfach bezeichnen Informatiker Probleme, die sich durch Algorithmen in polynomieller Zeit lösen lassen. Im Gegensatz dazu benötigt ein schwieriges Problem exponentielle Zeit, was bedeutet, dass es eine Anzahl von Schritten erfordert, die durch eine Exponentialfunktion angenähert werden (die Begriffe wie 2 enthält).ⁿ).

Seit Jahrzehnten untersuchen Forscher den Zusammenhang zwischen Zufälligkeit und Härte. Das Problem der Primzahlkonstruktion galt als einfach, wenn man Zufälligkeit zuließ – und sich damit zufrieden gab, jedes Mal eine andere Zahl zu erhalten – und als schwierig, wenn man auf Determinismus bestand.

Noch ist es niemandem gelungen, Taos Herausforderung zu meistern, aber das neue Werk kommt ihm nahe. Es basiert stark auf einem Ansatz, der 2011 von Shafi Goldwasser und Eran Gat, Informatikern am Massachusetts Institute of Technology, eingeführt wurde. Sie beschrieben „pseudodeterministische“ Algorithmen – mathematische Rezepte für Suchprobleme wie die Suche nach großen Primzahlen, die sich die Vorteile des Zufalls zunutze machen und mit hoher Wahrscheinlichkeit immer noch die gleiche Antwort liefern könnten. Sie würden die Effizienz zufälliger Bits im Rezept nutzen, die im Ergebnis de-zufällig wären und deterministisch erscheinen würden.

Seitdem erforschen Forscher pseudodeterministische Algorithmen. Im Jahr 2017 haben Santhanam und Igor Oliveira von der University of Warwick (die ebenfalls zu der neuen Arbeit beigetragen haben) beschrieben ein pseudodeterministischer Ansatz zur Konstruktion von Primzahlen, der Zufälligkeit nutzte und überzeugend deterministisch aussah, aber in „subexponentieller“ Zeit funktionierte – schneller als exponentielle, aber langsamer als polynomielle Zeit. Dann im Jahr 2021, Tell und Lijie Chen, ein Informatiker an der University of California, Berkeley, erforscht wie man ein schwieriges Problem nutzt, um einen Pseudozufallszahlengenerator zu erstellen (ein Algorithmus, der eine Folge von Zahlen generiert, die nicht von einer Zufallsausgabe zu unterscheiden sind). „[Wir] haben einen neuen Zusammenhang zwischen Härte und Pseudozufälligkeit gefunden“, sagte Chen.

Im Frühjahr 2023 fügten sich die Teile schließlich zusammen ein Bootcamp zum Thema Rechenkomplexität am Simons Institute for the Theory of Computing in Berkeley, als die Forscher begannen, gemeinsam an dem Problem zu arbeiten und frühere Ergebnisse miteinander zu verknüpfen. Für die neue Arbeit, sagte Chen, hatte Hanlin Ren – ein Informatiker in Oxford und Mitautor – die ersten Ideen, das Chen-Tell-Ergebnis auf neuartige Weise mit dem Santhanam-Oliveira-Ansatz zu kombinieren. Anschließend entwickelte das gesamte Team die Ideen zur Erstellung des neuen Papiers weiter.

Der resultierende pseudodeterministische Algorithmus nutzte laut Santhanam neue Sichtweisen auf frühere Arbeiten, um Primzahlen in polynomieller Zeit zu erzeugen. Es nutzte nachweislich Zufälligkeit, um eine Primzahl einer bestimmten Länge auszugeben, und das Tool ist genauer als zufällige Schätzungen und recheneffizienter als deterministische Berechnungen.

Der neue Algorithmus sei außerdem bemerkenswert einfach, sagte Santhanam, und er könne auf eine Vielzahl von Suchproblemen angewendet werden – eigentlich auf jede dichte Teilmenge von Zahlen, wie etwa die Primzahlen, deren Zugehörigkeit in polynomieller Zeit bestimmt werden könne. Aber es ist nicht perfekt. Der Algorithmus funktioniert für unendlich viele Eingabelängen, deckt jedoch nicht alle Ziffernlängen ab. Möglicherweise sind noch einige Werte vorhanden n da draußen, für die der Algorithmus nicht deterministisch eine Primzahl erzeugt.

„Es wäre cool, diesen kleinen Vorbehalt loszuwerden“, sagte Grossman.

Das ultimative Ziel, sagte Santhanam, sei es, einen Algorithmus zu finden, der überhaupt keine Zufälligkeit erfordert. Aber diese Suche bleibt offen. „Determinismus ist das, was wir gerne nutzen würden“, sagte er.

Er wies aber auch darauf hin, dass pseudozufällige Prozesse mächtige Werkzeuge seien und Projekte wie die Konstruktion von Primzahlen nur eine Möglichkeit seien, sie zu nutzen, um Ideen aus Mathematik, Informatik, Informationstheorie und anderen Bereichen zu verbinden.

„Es ist spannend, darüber nachzudenken, wohin diese brillanten Beobachtungen sonst noch führen werden“, sagte Tell.