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 , 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 k2n+1, dove k è dispari e minore di 2n. 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à , che si riduce a 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à [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.
Note
- ^ (EN) Qi Cheng, Primality proving via one round in ECPP and one iteratione in AKS (PDF), su cs.ou.edu. URL consultato l'11.03.2008.
Collegamenti esterni
- Implementazione JAVA dell'algoritmo AKS., su angelusworld.com. URL consultato il 2 gennaio 2011 (archiviato dall'url originale il 7 luglio 2011).
V · D · M | ||
---|---|---|
Numeri più usati | Naturali · Interi · Pari e dispari | |
Principi generali | Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza | |
Successioni di interi | Fattoriale · Successione di Fibonacci · Numero di Catalan · Numero di Perrin · Numero di Eulero · Successione di Mian-Chowla · Successione di Thue-Morse | |
Caratteristiche dei numeri primi | Numero primo · Lemma di Euclide · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Test di primalità · Teorema fondamentale dell'aritmetica · Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Teorema dei numeri primi | |
Funzioni aritmetiche | Funzione moltiplicativa · Funzione additiva · Convoluzione di Dirichlet · Funzione φ di Eulero · Funzione di Möbius · Funzione tau sui positivi · Funzione sigma · Funzione di Liouville · Funzione di Mertens | |
Aritmetica modulare | Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Criteri di divisibilità · Teorema di Fermat sulle somme di due quadrati · Teorema di Wilson · Legge di reciprocità quadratica | |
Congetture | Congettura di Goldbach · Congettura di Polignac · Congettura abc · Congettura dei numeri primi gemelli · Congettura di Legendre · Nuova congettura di Mersenne · Congettura di Collatz · Ipotesi di Riemann | |
Altro | Problema di Waring | |
Principali teorici | Fibonacci · Fermat · Gauss · Eulero · Legendre · Riemann · Dirichlet | |
Discipline connesse | Teoria algebrica dei numeri · Teoria analitica dei numeri · Crittografia · Teoria computazionale dei numeri |