con p primo, il gruppo moltiplicativo Z

Teoria dei numeri e Crittografia: lezione del 9 maggio 2011

Nella lezione precedente abbiamo dimostrato parzialmente il seguente:

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 (continuazione).

Se a è una radice primitiva modulo p (che esiste per un risultato precedente) abbiamo distinto 2 casi possibili:

1) a

non è congruo 1 modulo n 2) a

è congruo 1 modulo n

Nel caso 1) abbiamo già dimostrato che lo stesso a è anche una radice primitiva modulo n=p

. 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 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 casualmente 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:

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.

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 detto sopra si ha _a

1 (mod n), ma allora (non essendo per assurdo verificata nessuna delle condizioni del passo 5)) _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 (si tratta di effettuare successive divisioni per 2, che si ottengono elidendo le ultime cifre binarie =0 di n-1).

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 <n e con base <n, e si può utilizzare l’esponenziazione modulare, che ha complessità di ordine O(x

): poiché il numero s é <x la complessità totale del Test di Rabin-Miller é 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 1an- 1 è la base scelta casualmente 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): si ha a

= _a

= ( ) a

1 (mod n)

- _a

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

= _a

= ( a

)

 ( 1) 

=1 (mod n).