- test di primalità deterministici: non vi sono elementi casuali nell’algoritmo, e l’output è “n è primo” se e solo se l’input n è un numero primo

Lezione del giorno 15 aprile 2009 Test di primalità.

Un test di primalità è un algoritmo tale che, dato in input un numero naturale n>1, produca un output “n è primo” oppure “n è composto” (definendo composto un naturale >1 non primo).

Si distinguono:

- test di primalità deterministici: non vi sono elementi casuali nell’algoritmo, e l’output è “n è primo” se e solo se l’input n è un numero primo

- test di primalità probabilistici: nell’algoritmo vi è la scelta casuale di alcuni elementi, e inoltre se l’input n è un numero primo allora l’output è sempre “n è primo” (si dice anche che “tutti i numeri primi superano il test”), ma se n è composto, l’output può essere sia “n è primo” sia “n è composto”, e la probabilità che l’output sia “n è primo” (pur essendo n composto) è maggiorata da una costante C<1, indipendente dall’input n e dagli elementi casuali. Se un input n>1 supera un test di primalità probabilistico un numero k di volte (con gli elementi casuali scelti ogni volta in modo indipendente), la probabilità che il numero n sia composto si può dunque rendere piccola a piacere (essa è maggiorata da C

, che è un numero piccolo a piacere se il numero di test k è abbastanza grande), quindi si può accettare che n sia effettivamente primo, con una bassa percentuale di errore.

Il primo test ingenuo di primalità è il test (deterministico) che verifica, per d=2,….,n-1, se esiste un d divisore non banale di n: se d esiste l’output è “n è composto”, se d non esiste l’output è “n è primo”:

1) in input il naturale n>1

2) per d=2,…..,n-1 si calcola il resto r della divisione di n per d: se per qualche d si ha r=0 (dunque d è divisore non banale di n) si si esce con output “n è composto”; altrimenti si esce con output “n è primo”.

L’algoritmo si implementa effettuando delle divisioni di n per numeri naturali d<n (sappiamo che ognuna di esse ha complessità polinomiale O(k

) se k=L(n) è la lunghezza binaria dell’input n), ma il numero di tali divisioni è <n<2

(perché n ha k cifre binarie) dunque il numero delle divisioni è di ordine esponenziale O(2

): si tratta in totale di un algoritmo di complessità esponenziale .

Questo test si può rendere più efficiente osservando che se esiste un divisore non banale del numero composto n, allora esiste certamente un divisore non banale di n che sia  n (infatti se per assurdo fosse n=bc con b,c> n , si avrebbe bc=n>( n )

=n, contraddizione).

Quindi nel test precedente si può limitare la ricerca ai valori d con 2d n : il numero di divisioni è in questo caso < n = n

<

, quindi è di ordine O

e anche tale algoritmo (sebbene più efficiente) ha complessità esponenziale.

Un altro test di primalità deterministico segue dal:

Teorema di Wilson.

Sia n> 1 un naturale . Allora: n è primo  (n-1)!-1 (mod n).

Dimostrazione:

(): Consideriamo il gruppo moltiplicativo Z

* . Se n è primo, n è coprimo con tutti i numeri 1,2,

…,n-1 (perché non sono multipli di n), dunque Z

* = {[1], [2], ….., [n-1]}.

Calcoliamo il prodotto di tutti gli elementi di tale gruppo:

[1][2] …..[n-1] = [12 …..(n-1)] = [(n-1)!].

In tale prodotto, sfruttando la proprietà commutativa, possiamo accoppiare ogni elemento [i] con il

suo inverso [i]

(nel caso in cui [i][i]

) ottenendo per ogni tale coppia il prodotto =[1]: al termine

di tale semplificazione il prodotto precedente si riduce a quello dei soli fattori [i] tali che [i]=[i]

,

cioè tali che [i]

=[i

]=[1].

Ma per un tale i si ha n(i

-1), n(i+1)(i-1), quindi (essendo n primo) n(i+1) oppure n(i-1), ossia i1 (mod n) oppure i-1 (mod n). Si conclude che:

