Numeri primi e complessità:l'algoritmo AKS

Numeri primi e complessità: l'algoritmo AKS

I primi giorni di agosto, nel mondo matematico è circolata velocemente la notizia che tre giovani ricercatori dello Indian Institute of Technology di Kanpur avevano risolto un problema congetturato da tempo e cercato per anni. Il loro articolo, insieme ad alcuni commenti ed alle prime reazioni della stampa e della comunità matematica, si può trovare sul sito www.cse.iitk.ac.in/news/primality.html

Un problema banale si dirà: basta dividere n per tutti i primi p che sono minori di n e vedere se il risultato è intero. Se questo avviene, n è composto e, di più, si trovano anche i suoi fattori primi. Altrimenti n è un numero primo. Anzi, se si vuole risparmiare tempo, da Eratostene in poi, è noto che basta prendere p minore della radice quadrata di n. Ecco un algoritmo che sicuramente porta al risultato della primalità per ogni n, con esito positivo o negativo che sia.
Ma, soprattutto dopo l'avvento dei grandi calcolatori elettronici, i numeri da valutare e che ricorrono nella pratica possono essere incredibilmente lunghi, con centinaia o migliaia di cifre decimali. E allora questo algoritmo che, per giungere a conclusione richiede un tempo che cresce esponenzialmente al crescere del numero di cifre di n, può risultare intollerabilmente lungo, anche con gli strumenti di calcolo più veloci: anni, secoli, più della vita presunta dell'universo.
Il lavoro annunciato dai ricercatori indiani si inserisce qui, nella scoperta di un algoritmo, già denominato AKS, (dalle iniziali dei nomi Agrawal, Kayal e Saxena), che riduce in maniera drastica il tempo di calcolo. È allo stesso tempo un risultato di Teoria dei numeri, perché sfrutta una proprietà caratteristica dei numeri primi, e di Teoria della complessità computazionale, perché mostra come si possa costruire un algoritmo efficiente a partire da questa proprietà.

Che cosa significa efficiente in questo contesto? Significa che PRIMES, il problema decisionale della primalità, si può risolvere con un algoritmo deterministico, in un tempo che cresce solo in maniera polinomiale al crescere del numero di cifre di n. Come si dice, il problema appartiene alla classe P e, fin dal titolo, il lavoro mette l'accento proprio su questo aspetto: "PRIMES is in P". La caratterizzazione dei numeri primi appare in secondo piano: comporta solo considerazioni elementari e in questo potrebbe essere una delle tante che sono note, seppure niente affatto banale. La vera intuizione è quella di poter implementare la condizione in tempo polinomiale.

Per chiarire maggiormente il contenuto del lavoro e l'importanza dell'algoritmo AKS, è utile ricordare il famoso piccolo teorema di Fermat:

"se p è un numero primo e a è un intero non divisibile per p, allora a^p- a è divisibile per p."

Per molti anni si è ritenuto che questa fosse una condizione necessaria e sufficiente perché p sia primo. Ma non è così. La condizione è necessaria ma non sufficiente o, in altri termini, per ogni a esistono dei numeri p che verificano la proprietà precedente cioè che dividono a^p- a, ma non sono primi.

Ad esempio, se si prende a = 2, il calcolo delle congruenze permette facilmente di verificare che 341 = 11·31 divide 2341 - 2. Si dice che 341 è uno pseudoprimo in base 2 per significare che soddisfa la condizione con a = 2 ma non è primo (341 è il più piccolo pseudoprimo in base 2). Analogamente 91 = 7·13 è il più piccolo pseudoprimo in base 3 ed è noto che, per ogni base a, esistono infiniti pseudoprimi in quella base. Anzi: esistono infiniti numeri di Carmichael, vale a dire numeri che sono pseudoprimi in ogni base, il più piccolo dei quali è 561 = 3·11·17.
Non è pertanto possibile prendere il piccolo teorema di Fermat come test deterministico di primalità: se un numero p non supera il test per qualche base a, nel senso di non dividere a^p- a, allora è certamente un numero composto, ma se il test è superato per qualche a, niente può essere detto di sicuro: gli pseudoprimi superano felicemente il test pur non essendo primi.
Tuttavia il teorema, opportunamente adattato, può essere usato, e lo è stato di fatto a partire dagli anni '70, per dare dei test probabilistici di primalità: pur di ripetere il test con basi diverse, la probabilità che il numero sotto esame passi il test eppure non sia primo si può rendere tanto piccola quanto si voglia.

