Teoria dei numeri e Crittografia: lezione del 2 maggio 2011

(1)

Teoria dei numeri e Crittografia: lezione del 2 maggio 2011

Sia G un gruppo (in notazione moltiplicativa). Per ogni aG e per ogni numero naturale k, definiamo la potenza di base a ed esponente k uguale al seguente elemento di G:

a

^k

=aa…a (k fattori).

La 2) dell’ultimo Teorema dimostrato nella lezione precedente si può dunque riformulare nel modo seguente:

se G è gruppo commutativo e finito di cardinalità n, per ogni aG si ha a

ⁿ

= 1

G

. (ripetiamo che la tesi è ugualmente valida nel caso di un gruppo non commutativo).

Dato un elemento a del gruppo G, possiamo estendere il concetto di potenza di base a anche al caso di esponente 0, definendo per convenzione a

⁰

=1

G

.

E’ facile verificare che per le potenze di base a valgono le usuali proprietà delle potenze numeriche:

se h, k sono interi  0 si ha a

^h+k

=a

^h

a

^k

, a

^hk

=(a

^h

)

^k

.

Nota: Se la notazione è additiva, invece di potenza parleremo di multiplo di a con coefficiente naturale k, definito come ka=a+a+…+a (k addendi), ponendo poi per convenzione 0a=0

A

(neutro del gruppo additivo G): le proprietà dimostrate sopra si possono facilmente riformulare nel linguaggio additivo.

Se G è gruppo commutativo finito di cardinalità n, per quanto già dimostrato, esiste qualche numero naturale k tale che a

^k

=1

G

(per esempio k=n), dunque esiste il minimo numero naturale k tale che a

^k

=1

G

(detto ordine o periodo dell’elemento a, e indicato con ord

G

(a), o semplicemente con ord(a)).

Se consideriamo una qualunque potenza di base a ad esponente naturale h, dividendo h per k=

ord(a) con quoziente q e resto r (con 0r<k) si ha a

^h

=a

^kq+r

=(a

^k

)

^q

a

^r

=(1

G

)

^q

a

^r

=a

^r

, quindi ogni potenza di base a coincide con una delle potenze a

⁰

,a

¹

,…,a

^k-1

.

Inoltre tali potenze sono distinte: se per assurdo fosse a

^s

=a

^t

con 0t<s<k, si avrebbe (cancellando t fattori con la legge di cancellazione) a

^s-t

=1

G

, con 0<s-t<k, contraddizione perché k=ord(a).

Inoltre una potenza a

^h

coincide con l’elemento neutro 1

G

se e solo se kh: infatti, ragionando come sopra con la divisione di h per k, si ha a

^h

= a

^r

, dunque se a

^h

=1

G

si ha r=0 (perché non può essere 0<r<k=ord(a)) e viceversa se r=0 allora a

^h

=a

⁰

=1

G

.

In particolare, poiché si è dimostrato che a

ⁿ

=1

G

(dove n è la cardinalità di G), il periodo k=ord(a) di un qualunque elemento di G è sempre divisore della cardinalità n del gruppo.

Si ha poi che due potenze a

^s

, a

^t

(con esponenti s,t0) coincidono se e solo se st (mod k=ord(a)):

infatti, se per esempio st, l’eguaglianza a

^s

=a

^t

è equivalente all’eguaglianza a

^s-t

=1

G

, e come già visto ciò avviene se e solo se k(s-t).

Riassumendo:

Se G è un gruppo commutativo finito di cardinalità n, per ogni aG si può definire il periodo dell’elemento a come il minimo numero naturale k=ord(a) tale che a

^k

=1

G

: tale numero è divisore di n. Le potenze di base a ed esponente  0 sono tutte e sole quelle con esponente 0,1,…,k-1 e sono distinte (quindi sono in numero di k); si ha inoltre a

^h

=1

G

 ord(a)= kh , e anche a

^s

=a

^t

 st (mod k).

