Test di primalità

Sia P è l'insieme di numeri primi ed n un numero intero. Un numero primo per definizione è un numero divisibile solo per 1 e sè stesso.

Una tecnica, quindi, per verificare se n è primo è di dividerlo per ogni m numero intero dispari minore o uguale alla radice di n. Tale tecnica è una specializzazione del "crivello di Eratostene"; solo che tale metodo non è efficiente: esso richiede un numero di step pari a O(n^1/2).

Un test efficiente dovrebbe richiedere un numero di step polinomiale, legato al numero delle cifre di input. ovvero log10(n). Una proprietà questa che è quasi rispettata dal Piccolo Teorema di Fermat.

Difatti se p è un numero primo, allora per ogni a non divisibile per p si ottiene che a^(p-1) = 1 mod p. Per cui si cerca di testare p per vari valori di base a tali che gcd(a,p)=1, per almeno un centianio di basi a

Non sempre il test del Piccolo Teorema di Fermat è efficace, a volte è superato da numeri composti di Carmichael; tuttavia con vari accorgimenti è possibile realizzare un algoritmo che può evitare questo.

D'altra parte esistono molti altri test, Teoremi o dimostrazioni che prendono spunto dal Piccolo Teorema di Fermat o sono riconducili ad esso.

Oggi con l'AKS è noto che il problema della primalità è in P. L'AKS stesso è una generalizzazione del Piccolo Teorema di Fermat come algoritmo polinomiale sugli anelli su campi finiti.

Ad esempio una versione diversa del Piccolo Teorema di Fermat può essere:
(X+a)^n = (X^n+a) mod n.

Vediamo quali possono essere le idee di base, da usare, dove alcune delle quali hanno portato
all'AKS.

Lemma A
Sia a appartenente a Z, n appartenente a N, n minore di 2 e gcd(a,n)=1. Allora n è primo se e solo se
(X + a)^n = X^n + a (mod n)   (1)

Nel seguito indichiamo per semplicità col simbolo (n i) il coefficiente binomiale di Newton.

Dimostrazione del Lemma A
Per i maggiore di zero e i minore di n, il coefficiente di x^i in ((X+a)^n - (X^n+a)) è (n i) a^(n-i).
Se n è primo allora (n i) a^(n-i) = 0 mod n e quindi tutti i coefficienti sono nulli.

Difatti se n=3 e a=2 gcd(a,n)=1 se considero i maggiore di zero e i minore di n è lo stesso di dire che (n i) a^(n-i) = 0 mod n.

Supponiamo invece n composto. Sia q un numero primo che è fattore di n e sia q^k  non divisore di n.
Allora q^k non divide (n i) ed è coprimo con a^(n-q) e quindi il coefficiente di X^q non è 0 mod n. Di conseguenza (X+a)^n-(X^n+a) non è nullo.

Ad esempio n=6=2*3=q*3
se q=2 se k=2  q^2 non divide (n i).
se gcd(a,n)=1 es a=5 allora  gcd(a^n-q,q^k)=1 infatti gcd(5^4,2^2)=1.

Il Lemma A è già un buon test di primalità: dato un valore n trovare dei valori a che rispettano il Lemma allora n è primo. Il problema del Lemma è valutare tutti i coefficienti di Newton, quindi serveono un numero di step uguale a O(n).

Un modo per ridurre i calcoli è di valutare entrambi i membri della (1) e verificare se c'è l'uguaglianza oppure ancora meglio è valutare l'espressione:
 
(X + a)^n = X^n + a (mod X^r-1,n)   (2)

dove r è un numero intero piccolo e scelto opportunamente (con una caratterizzazione).

Il Lemma A comporta che tutti i primi n soddisfano la (2) per tutti i valori di a e r.

In verità alcuni composti potrebbero anch'essi soddisfare la (2) ma con una opportuna scelta di r questo si può evitare e quindi n è effettivamente un numero primo.

In questo caso la scelta di r e la valutazione degli a ci porta ad un tempo O(logn) ottenendo un algoritmo polinomiale deterministico per il test di primalità e quindi la primalità è da dichiarare un problema in P.

Se definiamo l'ordine r di a come or(a), esso rappresenta il più piccolo valore k tale che a^k = 1 mod r.
Se definiamo, poi, la funzione totiente di Eulero ph(r) essa è il numero dei numeri minori di r e primi relativamente a r. Si dimostra che or(a) è un divisore di ph(r) per ogni a e per gcd(a,r)=1.

Allora in tal caso Manindra Agrawal, Neraji Kayal e Nitin Saxena hanno dimostrato l'AKS dicendo che:
Input: integer n > 1.
1. If (n = ab for a 2 N and b > 1), output COMPOSITE.
2. Find the smallest r such that or(n) > log2 n.
3. If 1 < (a, n) < n for some a less or equal than r, output COMPOSITE.
4. If n less or equal than r, output PRIME.
5. For a = 1 to sqrt(ph(r)) log n  do
if ((X + a)^n  is distinct from X^n + a (mod Xr − 1, n)), output COMPOSITE;
6. Output PRIME;

Famoso è il loro articolo "PRIMES IN P" il cui abstract dice semplicemente: "We present an unconditional deterministic polynomial-time algorithm that determines whether an input number is prime or composite".

Alla prossima