Teoria dei numeri e Crittografia: lezione del 23 novembre 2011 Lemma. Dato un intero n>1: l’anello commutativo con unità Z

Teoria dei numeri e Crittografia: lezione del 23 novembre 2011 Lemma.

Dato un intero n>1:

l’anello commutativo con unità Z

è campo Û n è primo Dimostrazione:

Ricordiamo che in Z

una classe [a]¹[0] ha inverso se e solo se a,n sono coprimi.

(Þ) Se per assurdo n non fosse primo, esisterebbe un divisore non banale d di n con 1<d<n, e la classe [d]¹[0] non avrebbe inverso (essendo mcd(d,n)=d>1) contro l’ipotesi che Z

è campo

(Ü) Le classi ¹[0] in Z

sono [1],[2],..,[n-1] ed essendo n coprimo con tutti i numeri 1,2,…,n-1 (perché essi non sono multipli di n ed n è primo) tutte queste classi hanno inverso, quindi Z

è campo.

Come conseguenza dei risultati precedenti:

Teorema di Gauss (il caso n primo).

Se n è primo, il gruppo moltiplicativo Z

* è ciclico (quindi esiste qualche radice primitiva modulo n).

Dimostrazione:

Segue immediatamente dall’ultimo Teorema della lezione precedente e dal Lemma.

Nota: La dimostrazione dell’esistenza di un generatore per il gruppo moltiplicativo A* di un campo finito A non è costruttiva, dunque in particolare non fornisce un algoritmo per calcolare una radice primitiva modulo n, quando n è primo: a tutt’oggi non è noto nessun algoritmo di complessità non più che polinomiale che risolva il problema.

In ogni caso, se n è primo, sappiamo da risultati precedenti che se a è una radice primitiva modulo n, allora tutte e sole le radici primitive modulo n sono le riduzioni a

modn con 1 i (n)-1=n-2, tali che i, (n) sono coprimi, e il numero di tali radici primitive modulo n è ()=(n-1).

Esempio. Per esempio se n=11, una radice primitiva modulo 11 è a=2 (il periodo di [2] in Z

* è un divisore di (11)=10, ma non è 5 perché [2

]=[32]=[10]¹[1], dunque tale periodo è 10=(11)). Il numero di radici primitive modulo 11 è ((11))=(10)=4: esse sono le riduzioni 2

mod11, dove 1 i (11)-1=9, con i,10 coprimi, ossia i=1,3,7,9 (sono esattamente 2, 8, 7, 5).

Teorema di Gauss (il caso del quadrato di un numero primo).

Se n=p

con p primo, il gruppo moltiplicativo Z

* è ciclico (quindi esiste qualche radice primitiva modulo n).

Dimostrazione.

Poiché tratteremo di classi di congruenza con diversi moduli, conveniamo di indicare, per un generico modulo m>1, la classe di congruenza rappresentata dall’intero a modulo m con [a]

. Sia a una radice primitiva modulo p (che esiste per il risultato precedente): (p)=(p-1) è il periodo di [a]

nel gruppo moltiplicativo Z

* quindi (p-1) è il minimo esponente positivo tale [a]

=[1]

cioè tale che a

1 (mod p) . Vi sono 2 casi possibili:

1) a

non è congruo 1 modulo n 2) a

è congruo 1 modulo n

Supponiamo che si verifichi il caso 1): sia d il periodo di [a]

nel gruppo moltiplicativo Z

*: per

una proprietà del periodo si ha d(n) cioè dp(p-1), dunque p(p-1)=hd con h numero naturale.

Essendo a

1 (mod n=p

), a maggior ragione si ha a

1 (mod p), dunque [a]

=[1]

e per una proprietà del periodo di [a]

in Z

* si deduce che (p-1)d, dunque d=(p-1)s con s numero naturale.

Da p(p-1)=hd=h(p-1)s segue p=hs, quindi s=1 oppure s=p. Ma non può essere s=1, altrimenti sarebbe d=(p-1), a

1 (mod n), in contraddizione con l’ipotesi del caso 1).

