Test di primalità

Un test di primalità è un algoritmo per sapere se un intero è primo .

Metodo ingenuo

Il test più semplice è il seguente: per verificare N , controlliamo se è divisibile per uno degli interi compresi in senso lato tra 2 e N-1. Se la risposta è negativa, allora N è primo, altrimenti è composto.

Diverse modifiche migliorano le prestazioni di questo algoritmo:

è sufficiente testare tutti i numeri da 2 a solo, poiché se allora o o , ${\ sqrt {N}}$ $N = pq$ $p \ leq {\ sqrt {N}}$ $q \ leq {\ sqrt {N}}$
possiamo ancora dimezzare il lavoro testando solo i numeri dispari, una volta fallita la divisibilità per due,
in generale, possiamo calcolare in anticipo una lista di numeri primi minori di un limite (con un crivello di Eratostene ), per testare solo questi. Ad esempio, per testare i numeri inferiori a 39.000, è sufficiente testare i numeri primi inferiori a 198 (perché 198 2 > 39.000), cioè 45 numeri primi.

Test probabilistici

I test probabilistici non sono test di primalità in senso stretto (fanno parte dei metodi Monte-Carlo ): non consentono di garantire con certezza che un numero sia primo, ma il loro basso costo in tempo di calcolo li rende ottimi candidati per le applicazioni in crittografia spesso dipendono in modo critico da grandi numeri primi e accettano un tasso di errore a condizione che sia molto basso: sono chiamati numeri primi industriali (in) . L'idea di base di testare la primalità di un numero N è la seguente:

Disegna a caso un numero a .
Verifica una certa identità che coinvolge a oltre al numero N dato e che è vera se il numero N è primo. Se l'identità non è soddisfatta, allora N è necessariamente composto e il test si interrompe; in questo caso, a è chiamato testimone di prova.
Ripetere il passaggio 1 fino a raggiungere il margine di incertezza desiderato.

Dopo diverse iterazioni, se N non viene riconosciuto come numero composto , viene dichiarato probabilmente primo .

Dato un test, potrebbero esserci alcuni numeri composti che sono dichiarati "probabilmente primi" indipendentemente dal testimone. Tali numeri resistenti al test sono chiamati numeri pseudoprimi per questo test.

Il test di primalità probabilistico più semplice è il test di primalità di Fermat . Il test di primalità Miller-Rabin e il test di primalità Solovay-Strassen sono varianti più sofisticate che rilevano tutti i composti. Uno di questi test viene utilizzato quando è richiesto un numero primo dopo un calcolo il più breve possibile accettando un piccolo margine di dubbio, ad esempio nella crittografia RSA o nel protocollo di scambio delle chiavi Diffie-Hellman .

Test deterministici rapidi

Il test ciclotomico è un test di primalità deterministico; dimostriamo che il suo tempo di esecuzione è O ( n clog (log (n)) ), dove n è il numero di cifre di N e c è una costante indipendente da n . La sua complessità è inferiore al polinomio .

Si può dimostrare che il test di primalità della curva ellittica esegue O ( n 6 ), ma solo utilizzando alcune congetture della teoria analitica dei numeri non ancora dimostrate ma ampiamente accettate come vere. In pratica, questo test è più lento del test ciclotomico per i numeri con più di 10.000 cifre.

L'implementazione di questi due metodi è piuttosto difficile, e il rischio di errore dovuto all'implementazione è quindi superiore a quello dei metodi probabilistici sopra menzionati.

Se l' ipotesi di Riemann generalizzata è vera, il test di Miller-Rabin può essere convertito in una versione deterministica con un tempo di esecuzione Õ ( n 4 ). In pratica, questo algoritmo è più lento dei due precedenti.

Nel 2002, Manindra Agrawal, Neeraj Kayal e Nitin Saxena hanno descritto un test di primalità deterministico (il test di primalità AKS ) che viene eseguito a Õ ( n 12 ). Inoltre, secondo una congettura (non dimostrata, quindi, ma ampiamente riconosciuta come vera), sarebbe eseguita in Õ ( n 6 ). È quindi il primo test di primalità deterministico del tempo di esecuzione polinomiale . In pratica, questo algoritmo è più lento degli altri metodi.

Metodi basati sulla teoria dei numeri

