Il test di primalità AKS
------------------------
Nell’agosto 2002, tre ricercatori indiani, Manindra Agrawal, Neeraj Kayal e Nitin Saxena, pubblicarono un articolo in cui proponevano un test di primalità deterministico il cui tempo di esecuzione è paragonabile a quello di Rabin–Miller (vedi più sotto). Come per quest’ultimo, l’idea di fondo è un perfezionamento del piccolo teorema di Fermat. Più precisamente, studiando i coefficienti binomiali, si dimostra che se a è primo con p, allora p è primo se e solo se i due polinomi (X – a)*p e Xp – a, a coefficienti in ? / p?, sono uguali, cioè se (X – a)p = Xp – a (mod p*).
Un test basato su questa identità richiede di calcolare tutti i coefficienti del polinomio (X – a)*p, operazione che richiede un tempo proibitivo. Per rendere effettivo questo test, si valuta l’identità modulo il polinomio Xr – 1, ossia si verifica se (X – a)p = Xp – a (mod Xr – 1, p*).
Se p è primo, questa identità è vera per ogni coppia (a, r); purtroppo la reciproca è falsa. I tre ricercatori indiani mostrarono che, per opportuni valori di r, basta verificare l’identità precedente per un certo numero di valori di a per stabilire se p è primo oppure no.
-
Il test di primalità di Miller
------------------------------
In base al piccolo teorema di Fermat, un modo per verificare se un numero p è primo consiste nel controllare se *x p *–1 = 1 (mod p) per un valore di x fra 2, 3… p – 1. Questo test è facile da programmare e ha un tempo di esecuzione breve. Purtroppo non dà sempre il risultato corretto: se il test risponde «vero», non è certo che p sia primo. Per esempio, il numero intero 341 supera il test, pur essendo il prodotto di 11 per 31. Un modo per aggirare la difficoltà è studiare la probabilità di ottenere la risposta «vero» quando p non è primo. Questa probabilità è estremamente bassa: per un numero scelto a caso fra i venticinque miliardi più piccoli, la probabilità che la risposta sia «vero» benché p non sia primo è circa 2 × 10–5.
Un’idea semplice consiste allora nell’effettuare il test per più valori di x. A priori, così si riduce la probabilità di errore. Questa idea fu perfezionata da Michael Rabin (nato nel 1931) e Gary Miller (nato nel 1948) a partire dalla fattorizzazione del polinomio X *p *–1 – 1. Ne risulta un test del tipo precedente, applicato usando un numero intero x. Se lo si ripete per k valori primi di x, il test stabilisce se un numero è primo con un rischio di errore dell’ordine di 1 / 4*k. Questo test è a priori* probabilistico ma, per numeri «piccoli», è facile ricavarne un test deterministico.
