n-1=2 st, con t numero naturale dispari (può anche essere t=1).

Matematica Discreta Lezione del 22/05/09

Test di primalità probabilistico di Rabin-Miller

Supponiamo che n sia un numero naturale >1 che dobbiamo sottoporre ad un test di primalità. Non è restrittivo supporre n dispari (se n è pari allora certamente non è primo tranne che nel caso n=2).

Dunque supponiamo n dispari, e perciò n-1 pari. Dividendo n-1 per 2 il maggior numero possibile di volte, possiamo rappresentare n-1 nella forma seguente:

n-1=2 ^s t, con t numero naturale dispari (può anche essere t=1).

Per esempio se n=113 allora n-1=112=2 ⁴ 7 (quindi s=4, t=7 in questo caso).

Consideriamo un qualunque numero naturale a tale che a<n e consideriamo le riduzioni modulo n delle potenze con base a ed esponente 2 ⁰ t, 2 ¹ t, 2 ² t,….., 2 ^s-1 t . Sono in totale s riduzioni modulo n:

_a ²

^t modn, _a ²

^t modn, _a ²

^t modn, ……., _a ²

^t modn

Per calcolare la prima riduzione si può usare l’algoritmo della esponenziazione modulare; è poi facile calcolare le rimanenti, notando che ognuno dei numeri di cui calcolare la riduzione è il quadrato del precedente.

Nell’esempio precedente (con n=113) essendo s=4, t=7 si tratterebbe di calcolare le seguenti 4 riduzioni modulo 113:

a ⁷ mod113, a ¹⁴ mod113, a ²⁸ mod113, a ⁵⁶ mod113

La prima a ⁷ mod113 si potrebbe calcolare con l’algoritmo della esponenziazione modulare; per calcolare ognuna delle seguenti, basterebbe elevare al quadrato la precedente e ridurre modulo n.

Dimostriamo ora un semplice risultato preliminare sui numeri primi:

Teorema. Se x è un numero naturale e se n è un numero primo tale che x ² 1 (mod n) allora:

xmodn =1 oppure xmodn = n-1 Dimostrazione:

Per ipotesi n è divisore di x ² -1=(x-1)(x+1) e per una proprietà dei numeri primi n è divisore di almeno uno dei fattori dunque n è divisore di (x-1) oppure n è divisore di (x+1).

Nel primo caso x1 (mod n) dunque xmodn =1 (ricordiamo che la riduzione xmodn è l’unico numero intero compreso fra 0,1,…,n-1 che è x (mod n)).

Nel secondo caso x -1 (mod n) ma n-1 -1 (mod n) (perché n è divisore di (n-1)-(-1)=n), e per la proprietà transitiva xn-1 (mod n) dunque xmodn = n-1.

Torniamo alle nostre riduzioni:

_a ²

^t modn, _a ²

^t modn, _a ²

^t modn, ……., _a ²

^t modn

dove n>1 è il numero naturale dispari di cui testare la primalità, ed a è un qualunque numero naturale <n.

Dimostriamo che se n è primo allora per tutti i valori di a naturali <n è vera almeno una delle seguenti condizioni:

1) La prima riduzione _a ²

^t modn è uguale ad 1

2) Almeno una delle riduzioni (compresa la prima) è uguale ad n-1

Infatti supponiamo per assurdo che non sia vera nessuna delle condizioni precedenti: essendo a<n, certamente a non è multiplo del numero primo n, e per il Piccolo Teorema di Fermat si ha:

a ^n-1  1 (mod n)

Ma n-1=2 ^s t dunque a ^n-1 = _a ²

^t =( _a ²

^t ) ² e per il Teorema precedente si ha:

_a ²

^t modn = 1 oppure _a ²

^t modn = n-1.

Poiché per assurdo abbiamo supposto falsa la condizione 2), l’unica possibilità è:

_a ²

^t modn = 1 quindi _a ²

^t  1 (mod n).

Ma si ha anche:

_a ²

^t =( _a ²

^t ) ² e di nuovo per il Teorema precedente si ha:

_a ²

^t modn = 1 oppure _a ²

^t modn = n-1.

Poiché per assurdo abbiamo supposto falsa la condizione 2), l’unica possibilità è:

_a ²

^t modn = 1 quindi _a ²

^t  1 (mod n).

Così procedendo a ritroso lungo le riduzioni, alla fine si arriva ad affermare che : _a ²

^t modn = 1 oppure _a ²

^t modn = n-1

Poiché per assurdo abbiamo supposto falsa la condizione 2), l’unica possibilità è:

a ²

^t modn = n-1

e si ottiene una contraddizione perché per assurdo abbiamo supposto falsa la condizione 1).

Riassumendo: se n è primo, per ogni numero naturale a<n è verificata almeno una fra le condizioni 1), 2).

Cosa avviene se n (dispari) non è primo ?

In questo caso per alcuni numeri naturali a<n è verificata almeno una delle condizioni 1), 2) e per altri non è verificata nessuna delle condizioni 1), 2).

Esempio.

Consideriamo il numero non primo n=221 (è il prodotto di 13 per 17). Si ha n-1 = 220 =2 ² 55 (quindi s=2, t=55 in questo caso).

Fissiamo il numero naturale a=5<n. Le 2 riduzioni da calcolare sono:

