Teoria dei numeri e Crittografia: lezione del 7 dicembre 2011 Numeri di Mersenne.

(1)

Teoria dei numeri e Crittografia: lezione del 7 dicembre 2011 Numeri di Mersenne.

Dopo avere studiato i numeri di Fermat (successivi di una potenza di 2), studieremo i numeri che precedono una potenza di 2.

Poniamo M

k

=2

^k

-1, con k>1: un tale numero naturale (dispari) è detto numero di Mersenne.

Come per i numeri di Fermat, studiamo quando un numero di Mersenne M

k

è primo: vedremo in tale caso che k non può essere un esponente qualunque.

Teorema.

Se M

k

=2

^k

-1 (con k>1) è un numero primo, l’esponente k è necessariamente primo.

Dimostrazione:

Per assurdo sia k non primo, e sia k=ts, con 1<t,s<k.

Sfruttando la proprietà (già considerata in altre dimostrazioni) che per ogni naturale s si ha:

(x-y)(x

^s

-y

^s

)

Applicata in particolare con y=1, x=2

^t

, si ottiene che x-y=2

^t

-1 è divisore di x

^s

-y

^s

=2

^ts

-1=2

^k

-1=M

k

, con 2

^t

-1>1 (perché t>1) e 2

^t

-1<M

k

(perché t<k), contraddizione perché M

k

è primo.

Dunque, per cercare valori primi di M

k

=2

^k

-1 si deve restringere la ricerca al caso in cui l’esponente k sia primo.

Esistono tuttavia esponenti k primi per cui M

k

non è primo: per esempio per k=11 si ha M

k

=2

¹¹

=2047=2389, non primo.

Notizie sulla situazione attuale della ricerca sui numeri di Mersenne primi si possono trovare sul sito: www.mersenne.org (progetto GIMPS: Great Internet Mersenne Primes Search).

A tutt’oggi sono stati trovati 46 numeri di Mersenne primi: il più grande è stato scoperto nell’Agosto del 2008: è il numero 2

^43.112.609

-1, ed ha 12.978.189 cifre in base 10.

Le tecniche per verificare se un numero di Mersenne è primo fanno uso del cosiddetto criterio di Lucas-Lehmer, che ora esporremo.

Definiamo la successione S

1

, S

2

, …., S

n

,….. di numeri naturali nel modo seguente:

S

1

= 4; per ogni i>1: S

i

= S

i-12

-2

(quindi per esempio S

2

=4

²

-2=14, S

3

=14

²

-2=194 etc.)

Il criterio di Lucas-Lehmer è enunciato nel seguente Teorema (di cui omettiamo la dimostrazione):

Teorema di Lucas-Lehmer.

Dato un numero di Mersenne M

p

=2

^p

-1, con p primo >2, si ha:

M

p

è primo  S

p-1

 0 (mod M

p

)

Si può allora costruire un algoritmo deterministico di primalità per i numeri di Mersenne M

p

=2

^p

-1, con p primo >2, nel modo seguente:

1) Si calcolano i numeri interi T

1

, T

2

, …., T

p-1

ponendo:

T

1

= 4; per ogni i>1: T

i

= (T

i-12

-2)modM

p

(notare che per ogni i si ha 0 T

i

<M

p

; inoltre per ogni i si ha anche S

i

T

i

(mod M

p

) come si dimostra facilmente per induzione)

2) Se T

p-1

=0 (ciò equivale ad S

p-1

 0 (mod M

p

)) si esce con output “M

p

è primo”; in caso

contrario si esce con output “M

p

è composto”.

(2)

Il numero M

p

ha lunghezza binaria p (in base 2 ha p cifre tutte =1). Esaminando la complessità dell’algoritmo, si nota che il calcolo di ognuno dei T

i

comporta:

il calcolo del prodotto T

i-12

di 2 fattori <M

p

quindi di lunghezza  p (complessità di ordine O(p

²

)); il calcolo della differenza T

i-12

-2, dove T

i-12

ha lunghezza  2p (complessità di ordine O(p))); il calcolo della riduzione (T

i-12

-2)modM

p

, dove (T

i-12

-2) ha lunghezza  2p (complessità di ordine O(p

²

)).

In totale il calcolo di ognuno dei T

i

ha complessità di ordine O(p

²

); poiché il numero dei T

i

da calcolare è (p-1)(quindi di ordine O(p)), la complessità totale del test è di ordine O(p

³

), dove p=L(M

p

) .

Anche nel caso in cui il numero di Mersenne M

p

non sia primo, i suoi divisori primi (almeno nel caso p primo >2) hanno una struttura particolare:

Teorema.

Se p è un primo >2, per ogni divisore primo q di M

p

=2

^p

-1 si ha q  1 (mod p), quindi q=1+kp con k naturale, e inoltre si ha q  1,7 (mod 8).

Dimostrazione:

Essendo M

p

dispari, si ha q dispari. Poiché 2

^p

 1 (mod q), si ha [2]

^p

=[1] in Z

q

* e se s=ord([2]) è il periodo di [2] in Z

q

*, si ha sp, da cui, essendo p primo, s=p (perché s1 in quanto [2][1]).

Il periodo s=p è divisore della cardinalità q-1 di Z

q

* , dunque q  1 (mod p), q=1+kp con k naturale e in particolare k pari perché q, p sono dispari).

Infine, posto k=2t, [2]

^(q-1)/2

=([2]

^p

)

^t

=[1] in Z

q

* , 2

^(q-1)/2

 1 (mod q), e per il criterio di Eulero 2 è resto quadratico modulo q, dunque (2/q)=1, e ciò sappiamo che avviene solo per q  1,7 (mod 8).

Per trovare un divisore primo di M

p

(con p primo >2 fissato), si può procedere allora facendo assumere in successione al parametro t i valori interi positivi t=1,2,…., e verificando con l’algoritmo della divisione se il numero q=1+2tp è  1,7 (mod 8) ed è divisore di M

p

. Il minimo valore di t per cui ciò avviene fornisce con certezza un divisore primo q di M

p

(se q non fosse primo avrebbe un divisore primo q

1

<q

,

ma q

1

sarebbe a maggior ragione divisore di M

p

, quindi sarebbe 

1,7 (mod 8) e della forma q

1

=1+2t

1

p con t

1

<t, contro la minimalità di t).

Dopo avere trovato un divisore primo q di M

p

, si può ripetere il ragionamento sul numero M

p

/q per

trovare altri divisori primi di M

p

e pervenire infine alla completa fattorizzazione di M

p