Altri test di primalità, probabilistici e/o condizionali, basati su altri principi, sono stati ovviamente elaborati nel tempo e risultano molto efficienti. La novità dell'algoritmo AKS è quella di essere deterministico e non condizionale, di esecuzione abbastanza semplice e basato sulla fondamentale proprietà enunciata dal piccolo teorema di Fermat.

In che cosa consiste l'algoritmo AKS? Il punto di partenza è un teorema, già utilizzato pochi anni fa da Agrawal (insieme a Biswas) per un criterio probabilistico di primalità, che caratterizza i numeri primi p attraverso il calcolo dei coefficienti del polinomio (x - a)^p - (x^p - a).
In questa forma, la condizione è lunga da usare, perché richiede la verifica che tutti i coefficienti binomiali da 1 a p - 1 siano divisibili per p. L'idea è ora quella di calcolare il valore assunto a meno di un polinomio della forma (x^r - 1). In altri termini, di eseguire il calcolo nell'anello quoziente dell'anello dei polinomi a coefficienti in Zp rispetto all'ideale generato da x^r - 1.
Purtroppo con questa riduzione si perde la parte sufficiente della condizione, la quale, per alcuni valori di r e di a, può essere soddisfatta anche da un numero composto. Si tratta di eliminare questi casi: gli autori dimostrano che, a questo scopo, si può scegliere un esponente r opportuno, per il quale è sufficiente controllare un numero "piccolo" di valori di a, tale da richiedere un tempo polinomiale. Per questo l'algoritmo esegue sostanzialmente due cicli, il primo dei quali è inteso a scegliere un valore "buono" di r, mentre il secondo varia in un limitato range di valori per a. La dimostrazione della condizione necessaria e del fatto che è anche sufficiente entro i limiti indicati per r ed a, richiede alcune considerazioni sottili ma elementari di Algebra e di Teoria dei numeri.

Il tempo di esecuzione stimato è piuttosto lungo, ma pur sempre polinomiale: per un numero dato, cresce con la potenza dodicesima del suo numero di cifre binarie. Questo tempo si può ricondurre alla potenza sesta pur di dimostrare una ipotesi, del tutto plausibile e verificata per numeri fino a 10¹⁰, sulla distribuzione dei cosiddetti numeri primi di Sophie Germain (i primi r tali che 2r + 1 sia ancora primo).

Ulteriori miglioramenti, fino alla terza potenza, possono provenire dalla dimostrazio-ne di una congettura avanzata nel lavoro.

Quali sono le implicazioni del risultato? L'algoritmo fornisce una svolta significativa in un settore lungamente atteso e di grande interesse pratico, ma per ora non sembra che possa avere una immediata applicazione. Per gli usi della Crittografia, ad esempio, che soprattutto ricorrono a grandi numeri primi, gli algoritmi probabilistici di primalità risultano molto più efficienti.
L'importanza dell'algoritmo AKS è soprattutto concettuale. L'interesse destato nel mondo matematico riguarda l'aspetto computazionale ma anche il fatto di usare metodi semplici, elementari, senza far ricorso a teorie elaborate. È un algoritmo che utilizza in maniera originale la classica teoria dei numeri e senza dubbio, oltre a far riflettere su quanti risultati nuovi sono ancora da scoprire in questa teoria, potrà essere migliorato di molto, fino a diventare veramente utile nella pratica.