Test di primalità

Un test di primalità è un algoritmo che, applicato ad un numero intero, ha lo scopo di determinare se esso è primo. Non va confuso con un algoritmo di fattorizzazione, che invece ha lo scopo di determinare i fattori primi di un numero: quest'ultima operazione è infatti generalmente più lunga e complessa.

Con la significativa eccezione del metodo delle curve ellittiche (noto come ECPP) e dell'algoritmo AKS, i test di primalità più efficienti oggi utilizzati sono probabilistici, nel senso che danno una risposta certa solo quando rispondono NO (ossia quando dicono che il numero è composto) mentre nel caso di risposta SÌ assicurano soltanto un limite inferiore alla probabilità che il numero sia primo. L'errore dei test può essere però reso piccolo a piacere.

Alcuni test

Il test di primalità basilare, che si basa sulla definizione stessa di numero primo, è il seguente: dato un numero di input n, si verifichi se esiste un intero m compreso tra 2 e n − 1 tale da dividere n. Se n è divisibile per almeno un m allora n è composto, altrimenti è primo. Il limite n-1 può essere abbassato a ${\sqrt {n}}$, in quanto se tutti i fattori fossero maggiori di questo valore, il loro prodotto sarebbe necessariamente maggiore di n, il che è assurdo. In questo caso particolare, il test di primalità fornisce anche la fattorizzazione del numero.

A partire dal Seicento, sono stati ideati diversi altri algoritmi, tra cui il test di Fermat e il test di Wilson; altri sono stati invece creati per essere usati solamente su particolari classi di numeri: esempi sono il test di Lucas-Lehmer per i numeri di Mersenne, il test di Proth per i numeri nella forma k2ⁿ+1, dove k è dispari e minore di 2ⁿ. Il test di Miller-Rabin è invece probabilistico.

Attualmente il test di uso generale più usato è l'ECPP, basato sulle curve ellittiche.

Complessità computazionale

Il problema di verificare se un numero è primo (detto PRIMES) è di complessità P. Tale risultato è stato raggiunto nel 2002.

In precedenza, era stato provato nel 1977 da Solovay e Strassen che esso era nella classe di complessità co-RP; nel 1992 Adleman e Huang, modificando l'algoritmo di Goldwasser - Kilian, mostrarono che esso era nella classe RP, e di conseguenza nella classe ZPP, intersezione di RP e co-RP.

Nel 2002 Agrawal, Kayal e Saxena fornirono un algoritmo deterministico polinomiale per PRIMES, noto come algoritmo AKS, di complessità $O(log(N)^{12})$, che si riduce a $O(log(N)^{6})$ se vale la congettura di Sophie Germain.

L'algoritmo è stato migliorato varie volte in passi successivi, e sembra essere stato trovato un algoritmo ibrido di complessità ${\tilde {O}}(log(N)^{4})$. Ciononostante al momento attuale questo algoritmo non comporta significativi vantaggi rispetto ai ben noti metodi probabilistici, né implica alcunché sulla fattorizzazione di un numero (se non nel test di verifica di primalità), e quindi nella crittografia basata sui primi.

Collegamenti esterni

• Implementazione JAVA dell'algoritmo AKS., su angelusworld.com. URL consultato il 2 gennaio 2011 (archiviato dall'url originale il 7 luglio 2011).