5 ⁵⁵ mod221, 5 ¹¹⁰ mod221

Utilizzando l’esponenziazione modulare per calcolare la prima riduzione si ottiene:

5 ⁵⁵ mod221=112 (Esercizio: sviluppare i calcoli……)

Per calcolare la seconda riduzione basta elevare al quadrato la prima e ridurre modulo n:

5 ¹¹⁰ mod221=112 ² mod221=168

Dunque per questo valore a=5 non è verificata nessuna delle condizioni 1),2).

Invece se fissiamo a=21 si ha:

21 ⁵⁵ mod221=200 (Esponenziazione modulare…..) 21 ¹¹⁰ mod221=200 ² mod221=220=n-1

ed è verificata la condizione 2).

Dunque per questo valore a=21 è verificata almeno una delle condizioni 1),2).

Rabin nel 1980 dimostrò però che se il numero naturale dispari n non è primo, allora il numero dei numeri naturali a<n che verificano almeno una delle condizioni 1),2) è al più 1/4 del numero di tutti i possibili numeri naturali <n (che è n-1).

In effetti, facendo alcuni esperimenti, si verifica che spesso il numero dei numeri naturali a<n che verificano almeno una delle condizioni 1),2) è molto minore di (n-1)/4: per esempio per n=221 (vedere esempi precedente) il risultato di Rabin garantisce che il numero dei numeri naturali a<221 che verificano almeno una delle condizioni 1),2) è 220/4=55, ma in effetti si è calcolato che tali valori sono solo 6 (quindi in numero molto minore del massimo previsto).

Possiamo in base alle considerazioni precedenti implementare il seguente test probabilistico (detto di Rabin-Miller):

- In input si immette il numero naturale dispari n>1 da testare - Si rappresenta n-1 nella forma :

n-1=2 ^s t, con t numero naturale dispari

- Si sceglie casualmente un numero naturale a<n e si calcolano le s riduzioni modulo n:

a ²

^t modn, a ²

^t modn, a ²

^t modn, ……., a ²

^t modn - Se è vera almeno una delle seguenti condizioni:

1) La prima riduzione _a ²

^t modn è uguale ad 1

2) Almeno una delle riduzioni (compresa la prima) è uguale ad n-1

il test esce con output “n è primo”; in caso contrario il test esce con output “n non è primo”.

Per quanto detto sopra, un input n primo supera sempre il test positivamente con output “n è primo”. Se dunque un input n non supera il test (cioè se l’output è “n non è primo”) si può essere certi che n effettivamente non è primo.

Ma se un input n supera il test positivamente con output “n è primo”, possiamo affermare che n è un numero primo con una probabilità di errore 1/4 (perché i valori di a che ci inducono in errore sono al più 1/4 di tutti quelli che possiamo scegliere random).

Se eseguiamo il test k volte sempre con lo stesso input, con k scelte indipendenti del valore casuale a, e se tutte le volte n supera il test positivamente con output “n è primo ” possiamo affermare che n è un numero primo con una probabilità di errore 1/4 ^k (se k è grande, tale probabilità di errore è piccolissima).

Come osservato nella lezione precedente, se, sottoponendo l’input x al test probabilistico di Rabin- Miller, per 20 volte l’output è sempre “x è primo” possiamo concludere che x è primo con una probabilità di errore che è (1/4) ²⁰ =1/(1.099.511.627.776) (quindi una probabilità di errore minore di 1 su 1000 miliardi).

Esaminiamo ora la complessità del test di Rabin-Miller. Sia k il numero di cifre dell’input n in base 2.

Per rappresentare n-1 nella forma n-1=2 ^s t, con t>0 naturale dispari, si tratta di effettuare delle successive divisioni per 2 (fermandosi quando il quoziente è dispari): ogni divisione per 2 non è una vera operazione aritmetica se i dati sono rappresentati in base 2 (si tratta solo di cancellare un bit 0 alla fine del numero).

L’unico vero calcolo da effettuare è quello delle s riduzioni modulo n:

a ²

^t modn dove j=0,1,….,s-1

la prima con l’esponenziazione modulare, le altre con il calcolo del quadrato del termine precedente ed una riduzione modulo n.

Sappiamo dalla teoria dell’esponenziazione modulare che il numero di operazioni da compiere per calcolare la prima riduzione a ^t modn è 3h dove h è il numero di cifre dell’esponente t in base 2:

poiché n-1=2 ^s t si ha t<n-1<n e dunque il numero h di cifre di t in base 2 è  del numero k di cifre di n in base 2, quindi il numero di operazioni da compiere per calcolare la prima riduzione a ^t modn è

3k. Ognuna delle seguenti (s-1) riduzioni coinvolge un quadrato (quindi un prodotto) e una riduzione modulo n (quindi una divisione) per un totale di 2(s-1) operazioni.

Ma è s<k (perché il numero n-1=2 ^s t è 2 ^s e quest’ultimo in base 2 è un numero con s+1 cifre, dunque n-1 ed anche n hanno un numero di cifre >s).

In totale il test di Rabin-Miller esegue un numero di operazioni <3k+2(k-1)<5k, ed ha dunque

complessità polinomiale rispetto al numero k di cifre dell’input n in base 2.