Test di primalità

Da Wikipedia, l'enciclopedia libera.

Questa voce di matematica è solo un abbozzo: contribuisci a migliorarla secondo le convenzioni di Wikipedia.

Un test di primalità è un algoritmo che, applicato ad un numero intero, ha lo scopo di determinare se esso è primo.

Si noti la differenza tra test di primalità e fattorizzazione di un numero intero: se da un lato la scomposizione in fattori primi di un numero non è un'operazione veloce (e proprio questa sua caratteristica viene sfruttata per la creazione di codici cifrati), più rapido è verificare se un numero sia primo o meno. Con la significativa eccezione del metodo delle curve ellittiche (noto anche come ECPP) che è deterministico, 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.

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 un qualunque m allora n è composto, altrimenti è primo.

Nel corso del tempo sono stati elaborati varie tipologie di test di primalità, tra cui i più semplici sono il test di Fermat, il test di Wilson, il test di Lucas - Lehmer ed il test di Miller - Rabin. Nel 1992 Adleman e Huang, modificando l'algoritmo di Goldwasser - Kilian, mostrarono come il problema della verifica di primalità (solitamente detta PRIMES, in inglese) appartenga alla classe di complessità RP. Poiché nel 1977 Solovay e Strassen avevano mostrato che tale verifica appartiene anche alla classe co-RP, il test di Adleman e Huang mostrò che PRIMES appartiene alla 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 (l o g (N) 12)$ , che si riduce a $O (l o g (N) 6)$ se vale la congettura di Sophie Germain.

Dal 2002 l'algoritmo è stato migliorato vaire volte in passi successivi, e sembra essere stato trovato un algoritmo ibrido di complessità $\tilde O(log(N)^{4})$ ^[1]. 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.