Test di primalità (probabilistico) di Rabin-Miller Ricordiamo i passi dell’algoritmo del test di Rabin-Miller:

Matematica Discreta II

Lezione del giorno 7 novembre 2007

Test di primalità (probabilistico) di Rabin-Miller Ricordiamo i passi dell’algoritmo del test di Rabin-Miller:

1) in input il naturale n>1 dispari

2) si calcola la massima potenza 2

di base 2 ed esponente t>0 tale che 2

sia divisore del numero pari n-1, e si scrive: n-1=2

k, con k>0 naturale dispari (in questo passo si effettuano t divisioni per 2 fino ad ottenere un quoziente dispari)

3) si sceglie casualmente un intero a con 2an-1 (detto base)

4) si calcolano (con l’algoritmo dell’esponenziazione modulare) le riduzioni delle t potenze di base a ed esponente k, 2

k, 2

k, ….. , 2

k:

modn per j=0,1,….,t-1

5) se è verificata almeno una delle seguenti condizioni:

a

mod1 (mod n) oppure

modn = n-1 per qualche j=0,1,….,t-1 si esce con output ”n è primo”, altrimenti si esce con output “n non è primo”

Verifichiamo prima di tutto che un input n primo (dispari) supera sempre il test correttamente con output ”n è primo”.

Utilizzeremo la proprietà seguente: se n è primo e se x è un naturale tale che x

1 (mod n) , allora x1 (mod n) (infatti da x

1 (mod n) segue n(x

-1), n(x-1)(x+1), n(x-1) oppure n(x+1)).

Supponiamo dunque l’input n primo (dispari) e per assurdo supponiamo non verificata nessuna delle condizioni del passo 5); essendo la base a non multiplo di n (perché a<n), per il Piccolo Teorema di Fermat si ha:

a

=

=

1 (mod n)

e per quanto detto sopra si ha

1 (mod n); ma allora (non essendo verificata la condizione del passo 5) per j=t-1) si può escludere che sia

n-1-1 (mod n), e dedurre che si ha

1 (mod n). Di nuovo allora analogamente

=

1 (mod n),

1 (mod n),

1 (mod n) ((non essendo verificata la condizione del passo 5) per j=t-2) e così via procedendo a ritroso, fino ad arrivare ad

=

1, contraddizione (è una fra le condizioni del passo 5)).

Esaminiamo poi la complessità dell’algoritmo.

Sia s il numero di cifre binarie (taglia) dell’input n. Quindi 2

n<2

.

Nel passo 2), per rappresentare n-1 nella forma n-1=2

k, con k>0 naturale dispari, si tratta di effettuare t successive divisioni per 2 (fermandosi quando il quoziente è dispari): il numero t di tali divisioni è < s (perché 2

>n>n-1=2

k2

).

Nel passo 5) si tratta di calcolare (come già notato) le riduzioni modulo n delle t<s potenze:

dove j=0,1,….,t-1

e si può utilizzare l’esponenziazione modulare, che ha complessità polinomiale (notare anche che si possono semplificare i calcoli osservando che ognuna di tali t potenze è il quadrato della precedente, quindi dal calcolo della riduzione modulo n della prima a

si possono ricavare facilmente le riduzioni delle successive, quadrando ripetutamente).

Nel test di Rabin-Miller, se un input n (dispari) non supera il test, cioè se si esce con output “n non è primo”, si può essere certi che n in effetti non sia primo.

Ma nello stesso test, che non è deterministico, può avvenire che un input n non primo (dispari)

superi egualmente il test con output “n è primo”.

Esempio.

Consideriamo l’input non primo n=561=31117, e scegliamo come base a=2.

Si ha:

n-1=560=2

k dove t=4, k=35; le potenze da studiare sono 2

,2

=2

, 2

=2

, 2

=2

, con le seguenti riduzioni modulo 561:

2

mod561=263

2

mod561=(263)

mod561=166 2

mod561=(166)

mod561=67 2

mod561=(67)

mod561=67=1

Non è quindi verificata nessuna delle condizioni del passo 5), e il numero n=561 non supera il test di Rabin-Miller nella base a=2, rivelandosi correttamente non primo.

Consideriamo ora l’input n=2047, e scegliamo sempre come base a=2.

Si ha:

n-1=2046=2

k dove t=1, k=1023; l’unica potenza da studiare é 2

, con la seguente riduzione modulo 2047:

2

mod2047=1

E’ quindi verificata una delle condizioni del passo 5), e il numero n=2047 supera il test di Rabin- Miller nella base a=2 con output “n è primo”: eppure ciò non è corretto in quanto 2047=2389 non è primo.

Per concludere in modo definitivo che il test di Rabin-Miller sia un test di primalità probabilistico, dobbiamo calcolare un maggiorante per la probabilità che un input n composto (dispari) superi il test per una scelta casuale della base a.

In effetti storicamente Miller (1977) implementò per primo il test, ma avendo come scopo la costruzione di un test di primalità deterministico di complessità polinomiale: aveva infatti congetturato che se n è un input composto (dispari) con s cifre binarie allora esiste una base a con 2a2s

in cui n non supera il test; se tale congettura fosse vera (ma nessuno ha trovato una dimostrazione di ciò) il test diventerebbe deterministico, perché non si dovrebbe scegliere casualmente la base a, ma farle assumere tutti i valori interi nell’intervallo [2, 2s

] e se il test è sempre superato concludere con certezza che n è primo (il numero delle basi a su cui effettuare il test è <2s

, quindi la complessità è polinomiale).

