Il test di primalità AKS

L'algoritmo AKS è un algoritmo per determinare se un numero $ n $ è primo in tempo polinomiale. Si basa sul teorema di Agrawal-Kayal-Saxena

Come funziona l'algoritmo?

Controllo se $ n $ è una potenza perfetta
Se $ n = m^k $ per qualche $ m, k \in \mathbb{N} $ con $ k > 1 $, allora $ n $ non è primo perché è una potenza di un numero più piccolo. In questo caso, il numero $ n $ è composto e l'algoritmo termina.
Questo controllo elimina i numeri sicuramente non primi come le potenze perfetta, perché il quadrato di un numero primo è sicuramente un numero composto (es. 7²=49).
Trovo un valore piccolo di $ r $
Cerco il più piccolo intero $ r $ in cui l'ordine moltiplicativo di $ n $ modulo $ r $, ossia $ Ord(r, n) $, sia maggiore di $ 4 \log^2 n $. $$ Ord(r, n) > 4 \log^2 n $$
Controllo il massimo comune divisore (MCD)
Se esiste un numero $ a \leq r $ tale che $ 1 < \text{MCD}(a, n) < n $, significa che $ n $ è composto perché ha un divisore non banale. Quindi, il numero $ n $ è composto e l'algoritmo termina.
Se $ n \leq r $, allora è primo
Se il numero è così piccolo da essere minore o uguale a $ r $, allora è sicuramente primo.
Test polinomiale
Verifico l'equivalenza sequente per vari valori di $ a $ da 1 a $ | 2 \sqrt{\phi(r)} \log_2 n | $ $$ (x + a)^n \equiv x^n + a \pmod{x^r - 1, n} $$ Se l'equivalenza è soddisfatta per ogni valore di $ a $, allora il numero $ n $ è primo. In caso contrario $ n $ è composto.

Un esempio pratico

Considero come esempio il numero intero seguente:

\[ n=1009 \]

Utilizzo il test di primalità AKS per capire se è un numero primo.

Per prima cosa verifico che $n$ non sia una potenza perfetta nella forma $m^k$ per qualche intero $m$ e $k>1$.

In questo cso $1009$ non è una potenza perfetta, dunque procedo.

Scelgo il più piccolo intero $r$ tale che l'ordine moltiplicativo di $n$ modulo $r$ soddisfi la seguente:

\[ \operatorname{Ord}_r(1009) > 4 \log_2^2(1009) \]

Sapendo che $\log_2(1009)$ è circa 10, dunque $4\log_2^2(1009) \approx 4 \times 10^2 = 400$.

\[ \operatorname{Ord}_r(1009) > 400 \]

Per semplificare l’esempio, suppongo di trovare un intero $r$ che è anche primo), in questo modo la funzione di Eulero è facile da calcolare. Se $r$ è primo, $\phi(r)=r-1$.

Ad esempio, scelgo $r=409$ e la funzione di Eulero è $\phi(409)=408$.

Se $1009$ agisce da generatore modulo $409$, allora l’ordine $\operatorname{Ord}_{409}(1009)=408$, che soddisfa $408 > 400$.

Nota. In un’implementazione reale dovrei verificare, per ogni candidato $r$, che l’ordine moltiplicativo di $1009$ modulo $r$ sia effettivamente maggiore di $4\log_2^2(1009)$. In questo caso, suppongo che la scelta $r=409$ sia valida.

A questo punto controllo dei massimi comuni divisori (MCD)

Per ogni intero $a$ compreso tra 2 e $r$ verifico che

\[ 1 < \gcd(a,1009) < 1009. \]

Dal momento che $1009$ è primo, per ogni $a$ si ha $\gcd(a,1009)=1$. Quindi non si individuano divisori non banali e il test continua.

Verifico se $n\le r$

Controllo se $n\le r$ allora il numero verrebbe dichiarato primo senza ulteriori controlli.

In questo caso $1009 > 409$, dunque procedo al passo successivo.

L'ultima verifica è il test polinomiale.

Devo verificare che per ogni $a$ compreso tra 1 e $ \left\lfloor 2\sqrt{\phi(r)}\log_2(1009) \right\rfloor \approx 404 $ valga la congruenza:

\[ (x+a)^{n} \equiv x^{n}+a \pmod{x^{r}-1,\;n} \]

Dove $ n=1009 $ e $ r = 409 $.

\[ (x+a)^{1009} \equiv x^{1009}+a \pmod{x^{409}-1,\;1009} \]

Poiché $1009$ è effettivamente un numero primo, la congruenza pèverificata per tutti gli interi $a$ da 1 a 404.

\[ (x+1)^{1009} \equiv x^{1009}+1 \pmod{x^{409}-1,\;1009} \]

\[ (x+2)^{1009} \equiv x^{1009}+2 \pmod{x^{409}-1,\;1009} \]

\[ (x+3)^{1009} \equiv x^{1009}+3 \pmod{x^{409}-1,\;1009} \]

\[ \vdots \]

Avendo superato tutte le fasi del test AKS, inclusa la verifica polinomiale, il procedimento conclude che $1009$ è un numero primo.

E così via.