On pairs of primes with small order reciprocity

Stel je voor dat je probeert een superbeveiligde digitale kluis te bouwen. Om de vergrendeling onbreekbaar te maken, heb je twee gigantische, mysterieuze getallen (priemgetallen) nodig die een heel specifiek spelletje "verstoppertje spelen" met elkaar. In de wereld van de cryptografie zijn deze getallen de sleutels tot een speciaal soort wiskunde genaamd pairing-gebaseerde zero-knowledge bewijzen. Deze bewijzen laten je toe om te bewijzen dat je een geheim kent zonder het geheim zelf daadwerkelijk te onthullen—perfect voor anoniem stemmen of privétransacties. Maar voor deze bewijzen om snel genoeg bruikbaar te zijn, moeten de twee priemgetallen "vriendelijk" zijn. Ze moeten een specifieke, kleine relatie hebben waarbij het ene getal heel snel in een macht van het andere getal kan worden omgezet, en vice versa. Als ze te ver uit elkaar liggen of te ingewikkeld zijn, wordt de wiskunde te traag om praktisch te zijn. Als ze te simpel zijn, is de kluis misschien niet veilig genoeg. De grote vraag is: bestaan deze perfecte, vriendelijke paren van gigantische getallen eigenlijk in de vrije natuur, of zijn ze slechts een wiskundige mythe?

Dit artikel is een enorme digitale schattenjacht naar die specifieke paren priemgetallen. De auteurs, Craig Costello en Gaurish Korpál, zetten zich af om paren grote priemgetallen te vinden waarbij elk getal een "kleine orde" heeft ten opzichte van het andere. In gewone mensentaal betekent dit dat als je het ene priemgetal een paar keer met zichzelf vermenigvuldigt, je uiteindelijk een getal krijgt dat een restwaarde van 1 geeft bij deling door het andere priemgetal, en dat dit gebeurt met een verrassend klein aantal stappen. Ze noemen deze relatie "orde-reciprociteit".

Waarom is dit belangrijk? Omdat het vinden van deze paren de eerste stap is naar het bouwen van een "2-cyclus" van speciale curves die worden gebruikt in de cryptografie. Deze 2-cycli zouden de manier waarop we digitale gegevens beveiligen kunnen revolutioneren. Er is echter een addertje onder het gras: de enige bekende familie van deze paren (de MNT-familie) is al goed bekend, maar heeft enkele gebreken die het minder ideaal maken voor de moderne beveiligingsbehoeften. De auteurs wilden weten of er andere paren bestaan, vooral paren met iets grotere "ordes" (zoals 12 of 50) die mogelijk veiliger en efficiënter zijn.

Om het antwoord te vinden, bouwde het team een slim computeralgoritme—een digitale zeef—die miljoenen priemgetallen kon scannen om deze zeldzame verbindingen op te sporen. Ze keken niet alleen naar kleine getallen; ze zochten diep, tot aan het 200 miljoenste priemgetal. Ze zochten naar paren waarbij de "orde"-getallen klein waren (tussen 2 en 50), wat het ideale punt is voor praktische cryptografie.

De resultaten van hun zoektocht waren een mix van opwindende bevestiging en verrassende schaarste. Ze ontdekten dat de beroemde MNT-familie (met orden 4 en 6) nog steeds het meest voorkomende type paar was dat ze konden vinden, zelfs onder de grootste getallen die ze controleerden. Echter, voor andere combinaties zijn de paren ongelooflijk zeldzaam. In feite suggereert hun database dat naarmate de priemgetallen groter worden, het vinden van deze speciale paren steeds moeilijker wordt. Ze vonden precies één voorbeeld van een paar met orden (12, 12) in hun hele enorme zoektocht, en voor veel andere combinaties vonden ze absoluut niets.

Het artikel beweert niet het mysterie te hebben opgelost of er oneindige families van deze paren bestaan. In plaats daarvan suggereert het dat ze mogelijk uiterst zeldzaam zijn. De auteurs stellen verschillende open vragen: Is dat enkele (12, 12)-paar dat ze vonden het enige dat in de wereld bestaat? Zijn er andere combinaties die oneindig vaak voorkomen, of verdwijnen ze allemaal naarmate de getallen groter worden? Hun werk bewijst niet dat deze paren niet bestaan, maar suggereert sterk dat als je naar hen op zoek bent, je een zeer goede kaart en een hoop geluk nodig zult hebben, want ze verbergen zich in de diepste, meest drukke hoeken van het getallenuniversum.