[(n-1)!]=[1][-1]=[-1] , da cui la tesi.

(): Sia (n-1)!+1=kn, con k intero. Se per assurdo esistesse un divisore non banale d di n, con 1<d<n, tale d sarebbe divisore di 1=kn-(n-1)! (perché d è uno dei fattori del prodotto (n-1)!) contraddizione perché d>1.

Nota: la condizione (n-1)!-1 (mod n) del Teorema di Wilson equivale a (n-1)!modn=(n-1) (in quanto -1(n-1) (mod n)).

Il Teorema di Wilson permette di costruire un test di primalità deterministico:

1) in input il naturale n>1

2) si costruisce la la successione y

,y

y

ponendo y

=1, e per i>1 y

=(iy

)modn, ottenendo alla fine il valore y

=(n-1)!modn: se y

=(n-1) si esce con output “n è primo”; altrimenti si esce con output “n è composto”.

Nel passo 2), il calcolo di (n-1)!modn comporta l’esecuzione di operazioni (prodotti e riduzioni modulo n) in numero <n< ₂

dunque in numero di ordine O(2

) se k=L(n), ed anche questo algoritmo ha complessità esponenziale.

Esporremo in seguito l’unico test di primalità di complessità polinomiale attualmente esistente: il test AKS (Agrawal, Kayal, Safena 2002).

Esaminiamo ora alcuni test di primalità probabilistici.

Il primo è il cosiddetto test di Fermat (basato sul Piccolo Teorema di Fermat): in effetti esso non è un test probabilistico a tutti gli effetti, perché vedremo che la probabilità che un numero composto superi (erroneamente) il test è maggiorata da una costante, ma ciò avviene per tutti i i numeri composti tranne che per particolari valori dell’input (i cosiddetti numeri di Carmichael).

I passi dell’algoritmo sono:

1) in input il naturale n>1

2) si sceglie casualmente un intero a con 1an-1 (detto base) 3) si calcola d=mcd(a,n); se d>1 si esce con output ”n è composto”

4) se d=1 si calcola la riduzione x=a

modn e se x1 si esce con output ”n è composto”; altrimenti si esce con output “n è primo”

Osserviamo prima di tutto che ogni input n primo supera il test: se 1an-1, certamente a non è multiplo di n e quindi nel passo 3) si ha d=1; per il Piccolo Teorema di Fermat si ha allora, nel passo 4), x=1 e quindi nel passo 4) si esce con output “n è primo”.

Osserviamo ora che il test ha complessità polinomiale O(k

) se k=L(n): infatti il passo 2) si effettua con l’algoritmo Euclideo, il passo 3) con l’algoritmo dell’esponenziazione modulare.

Un numero composto supera il test quando: nel passo 3) si ha d=mcd(a,n)=1 (ossia se la base casuale a è un numero coprimo con n) e nel passo 4) si ha x=a

modn=1.

Un input composto n che superi il test di Fermat relativamente alla scelta della base a è detto pseudoprimo nella base a (perché n “finge” di essere primo, superando il test per quella scelta di a): per quanto osservato sopra ciò equivale ad affermare che:

mcd(a,n)=1, a

modn=1 (con 1an-1) Esempio.

Sia n=341. Sottoponiamo n al test di Fermat con la base a=2. E’ facile verificare che mcd(341,2)=1.

Inoltre 2

mod341=1 (come già calcolato nell’esempio di applicazione dell’esponenziazione modulare). Dunque n=341 é pseudoprimo nella base a=2, poiché supera il test per tale scelta di a.

Proviamo il test con la base 3 (si ha mcd(341,3)=1): analogamente a quanto fatto nel caso a=2, con l’esponenziazione modulare si ha

y

= (1

3

) mod341=3 ;y

= (3

3

) mod341=9 ;y

= (9

3

) mod341=243;

y

= (243

3

) mod341=56 ;y

= (56

3

) mod341=201 ;y

= (201

3

) mod341=163 ;

y

= (163

3

) mod341=254 ;y

= (254

3

) mod341=67 ;y

= (67

3

) mod341=56=2

mod341 Poiché 2