Dunque s=p, d=p(p-1): il periodo di [a]

nel gruppo moltiplicativo Z

* è allora d=(n)=p(p-1), e l’intero a è una radice primitiva modulo n.

Supponiamo che si verifichi invece il caso 2): consideriamo l’intero b=a+p. Sviluppando la potenza con esponente p-1 con la regola di Newton si ha:

b

= (a+p)

=

1 1

0

1

p p j j

j

p a p

j

  



  

 

 

 ^{= a}

^+(p-1)pa

^+p

m (con m intero) Tenendo conto che a

1 (mod n) , si hanno le seguenti congruenze modulo n=p

: b

 a

+(p-1)pa

= a

+p

a

- pa

 1- pa

(mod n)

Si conclude che b

non è congruo 1 modulo n (se così fosse sarebbe p

pa

, quindi pa

ossia pa contro l’ipotesi che [a]

 Z

*). Ma [a]

=[a+p]

=[b]

dunque anche b é una radice primitiva modulo p.

Sostituendo a con b si ricade allora nel caso 1), e si ha che b=a+p è una radice primitiva modulo n . Nota: dalla dimostrazione precedente si ricava che, se a è una radice primitiva modulo p allora vi sono solo 2 casi possibili: a è anche radice primitiva modulo p

(se a

non è congruo 1 modulo p

), oppure (a+p) è radice primitiva modulo p

(se a

è congruo 1 modulo p

).

Quindi conoscendo una radice primitiva modulo p si può calcolare una radice primitiva modulo p

. Si noti che esistono algoritmi per calcolare una radice primitiva modulo p (per esempio un noto algoritmo dovuto a Gauss).

Test di primalità di Rabin-Miller

E’ un test di primalità probabilistico, che si applica ad un input n>1 naturale dispari (non è una restrizione sostanziale perché un naturale pari è sempre composto, tranne nel caso n=2).

Rispetto al test di Fermat non presenta “eccezioni” (come i numeri di Carmichael) ed inoltre la probabilità che un numero composto superi il test è  1/4 (contro il  1/2 del test di Fermat per i numeri non di Carmichael).

I passi dell’algoritmo del test di Rabin-Miller sono:

1) in input il naturale n>1 dispari

2) si calcola la massima potenza 2

di base 2 ed esponente s>0 tale che 2

sia divisore del numero pari n-1, e dunque si rappresenta (n-1) nella forma: n-1=2

t, con t>0 numero naturale dispari 3) si sceglie random un intero a con 1 a  n-1 (detto base)

4) si costruiscono le riduzioni modulo n delle s potenze di base a ed esponente t, 2

t, 2

t, ….. , 2

t:

_a

modn i=0,1,…..,s-1 5) se è verificata almeno una delle seguenti condizioni:

a

modn =1 oppure _a

modn = n-1 per qualche i=0,1,….,s-1

si esce con output ”n è primo”, altrimenti si esce con output “n è composto”.

Notiamo che le condizioni del passo 5) equivalgono alle congruenze:

a

1 (mod n), _a

-1 (mod n) i=0,1,…..,s-1.

Notiamo anche che nel passo 4) si possono semplificare i calcoli osservando che ognuna delle s

potenze _a

è il quadrato della precedente, quindi dal calcolo della riduzione modulo n di a

(che é

la prima) si possono ricavare facilmente le riduzioni delle successive, quadrando ripetutamente le precedenti riduzioni ed ogni volta riducendo il risultato modulo n .

Verifichiamo prima di tutto che un input n primo (dispari) supera sempre il test.

Utilizzeremo la proprietà seguente: se n è primo e se x è un numero 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 a non multiplo di n (perché a<n), per il Piccolo Teorema di Fermat si ha:

a

= _a

= ( a

)

1 (mod n)

e per quanto premesso sopra si ha _a

1 (mod n), ma allora (non essendo per assurdo verificata nessuna delle condizioni del passo 5)) si deduce _a

= ( a

)

1, _a

1, da cui (con lo stesso ragionamento) _a

1, e così via procedendo a ritroso, fino ad arrivare ad _a

