On pairs of primes with small order reciprocity

Immagina di cercare di costruire una cassaforte digitale super sicura. Per rendere la serratura indistruttibile, hai bisogno di due numeri giganti e misteriosi (numeri primi) che giochino un gioco di "nascondino" molto specifico l'uno con l'altro. Nel mondo della crittografia, questi numeri sono le chiavi per un tipo speciale di matematica chiamata prove a conoscenza zero basate su accoppiamenti (pairing-based zero-knowledge proofs). Queste prove ti permettono di dimostrare di conoscere un segreto senza rivelare effettivamente il segreto stesso—perfetto per il voto anonimo o le transazioni private. Ma affinché queste prove funzionino abbastanza velocemente da essere utili, i due numeri primi devono essere "amichevoli". Devono avere una relazione specifica e piccola, in cui un numero può essere trasformato in una potenza dell'altro molto rapidamente, e viceversa. Se sono troppo distanti o troppo complicati, la matematica diventa troppo lenta per essere pratica. Se sono troppo semplici, la cassaforte potrebbe non essere abbastanza sicura. La grande domanda è: esistono davvero queste coppie perfette e amichevoli di numeri giganti nel mondo reale, o sono solo un mito matematico?

Questo articolo è una massiccia caccia al tesoro digitale alla ricerca di queste specifiche coppie di numeri primi. Gli autori, Craig Costello e Gaurish Korpál, si sono posti l'obiettivo di trovare coppie di grandi numeri primi in cui ciascuno abbia un "ordine piccolo" rispetto all'altro. In parole povere, questo significa che se moltiplichi un numero primo per se stesso alcune volte, otterrai infine un numero che lascia un resto di 1 quando diviso per l'altro numero primo, e questo accade con un numero sorprendentemente piccolo di passaggi. Chiamano questa relazione "reciprocità dell'ordine".

Perché questo è importante? Perché trovare queste coppie è il primo passo per costruire un "ciclo 2" di curve speciali utilizzate nella crittografia. Questi cicli 2 potrebbero rivoluzionare il modo in cui proteggiamo i dati digitali. Tuttavia, c'è un intoppo: l'unica famiglia nota di queste coppie (chiamata famiglia MNT) è già ben nota ma presenta alcuni difetti che la rendono meno che ideale per le moderne esigenze di sicurezza. Gli autori volevano sapere se esistono altre coppie là fuori, specialmente con "ordini" leggermente più grandi (come 12 o 50) che potrebbero essere più sicure ed efficienti.

Per trovare la risposta, il team ha costruito un algoritmo intelligente—un setaccio digitale—che potesse scansionare milioni di numeri primi per individuare queste rare connessioni. Non si sono limitati a cercare numeri piccoli; hanno cercato in profondità, controllando fino al 200 milioniesimo numero primo. Cercavano coppie in cui i numeri dell'"ordine" fossero piccoli (tra 2 e 50), che è il punto di equilibrio ideale per la crittografia pratica.

I risultati della loro ricerca sono stati un mix di eccitante conferma e sorprendente scarsità. Hanno scoperto che la famosa famiglia MNT (con ordini 4 e 6) è ancora il tipo di coppia più comune che riuscivano a trovare, anche tra i numeri più grandi che hanno controllato. Tuttavia, per altre combinazioni, le coppie sono incredibilmente rare. Infatti, il loro database suggerisce che man mano che i numeri primi diventano più grandi, trovare queste coppie speciali diventa sempre più difficile. Hanno trovato esattamente un esempio di una coppia con ordini (12, 12) in tutta la loro massiccia ricerca, e per molte altre combinazioni, non hanno trovato assolutamente nulla.

Il documento non sostiene di aver risolto il mistero della esistenza di famiglie infinite di queste coppie. Inve al, suggerisce che esse potrebbero essere evanescenti. Gli autori pongono diverse domande aperte: quella singola coppia (12, 12) che hanno trovato è l'unica esistente? Esistono altre combinazioni che appaiono infinitamente spesso, o scompaiono tutte man mano che i numeri diventano più grandi? Il loro lavoro non prova che queste coppie non esistano, ma suggerisce fortemente che, se le state cercando, avrete bisogno di una mappa molto buona e di molta fortuna, perché si nascondono negli angoli più profondi e affollati dell'universo numerico.