mod3411, n=341 non supera il test nella base a=3, dunque é composto: in effetti 341=1131 .

Calcoliamo un maggiorante per la probabilità che un numero composto n superi il test di Fermat.

Il numero dei valori possibili per la scelta dell’elemento casuale a nel test è (n-1); vediamo come possiamo valutare il numero dei valori a per i quali il test è superato, cioè il numero delle possibili basi in cui n è pseudoprimo:

Teorema.

Sia n un numero naturale, e supponiamo che esista almeno un naturale b, con 1bn-1, mcd(b,n)=1, tale che b

modn1. Allora il numero dei naturali a tali che 1an-1, mcd(a,n)=1, a

modn=1 (cioè il numero delle basi in cui n è pseudoprimo) è (n)/2.

Di questo Teorema daremo in seguito la dimostrazione: prima osserviamo alcune conseguenze di tale Teorema.

Se n è un naturale composto, e se soddisfa le ipotesi del Teorema precedente, la probabilità che n superi il test di Fermat (per una scelta casuale della base a) è 1/2. Infatti il numero dei valori a (compresi fra 1 ed n-1) per cui n supera il test è (n)/2(n-1)/2, e la probabilità che a sia scelto casualmente fra questi valori è allora [(n-1)/2]/(n-1)=1/2.

Ripetendo k volte il test, ogni volta con una scelta casuale indipendente del valore della base a, la probabilità che un numero composto (soddisfacente le ipotesi del Teorema) superi tutte le volte il test di Fermat è 1/2

, quindi tale probabilità può essere resa piccola a piacere (per k sufficientemente grande).

Per esempio se k=100 tale probabilità è 1/2

1/10

.

Dunque se l’input n supera k volte il test di Fermat, con k abbastanza grande, possiamo affermare che n è primo, con una probabilità di errore molto bassa, eccetto che nel caso in cui n sia un numero composto che non soddisfa le ipotesi del Teorema precedente.

Problema: cosa avviene se il numero naturale n composto non soddisfa le ipotesi del Teorema precedente ? Esistono tali numeri n ?

Per un naturale n composto che non soddisfa le ipotesi del Teorema precedente si ha che non esiste nessun naturale b, con 1bn-1, mcd(b,n)=1, tale che b

modn1, dunque per ogni intero a tale che 1an-1, mcd(a,n)=1, si ha sempre a

modn=1. Quindi n è pseudoprimo in tutte le basi a tali che 1an-1, mcd(a,n)=1, che sono in numero di (n).

Per un tale n, la probabilità che n superi il test è (n)/(n-1) , e se usiamo la formula per calcolare

(n) conoscendo la scomposizione di n in potenze di fattori primi distinti p

,p

,…,p

:

n = p ₁ ^k

p ₂ ^k

....p _r ^k

; (n) = p ₁ ^k

^{ 1} (p ₁ - 1)p ₂ ^k

^{ 1} (p ₂ - 1)....p _r ^k

^{ 1} (p _r - 1) oppure equivalentemente:

(n) = n[(p

-1)/p

][(p

-1)/p

]…..[(p

-1)/p

] = n(1-1/p

)(1-1/p

)...(1-1/p

) otteniamo che tale probabilità è :

(n)/(n-1)  (n)/n =(1-1/p

)(1-1/p

)...(1-1/p

)

Se i fattori primi p

sono molto grandi, tale probabilità è molto vicina ad 1, quindi molto alta:

sottoponendo un tale input n al test di Fermat anche un numero molto grande di volte, è molto probabile che superi sempre il test.

Un numero naturale composto n che soddisfa la condizione:

per ogni intero a tale che 1an-1, mcd(a,n)=1, si ha sempre a

modn=1 è detto numero di Carmichael.

Esempio: Un numero di Carmichael molto grande è n=225.593.397.919 (si dimostra che è di Carmichael con il Teorema di Korselt che vedremo in seguito): la sua decomposizione in fattori primi è 2207661915443 . Per tale n la probabilità che n superi il test di Fermat è circa:

(1-1/2207)(1-1/6619)(1-1/15443)  0,99933 (molto vicina al 100%).