= ( ) a

1, a

1, contraddizione perchè a

1, a

 -1 sono fra le condizioni del passo 5) che per assurdo abbiamo supposto non verificate.

Esaminiamo poi la complessità dell’algoritmo.

Sia x=L(n) la lunghezza binaria dell’input n.

Notiamo prima di tutto che da 2

 2

t=n-1<n<2

segue s<x.

Nel passo 2), il calcolo della differenza (n-1) ha complessità lineare O(x) e possiamo trascurare la complessità della rappresentazione di n-1 nella forma n-1=2

t, con t>0 numero naturale dispari:

l’esponente s si ottiene dal numero degli ultimi bits 0 consecutivi nella rappresentazione binaria del numero n-1, e il numero t si ottiene elidendo questi s bits.

Nel passo 4) si tratta di calcolare le s riduzioni modulo n (per confrontarle con i valori 1, n-1):

_a

modn dove i=0,1,….,s-1

ognuna con esponente 2

t<2

t<n-1<n e con base a<n, e si può utilizzare l’algoritmo della esponenziazione modulare, che ha complessità di ordine O(x

): poiché il numero s di riduzioni da calcolare é <x la complessità totale del Test di Rabin-Miller é di ordine O(x

).

Anche per il test di Rabin-Miller, come per il test di Fermat, può avvenire che un input n composto (dispari) superi il test, “fingendo” di essere primo.

Diremo che un naturale n composto dispari è fortemente pseudoprimo nella base a (dove a è la base scelta random nel passo 3)), se n supera il test di Rabin-Miller per tale scelta di a.

Ricordiamo che n (composto) é detto pseudoprimo nella base a, se n supera il test di Fermat per tale scelta di a, cioè se a

1 (mod n).

Dimostriamo ora che se n composto (dispari) è fortemente pseudoprimo nella base a, allora n è anche pseudoprimo nella stessa base a: infatti, essendo verificata una delle condizioni del passo 5), vi sono 2 casi possibili:

a

1 (mod n): in tale caso si ha a

= a

= ( ) a

1 (mod n);

2ⁱt

a -1 (mod n) per qualche i=0,1,…..,s-1: in tale caso si ha a

= a

= ( 1) 

=1 (mod n).

Esempio.

Consideriamo il minimo numero di Carmichael n=561=31117.

Sappiamo che esso è pseudoprimo in tutte le basi a tali che a,561 sono coprimi, quindi in tutte queste basi (che sono la maggioranza) “finge” di essere primo superando il test di Fermat.

Una di tali basi è per esempio a=2; se utilizziamo con tale base il test di Rabin-Miller, si ha:

n-1=560=2

t dove s=4, t=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=1

quindi non é verificata nessuna delle condizioni del passo 4), e il numero n=561 non supera il test di Rabin-Miller nella base a=2 (cioé in tale base 561 é soltanto pseudoprimo nella base, ma non é fortemente pseudoprimo): in pratica 561 “si rivela” composto utilizzando la base a=2 nel test di Rabin-Miller (mentre “fingeva” di essere primo nel test di Fermat).

Nota. Miller (1977) implementò per primo il test di primalità sopra esposto, e formulò la seguente congettura (ancora non dimostrata né vera né falsa) :

se n è un input composto (dispari) di lunghezza x=L(n), allora esiste una base a con 1 a 2x

in cui n non è fortemente pseudoprimo (cioè in cui n non supera il test, rivelando di essere composto).

Se tale congettura fosse dimostrata vera, il test diventerebbe deterministico di complessità polinomiale, perché non si dovrebbe scegliere casualmente la base a, ma farle assumere tutti i valori nell’intervallo [1, 2x

] (valori il cui numero è di ordine O(x

)) e se il test è sempre superato si potrebbe concludere con certezza che n è primo (la complessità del test sarebbe di ordine O(x

)).

Fu in seguito Rabin (1980) che trasformò questo “tentativo” di costruzione di test deterministico nel

test probabilistico, ora conosciuto appunto come test di Rabin-Miller.