La teoria dei numeri fornisce metodi; un buon esempio è il test di Lucas-Lehmer per verificare se un numero è primo. Questo test è legato al fatto che l' ordine moltiplicativo di un certo numero a modulo n è n-1 per un numero primo n quando a è una radice primitiva . Se possiamo dimostrare che a è una radice primitiva per n , possiamo dimostrare che n è primo.

Teoria della complessità

Nella teoria della complessità , il problema PRIMES è il problema della decisione di appartenere al linguaggio formale che contiene i numeri primi, scritti in binario:

BONUS = {10, 11, 101, 111, 1011, ...}

dove 10, 11, 101, 111, 1011 ... sono le scritture binarie dei numeri primi 2, 3, 5, 7, 11, ecc.

PRIMES è in co-NP : infatti, i suoi COMPOSITI complementari, cioè la decisione di appartenere all'insieme dei numeri non primi, è in NP , perché possiamo decidere i COMPOSITI in tempo polinomiale per il numero di cifre del numero da testare , su una macchina di Turing non deterministica , indovinando un fattore.

Nel 1975, Vaughan Pratt (en) ha dimostrato che esiste un certificato per PREMIUM verificabile in tempo polinomiale. Quindi, PRIMES è anche in NP e quindi in NP ∩ coNP .

Gli algoritmi Solovay – Strassen e Miller – Rabin mostrano che PRIMES è in coRP . Nel 1992, l'algoritmo Adleman-Huang mostra che PRIMES è in RP . Quindi, PRIMES è in ZPP = RP ∩ coRP .

Il test di primalità Adleman – Pomerance – Rumely (en) del 1983 mostra che PRIMES è in QP (tempo quasi-polinomiale), una classe che non è stata dimostrata essere paragonabile a una delle classi sopra menzionate.

Il test di primalità AKS è un algoritmo di tempo polinomiale e infine mostra che PREMIUMS è in P . Ma PRIMES non ha dimostrato di essere P-completo . Non sappiamo se PRIMES sia in NC o in LOGSPACE per esempio. Ma sappiamo che PRIMES non è in AC 0 .

Note e riferimenti

Vaughan Pratt. "Ogni primo ha un certificato succinto". SIAM Journal on Computing , vol. 4, pagg. 214-220. 1975. Citazioni , testo completo .
Michael O Rabin , “ Algoritmo probabilistico per testare la primalità ”, Journal of Number Theory , vol. 12, n ° 1,1 ° febbraio 1980, pag. 128-138 ( ISSN 0022-314X , DOI 10.1016 / 0022-314X (80) 90084-0 , lettura online , accesso 9 luglio 2019 ).
Adelman e Huang 1992 .
Leonard M. Adleman , Carl Pomerance e Robert S. Rumely , “ Sulla distinzione dei numeri primi dai numeri compositi ”, Annals of Mathematics , vol. 117, n . 1,1983, pag. 173-206 ( ISSN 0003-486X , DOI 10.2307/2006975 , lettura online , accesso 9 luglio 2019 ).
“ QP sullo zoo della complessità ” .
(it-IT) “ PRIMES è in P | Annals of Mathematics ” (consultato il 9 luglio 2019 ) .
Allender, Saks e Shparlinski 2001 .

Appendici

Bibliografia

[Adelman e Huang 1992] (en) Leonard M. Adelman e Ming-Deh Huang , Test di primalità e varietà abeliane su campo finito , Berlino, Springer-Verlag , coll. "Appunti di matematica" ( n o 1512),aprile 1992, 142 pag. ( ISBN 3-540-55308-8 , OCLC 25933224 , avviso BnF n o FRBNF37383187 ).
[Allender, Saks e Shparlinski 2001] (en) Eric Allender, Michael Saks e Igor Shparlinski, " Un limite inferiore per la primalità " , Journal of Computer and System Sciences , vol. 62 “Numero speciale sulla quattordicesima conferenza annuale IEE sulla complessità computazionale” , n o 2,marzo 2001, pag. 356-366 ( DOI 10.1006 / jcss.2000.1725 ).
[Demazure 1997] Michel Demazure , Corso di algebra. Primalità, divisibilità, codici , Cassini,1997.Questo libro contiene molti algoritmi scritti in Caml Light .
[Demazure 2008] Michel Demazure , Corso di algebra. Primalità, divisibilità, codici , Cassini,2008.

Questo libro contiene molti algoritmi scritti in Ruby . La presentazione di questa edizione è diversa dalla precedente ed è rivolta ad un pubblico più ampio.

link esterno

(it) I fatti principali: da Euclide ad AKS , di Scott Aaronson