Solo in seguito Rabin (1980) ebbe l’idea di utilizzare lo stesso test ma come test di primalità probabilistico, e dimostrò che un input non primo supera il test per un numero di basi che è non superiore ad 1/4 del numero totale di basi possibili, dunque la probabilità che un numero composto superi il test in una base casuale è 1/4: eseguendo il test y volte, con y scelte indipendenti della base casuale, la probabilità che un numero composto superi tutte le volte il test è 1/4

(valore che si può rendere piccolo a piacere).

Il problema del logaritmo discreto.

Ricordiamo che, dato un gruppo (moltiplicativo) A e fissato un elemento aA, si è definito il sottogruppo ciclico (a) generato da a come l’insieme di tutte le potenze di base a con esponente intero relativo.

Il gruppo A è detto gruppo ciclico se esiste almeno un elemento aA tale che (a)=A (quindi equivalentemente se esiste almeno un elemento aA tale che ogni elemento di A sia potenza di base a con esponente intero relativo). Un tale elemento aA è detto generatore del gruppo ciclico A.

Nel caso particolare di un gruppo finito A, ogni elemento aA è periodico, e sappiamo che, se k è il periodo di a, il sottogruppo ciclico (a) generato da a è formato dalle k potenze distinte:

(a)= {a

=1

, a

=a

a

,……, a

}.

Dunque, nel caso particolare di un gruppo finito A, è ovvio che esso è gruppo ciclico se e solo se esiste almeno un elemento aA di periodo uguale alla cardinalità n del gruppo A.

Esempio:

Nel gruppo moltiplicativo Z

*= {[1], [2], [3], [4]}= {1, 2, 3, 4} degli elementi invertibili di Z

(cioè delle classi di congruenza modulo 5 con rappresentante coprimo con 5), il periodo dell’elemento a=2 è 4 (in quanto 2

=2, 2

=4, 2

=8=3, 2

=16=1=neutro), dunque coincide con la cardinalità di Z

*.

Si conclude che Z

* è gruppo ciclico con generatore a=2: ognuno degli elementi del gruppo è potenza di base a=2.

Nel gruppo moltiplicativo Z

*= {1, 3, 5, 7} degli elementi invertibili di Z

si verifica che nessun elemento ha periodo uguale alla cardinalità 4 di Z

* (ogni elemento al quadrato dà il neutro), dunque Z

* non è gruppo ciclico.

Vedremo in seguito (Teorema di Gauss) per quali valori di n il gruppo moltiplicativo Z

* è ciclico.

Se il gruppo moltiplicativo Z

* è ciclico per un certo valore di n, chiameremo radice primitiva modulo n ogni intero a tale che 1an-1, e tale che [a] Z

* è un generatore del gruppo ciclico Z

* (quindi le radici primitive modulo n sono in numero uguale a quello dei generatori di Z

*). Per esempio, come visto sopra, 2 è una radice primitiva modulo 5, ma non esistono radici primitive modulo 8.

Calcoliamo il numero dei generatori di un gruppo ciclico finito:

Teorema.

Sia A un gruppo (moltiplicativo) ciclico finito di cardinalità n>1 e sia aA un generatore di A (dunque il periodo di a è n, e gli elementi distinti di A sono a

,a

,…,a

).

Allora:

un elemento x=a

A è generatore di G  1kn-1 e k,n sono coprimi.

In particolare il numero dei generatori di G è (n) (funzione di Eulero di n).

Dimostrazione:

Notiamo che a

=1

ha periodo 1n, dunque i generatori di A (cioè gli elementi di periodo n) sono da ricercare fra le potenze a

con 1kn-1.

(): Se x=a

è un generatore di A, ogni elemento di A è potenza di base x. In particolare si ha a=x

(con t intero), dunque a=a

, e poiché a ha periodo n si ottiene 1kt (mod n), 1=kt+nh (con h intero), concludendo che 1=mcd(k,n)

(): Supponiamo k,n coprimi. La tesi è che x=a

è generatore di A, cioè che ogni elemento yA è potenza di base x. Essendo 1=mcd(k,n). esistono interi c,d tali che 1=kc+nd, da cui:

a=a

=(a

)

(a

)

=x

(perché a

=1

)

Ma ogni elemento yA è potenza di base a, quindi y=a

=x

e si ha la tesi.

Gauss trovò tutti e soli i valori n>1 per i quali il gruppo moltiplicativo Z

* è ciclico (e per i quali dunque esiste qualche radice primitiva modulo n):

Teorema di Gauss.

Dato un naturale n>1:

il gruppo moltiplicativo Z

* è ciclico  n é uno dei seguenti valori: 2, 4, p

(con p primo dispari , k>0), 2p

(con p primo dispari , k>0).

Dimostreremo in seguito solo un caso particolare di tale teorema:

Teorema. Se n è un naturale primo, il gruppo moltiplicativo Z

* è ciclico .

Come conseguenza di tale teorema si ha che, se n è primo, esiste una radice primitiva a modulo n tale che Z

* = {1,2,…..,n-1}={a

,a

,a

,……,a

}, dunque, comunque fissato un intero y, con 2yn- 1, esiste un (unico) intero t con 1tn-2 per cui si abbia y=a

in Z

* (eguaglianza ovviamente da intendere modulo n). Tale intero t è detto logaritmo discreto di y in base a.

Problema del logaritmo discreto: dato un numero primo n, una radice primitiva a modulo n e un intero y, con 2yn-1, calcolare il logaritmo discreto di y in base a.

Attualmente non esiste una algoritmo di complessità bassa (polinomiale) che risolva tale problema:

quindi lo si può scegliere come base per sistemi crittografici a chiave pubblica, come vedremo.