On pairs of primes with small order reciprocity

Stellen Sie sich vor, Sie versuchen, einen supersicheren digitalen Tresor zu bauen. Um das Schloss unknackbar zu machen, benötigen Sie zwei riesige, geheimnisvolle Zahlen (Primzahlen), die ein ganz spezielles Versteckspiel miteinander spielen. In der Welt der Kryptografie sind diese Zahlen die Schlüssel zu einer besonderen Art von Mathematik namens Pairing-basierten Zero-Knowledge-Beweisen. Diese Beweise ermöglichen es Ihnen, zu beweisen, dass Sie ein Geheimnis kennen, ohne das Geheimnis selbst preiszugeben – perfekt für anonymes Wählen oder private Transaktionen. Aber damit diese Beweise schnell genug für den praktischen Einsatz funktionieren, müssen die beiden Primzahlen „freundlich“ sein. Sie müssen eine ganz bestimmte, kleine Beziehung zueinander haben, bei der die eine Zahl sehr schnell in eine Potenz der anderen umgewandelt werden kann und umgekehrt. Wenn sie zu weit voneinander entfernt oder zu kompliziert sind, wird die Mathematik zu langsam für die Praxis. Wenn sie zu einfach sind, ist der Tresor vielleicht nicht sicher genug. Die große Frage lautet: Existieren diese perfekten, freundlichen Paare aus riesigen Zahlen tatsächlich in der Natur, oder sind sie nur ein mathematischer Mythos?

Dieses Paper ist eine massive digitale Schatzsuche nach genau diesen Paaren von Primzahlen. Die Autoren, Craig Costello und Gaurish Korpál, machten sich auf die Suche nach Paaren großer Primzahlen, bei denen jede eine „kleine Ordnung“ im Verhältnis zur anderen besitzt. Auf einfachem Deutsch ausgedrückt bedeutet dies: Wenn man eine Primzahl einige Male mit sich selbst multipliziert, erhält man schließlich eine Zahl, die bei der Division durch die andere Primzahl den Rest 1 lässt, und dies geschieht in einer überraschend geringen Anzahl von Schritten. Sie nennen diese Beziehung „Ordnungsreziprozität“.

Warum ist das wichtig? Weil das Finden dieser Paare der erste Schritt zum Bau eines „2-Zyklus“ spezieller Kurven ist, die in der Kryptografie verwendet werden. Diese 2-Zyklen könnten die Art und Weise, wie wir digitale Daten sichern, revolutionieren. Es gibt jedoch einen Haken: Die einzige bekannte Familie dieser Paare (die sogenannte MNT-Familie) ist bereits gut bekannt, weist aber einige Mängel auf, die sie für moderne Sicherheitsbedürfnisse weniger ideal machen. Die Autoren wollten wissen, ob es noch andere Paare da draußen gibt, insbesondere solche mit etwas größeren „Ordnungen“ (wie 12 oder 50), die vielleicht sicherer und effizienter sind.

Um die Antwort zu finden, baute das Team einen cleveren Computeralgorithmus – ein digitales Sieb –, das Millionen von Primzahlen scannen konnte, um diese seltenen Verbindungen aufzuspüren. Sie suchten nicht nur nach kleinen Zahlen; sie suchten tief, bis hin zur 200-Millionsten Primzahl. Sie suchten nach Paaren, bei denen die „Ordnungszahlen“ klein waren (zwischen 2 und 50), was der ideale Bereich für praktische Kryptografie ist.

Die Ergebnisse ihrer Suche waren eine Mischung aus aufregender Bestätigung und überraschender Knappheit. Sie fanden heraus, dass die berühmte MNT-Familie (mit den Ordnungen 4 und 6) immer noch der häufigste Typ von Paar ist, den sie selbst unter den größten Zahlen, die sie überprüften, finden konnten. Für andere Kombinationen waren die Paare jedoch unglaublich selten. Tatsächlich deutet ihre Datenbank darauf hin, dass es mit zunehmender Größe der Primzahlen immer schwieriger wird, diese speziellen Paare zu finden. Sie fanden genau ein Beispiel eines Paares mit den Ordnungen (12, 12) in ihrer gesamten massiven Suche, und für viele andere Kombinationen fanden sie absolut gar nichts.

Das Paper behauptet nicht, das Rätsel gelöst zu haben, ob unendliche Familien dieser Paare existieren. Stattdessen legt es nahe, dass sie verschwindend selten sein könnten. Die Autoren werfen mehrere offene Fragen auf: Ist das einzige (12, 12)-Paar, das sie fanden, das einzige, das existiert? Gibt es andere Kombinationen, die unendlich oft vorkommen, oder sterben sie alle aus, wenn die Zahlen größer werden? Ihre Arbeit beweist nicht, dass diese Paare nicht existieren, aber sie deutet stark darauf an, dass man, wenn man nach ihnen sucht, eine sehr gute Karte und viel Glück braucht, denn sie verstecken sich in den tiefsten, am dichtesten besiedelten Ecken des Zahlenuniversums.