Teorema di Eulero-Fermat.

Siano a,n due naturali coprimi (con n>1). Allora a

^(n)

1 (mod n).

Dimostrazione:

Il gruppo commutativo finito G= Z

n

* ha cardinalità (n), ed essendo a,n coprimi, si ha [a]G.

(2)

Per un risultato dimostrato in precedenza, ogni elemento di un gruppo finito commutativo elevato alla cardinalità del gruppo dà come risultato l’elemento neutro: nel nostro caso si ha [1]=[a]

^(n)

=[a][a]….[a]=[aa….a]=[a

^(n)

]

da cui la tesi.

Corollario (Piccolo Teorema di Fermat).

Se n è un numero primo, per ogni naturale a non multiplo di n si ha a

^n-1

1 (mod n).

Dimostrazione:

Essendo a non multiplo del primo n, i numeri a,n sono coprimi (perché le uniche possibilità per il mcd(a,n) sono 1, n). Poiché (n)=n-1 (perché n è primo) la tesi segue dal Teorema di Eulero- Fermat.

Test di primalità.

Ricordiamo che un test di primalità deterministico è un algoritmo tale che, dato in input un numero naturale n>1, produce un output “n è primo” oppure “n è composto” (definendo composto un naturale >1 non primo), e tale che l’output sia “n è primo” se e solo se l’input n è un numero primo.

Oltre il test ingenuo di primalità (che verifica, per d=2,….,n-1, se esiste un d divisore non banale di n) un altro test di primalità deterministico segue dal seguente risultato:

Teorema di Wilson.

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

Dimostrazione:

(): Consideriamo il gruppo moltiplicativo Z

n

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

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

n

* = {[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]

^-1

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

^-1

) 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]

^-1

, 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 ovviamente alla condizione (n-1)!modn=(n-1)

(in quanto -1(n-1) (mod n)).

Il Teorema di Wilson permette di costruire il seguente test di primalità deterministico:

1) in input il naturale n>1

2) si costruisce la la successione y

1

,y

2,…,

y

n-1

ponendo y

1

=1, e per i>1 y

i

=(iy

i-1

)modn: notare che per ogni i>1 si ha y

i

 i! (mod n), come si dimostra facilmente per induzione (I

^a

forma), e dunque per i=n-1 si ha y

n-1

(n-1)! (mod n), ossia y

n-1

=(n-1)!modn (in quanto 0 y

i

 n-1)

3) se y

n-1

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

(3)

Esaminando la complessità di tale algoritmo, si verifica che, nonostante la costruzione di ogni termine y

i

si possa effettuare con algoritmi “efficienti” di complessità non più che polinomiale, il numero di y

i

da calcolare è di ordine O(n) lineare rispetto all’input n, quindi di ordine esponenziale O(2

^x

) rispetto ad x=L(n) (perché 2

^x-1

 n<2

^x

).

Quindi tale algoritmo di primalità non è affatto “efficiente”.

Ricordiamo che un test di primalità probabilistico è un algoritmo tale che, dato in input un numero naturale n>1, dopo una serie di calcoli che coinvolgono anche alcuni elementi casuali, produce un output “n è primo” oppure “n è composto”, con la condizione che 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 l’input 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

^k

, 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.

Esamineremo alcuni test di primalità probabilistici, di complessità non più che polinomiale.

Il primo è il cosiddetto test di Fermat (basato sul Piccolo Teorema di Fermat): in realtà esso non è un test probabilistico a tutti gli effetti, perché vedremo che la probabilità che un numero composto superi (erroneamente) il test è maggiorata dalla costante C=1/2 (indipendente dall’input e dagli elementi casuali), ma ciò non avviene per tutti gli input composti.

Dunque tale test si può definire test probabilistico ma con delle “eccezioni” . I passi dell’algoritmo sono:

1) in input il numero 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 y=a

^n-1

modn : se y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)), y=1 e quindi si esce con output “n è primo”.