Teorema di Agrawal-Kayal-Saxena (AKS)

Il test AKS verifica la primalità di \( n \) usando proprietà algebriche invece dei tradizionali test di divisibilità. In altre parole, impiega dei polinomi per testare la struttura interna di \( n \).

Un algoritmo di primalità basato sul teorema AKS ha il vantaggio di funzionare in tempo polinomiale rispetto a \( \log n \), quindi è molto efficiente rispetto ai metodi classici.

Nota. Il termine $ \varphi(r) $ è la funzione di Eulero che conta quanti interi minori di $ r $ sono coprimi con \( r \).

Un esempio pratico

Ecco un esempio di utilizzo del test di primalità AKS per verificare se un numero è primo.

Considero il numero \( n = 5 \) è verifico se è primo. Lo so... è banale ma così è più semplice da capire.

Passo 1: Verifico se \( n \) è una potenza di un numero primo

Il numero \( 5 \) non è una potenza di un numero primo, cioè non si può scrivere come \( p^k \) con \( k > 1 \), quindi posso procedere.

Passo 2: Trovo un valore di \( r \)

Devo trovare il più piccolo numero primo \( r \) tale che soddisfi queste condizioni:

• \( k = Ord(r,n) > 4\,(\log_2 n)^2  \)
• \( r \leq \lfloor 16 \log_2^5 n \rfloor + 1 \)

Essendo un esempio didattico con \( n = 5 \) molto piccolo, per illustrare la parte polinomiale del test, considero il numero \( r = 3 \).

Si tratta di una semplificazione per rendere più comprensibili e immediati i calcoli.

Nota. In realtà il numero $ r= 3 $ non soddisfa le condizioni del teorema. Ad esempio, l'ordine moltiplicativo di $ n=5 $ nel modulo $ r=2 $ è $ k = Ord(3,5)= 2 $ $$ 5^2 \equiv 1\;(\bmod\,3) $$ Ma $ k=2 $ non è superiore a \(4\,(\log_2 5)^2  \) come richiede il teorema.

Passo 3: Controllo se \( n \) ha fattori primi \( p \leq r \)

Il numero \( 5 \) non ha fattori primi minori o uguali a \( 3 \).

Nota. Se il numero fosse composto, ad esempio \( n = 6 \), avrei scoperto che è divisibile per 2 e per 3 e avrei dovuto fermarmi a questo punto.

Passo 4: Controllo l'uguaglianza polinomiale

Devo verificare che la seguente condizione sia valida per ogni \( a = 1, \dots, \lfloor 2 \sqrt{\varphi(r)} \log_2 n \rfloor \).

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

Dove  \( \varphi(r) \) è la funzione di Eulero di \( r \), che conta quanti interi positivi minori di \( r \) sono coprimi con \( r \), mentre \( \log_2 n \) è il logaritmo in base 2 di \( n \).

In questo caso $ 2 \sqrt{\varphi(r)} \log_2 n \rfloor \approx 6 $.

Spiegazione. ci sono due numeri coprimi con $ r = 3 $ quindi la funzione di Eulero è $ \varphi(r)=2 $  e $ \log_2 5 \approx 2.32 $ \[2 \sqrt{\varphi(3)} \log_2 5\] \[2 \sqrt{2} \cdot 2.32 \] Poiché \( \sqrt{2} \approx 1.414 \), ottengo: \[ 2 \times 1.414 \times 2.32 \approx 6.56 \] Pertanto, per \( r = 3 \) e \( n = 5 \), il valore di \( 2 \sqrt{\varphi(r)} \log_2 n \) è circa 6.56 ovvero 6.

Devo verificare se vale la condizione $ (x + a)^n \equiv x^n + a \pmod{(x^r - 1, n)} $ per ogni \( a = 1, \dots, 6 \) sapendo che $ n = 5 $ e $ r = 3 $.

$$ (x + a)^5 \equiv x^5 + a \pmod{(x^3 - 1, 5)} $$

Faccio un test semplice con \( a = 1 \):

$$ (x + 1)^5 \equiv x^5 + 1 \pmod{(x^3 - 1, 5)} $$

Sapendo che la potenza del binomio è \( (x + 1)^5 = x^5 + 5x^4 + 10x^3 + 10x^2 + 5x + 1 \)

$$ x^5 + 5x^4 + 10x^3 + 10x^2 + 5x + 1 \equiv x^5 + 1 \pmod{(x^3 - 1, 5)} $$

Ora riduco modulo \( (x^3 - 1) \):

$$ x^3 \equiv 1 \pmod{(x^3 - 1, 5)} $$

Applico la proprietà delle potenze e riscrivi $x^5=x^3 \cdot x^2 $ e $ x^4 = x^4 \cdot x $.

Sapendo che $ x^3 \equiv 1 (x^3 - 1) $ posso sostituire $ x^5 = x^2 $ e $ x^4 = x $ nell'equivalenza

$$ x^5 + 5x^4 + 10x^3 + 10x^2 + 5x + 1 \equiv x^5 + 1 \pmod{(x^3 - 1, 5)} $$

$$ x^3x^2 + 5x^3x + 10x^3 + 10x^2 + 5x + 1 \equiv x^3x^2 + 1 \pmod{(x^3 - 1, 5)} $$

$$ 1 \cdot x^2 + 5x \cdot 1 + 10 \cdot 1 + 10x^2 + 5x + 1 \equiv 1 \cdot x^2 + 1 \pmod{(x^3 - 1, 5)} $$

$$ x^2 + 5x + 10 + 10x^2 + 5x + 1 \equiv x^2 + 1 \pmod{(x^3 - 1, 5)} $$

Essendo un'equivalenza nel modulo \( 5 \), i termini con coefficienti multipli di \( 5 \) spariscono perché hanno resto nullo:

$$ x^2 + 0 \cdot x + 0 + 0 \cdot x^2 + 0 \cdot x + 1 \equiv x^2 + 1 \pmod{(x^3 - 1, 5)} $$

$$ x^2 + 1 \equiv x^2 + 1 \pmod{(x^2 - 1, 5)} $$

In questo caso ottengo esattamente la forma richiesta dal test AKS ossia $ (x + a)^n \equiv x^n + a \pmod{(x^r - 1, n)} $.

Dal momento che tutte le condizioni del test AKS sono soddisfatte, posso concludere che \( 5 \) ha passato il test AKS per il numero intero $ a = 1 $.

Tuttavia, per sapere con certezza che $ n= 5 $ è un numero primo, devo ripetere il test AKS per ogni intero $ a $ da 1 a 6.

Se soddisfa il test AKS per tutti gli interi, allora è sicuramente un numero primo.

Nota. In altre parole, non basta verificare solo \( a = 1 \) per concludere che il numero \( n \) è primo.  Il test AKS richiede che la congruenza \[ (x + a)^n \equiv x^n + a \pmod{(x^r - 1, n)} \] sia valida per tutti gli interi \( a \) da \( 1 \) a \( \lfloor 2 \sqrt{\varphi(r)} \log_2 n \rfloor \). Se verificassi la congruenza solo per \( a = 1 \), potrei erroneamente concludere che alcuni numeri composti sono primi, perché ci sono numeri composti per cui la congruenza funziona per alcuni valori di \( a \), ma fallisce per altri.

E così via