(r) è lafunzione di Eulero) si abbia: (x+a)

Teoria dei numeri

Lezione del giorno 14 maggio 2009

Il test di primalità AKS si basa sul seguente risultato (di cui diamo solo l’enunciato):

Teorema AKS.

Siano n un intero >2, ed r un naturale coprimo con n, tale che ord

n>log

n (dove ord

n indica il periodo di [n] nel gruppo Z

*) e tale che per ogni intero a con 1a

(dove

è la funzione di Eulero) si abbia:

(x+a)

x

+a (mod x

-1, n)

Allora: se n ha un fattore primo p>

, n è necessariamente una potenza di p.

Il test AKS si implementa nel modo seguente, dato in input un naturale n>2:

1) si testa se n è una potenza di base naturale con opportuno esponente naturale >1: in caso affermativo si esce con output “n è composto”, altrimenti si prosegue al passo successivo

2) Si cerca un naturale r coprimo con n tale che ord

n>log

n

3) Se esiste un divisore d di n, con d<n, nell’intervallo [2,

] si esce con output “n è composto”

4) Se per ogni naturale a con 1a

si ha (x+a)

x

+a (mod x

-1, n) si esce con output

“n è primo”, altrimenti si esce con output “n è composto”.

Verifichiamo prima di tutto che il test AKS è un test di primalità deterministico, quindi che un input n supera il test se e solo se n è primo.

Sia dunque n primo. Il passo 1) viene superato da n, in quanto n, essendo primo, non è potenza di base naturale con esponente naturale opportuno >1.

Il passo 3) viene superato da n in quanto n non ha divisori propri diversi da 1 e da n.

Infine nel passo 4) si esce certamente con output “n è primo” come conseguenza dell’implicazione () dell’ultimo teorema dimostrato (prima del Teorema AKS) in cui l’ipotesi a,n coprimi era superflua: infatti da tale implicazione segue (x+a)

x

+a (mod n) e dunque a maggior ragione (x+a)

x

+a (mod x

-1, n).

Viceversa se n è un input che fornisce output “n è primo”, dimostriamo che n è primo.

Per assurdo supponiamo che n superi il test AKS ma n non sia primo, e sia p un divisore primo di n, con p<n.

Poiché n supera il passo 1), si ha che n non è potenza di base naturale con esponente naturale >1.

Poiché n supera il passo 3), il divisore primo p è >

e per il Teorema AKS si conclude che n è potenza di p, con esponente naturale >1 (perché p<n), in contraddizione con il superamento del passo 1).

Il problema della complessità di calcolo del test AKS è interamente legato al naturale r trovato nel passo 2) (della cui esistenza ancora non siamo neanche formalmente certi).

Sarà utile il seguente risultato (di cui diamo solo l’enunciato):

Lemma AKS.

Se n>2 è un numero naturale, esiste un naturale rlog

n+1 coprimo con n, tale che ord

n>log

n (dove ord

n è il periodo di [n] nel gruppo moltiplicativo Z

*).

Dunque r esiste certamente, e inoltre il minimo r con le proprietà richieste è di ordine polinomiale

rispetto alla lunghezza binaria k dell’input n (perché n<2

, log

n<k, esiste rk

+1, e il minimo r è

dunque di ordine O(k

)).

Dimostriamo allora che il test di primalità AKS ha globalmente complessità polinomiale nella lunghezza binaria k dell’input n.

Abbiamo già visto in una lezione precedente che il passo 1) si esegue con complessità polinomiale, con un test che verifica se n è potenza di opportuna base naturale ed opportuno esponente >1.

La ricerca di r nel passo 2) si effettua facendo assumere ad r i valori successivi r=2,3…. e ad ogni valore testando se r,n sono coprimi (algoritmo Euclideo), e se il periodo di [n] nel gruppo Z

* è

>log

n (calcolando le potenze [n]

con 1ilog

n e verificando che nessuna coincida con [1]):

poiché come visto il numero di valori di r da testare (per trovare quello utile) è di ordine O(k

), anche questo passo 2) ha complessità polinomiale.

Nel passo 3), l’esistenza di un divisore d di n, con d<n, nell’intervallo [2,

] si effettua facendo assumere al naturale d tutti i valori in [2,

] e per ognuno testando se d é un divisore di n con d<n (il numero dei valori d da testare è <

<rlog

n<rk, quindi di ordine O(k

)).

Nel passo 4), per ogni naturale a con 1a

si testa se (x+a)

x

+a (mod x

-1, n) (il numero dei valori a da testare è come sopra di ordine O(k

)): tale congruenza si verifica calcolando le riduzioni modulo (x

-1, n) di ambo i membri (per il primo membro (x+a)

si usa l’esponenziazione modulare per i polinomi, di complessità polinomiale) e confrontando le riduzioni ottenute.

Poiché tutti i passi dell’algoritmo AKS sono di complessità polinomiale, lo stesso si può dire per

l’intero algoritmo.