Il teorema di Pepin permette di costruire un algoritmo deterministico di primalità per i numeri di Fermat F r = 2 ( )2

Teoria dei numeri e Crittografia: lezione del 12 maggio 2011

Il teorema di Pepin permette di costruire un algoritmo deterministico di primalità per i numeri di Fermat F r = ₂ ^{( ) 2}

+1 (con r>0):

1) si calcola la riduzione 3 ^{F 1}

₂ ^- modFr

2) se tale riduzione è = (n -1) si esce con output “F r è primo”; in caso contrario si esce con output “F r è composto”.

Poiché si può utilizzare l’esponenziazione modulare, la complessità di tale test è  O(x ³ ), dove x=L(F r )=2 ^r +1 (perché ₂ ^{( ) 2}

< F r < ₂ ^{( 2 1}

^{+ )} ).

I numeri di Fermat F r hanno alcune interessanti applicazioni geometriche relative al cosiddetto problema della “ciclotomia”: fissato un naturale n>2, suddividere una circonferenza in n parti uguali (equivalentemente disegnare un poligono regolare di n lati iscritto nella circonferenza) usando solo riga e compasso.

Per quali valori di n>2 il problema ha soluzione ?

Per esempio per n=6 il problema ha soluzione: il lato dell’esagono regolare si può costruire con riga e compasso perché la sua ampiezza è uguale a quella del raggio della circonferenza circoscritta.

Esiste un importante Teorema (di cui diamo solo l’enunciato):

Teorema.

Il problema della ciclotomia ha soluzione per tutti e soli i valori n>2 tali che n sia della forma:

^...

t r r r

n = 2 F F F

dove t0, e F F r

^, r

^,..., F r

sono numeri primi di Fermat distinti (al limite può essere anche m=0, quando n è una potenza di 2)

Per esempio per n=7 il problema della ciclotomia non ha soluzione (perché 7 è primo ma non è un primo di Fermat): non è possibile costruire con riga e compasso il lato dell’ettagono regolare.

Anche per n=9=3 ² il problema della ciclotomia non ha soluzione (perché 9 è il quadrato di un primo di Fermat): non è possibile costruire con riga e compasso il lato dell’ennagono regolare.

Dimostriamo che i fattori primi dei numeri di Fermat F r hanno una struttura particolare, per r>1.

Teorema.

Se r>1, per ogni divisore primo p di F r = ₂ ^{( ) 2}

+1 si ha p  ^{1 (mod 2 r+2} ), quindi p=1+k2 ^r+2 con k numero naturale.

Dimostrazione:

Per ipotesi p è divisore del numero dispari F r , quindi p è primo >2. Si ha ₂ ^{( ) 2}

 -1 (mod p).

Essendo 2, p coprimi si ha [2]Z p * , [ ] 2 ^{( 2}

⁾ =[-1] ² = [1], e se s=ord([2]) in Z p * , s è divisore di 2 ^r+1 , quindi s=2 ^d con dr+1. Dimostriamo che d=r+1. Se per assurdo fosse d<r+1, sarebbe:

_{[ ] 2} ^{( ) 2}

= _{([ ] 2} ^{( ) 2}

₎ ²

= _{([ ] ) 2} ^{s 2}

=[1]

ed essendo ₂ ^{( ) 2}

 -1 (mod p) si avrebbe 1  -1 (mod p), contraddizione perché p>2.

Dunque d=r+1, s=2 ^r+1 . Ma il s=ord([2]) è divisore della cardinalità p-1 di Z p * , p-1=2 ^r+1 z con z naturale, e dunque p-1 è multiplo di 8 (perché r+1>2), ossia p  ^{1 (mod 8).}

Per le proprietà del simbolo di Legendre si ha (2/p)=1, e per il criterio di Eulero 2 ^(p-1)/2  ^{1 (mod p),}

[2] ^(p-1)/2 =[1], dunque s=ord([2]) è divisore di (p-1)/2, cioè (p-1)/2=hs=h2 ^r+1 con h naturale da cui la

tesi.

Per trovare un divisore primo di F r (con r>1), si può allora implementare il seguente algoritmo: si fanno assumere in successione al parametro k i valori interi positivi k=1,2,…., verificando con l’algoritmo della divisione se il numero p=1+k2 ^r+2 è divisore di F r . Il minimo valore di k per cui p=1+k2 ^r+2 è divisore di F r fornisce con certezza un divisore primo p di F r (se p per assurdo non fosse primo, p avrebbe un divisore primo p 1 <p , ma p 1 sarebbe a maggior ragione divisore di F r , quindi sarebbe della forma p 1 =1+k 1 2 ^r+2 con k 1 <k, contro la minimalità di k).

Dopo avere trovato un divisore primo p di F r , si può ripetere il ragionamento sul numero F r /p per trovare altri divisori primi di F r /p (e quindi di F r )e pervenire alla completa fattorizzazione di F r in prodotto di primi.

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 l’identità algebrica già considerata in altre dimostrazioni:

(x ^s -y ^s )=(x-y)(x ^s-1 +x ^s-2 y+….+xy ^s-2 +y ^s-1 )

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-1 2 -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-1 2 -2)modM p

(notare che ogni 0 T i <M p , e che 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”.

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-1 2 di 2 fattori <M p quindi di lunghezza  p (complessità  O(p ² )); il calcolo della differenza T i-1 2 -2, dove T i-1 2 ha lunghezza  2p (complessità  O(p))); il calcolo della riduzione (T i-1 2 -2)modM p , dove (T i-1 2 -2) ha lunghezza  2p (complessità  O(4p ² )=O(p ² )).

In totale il calcolo di ognuno dei T i ha complessità  O(p ² ); poiché il numero dei T i è (p-1), la complessità totale del test è  O(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 alla completa fattorizzazione di M p in prodotto di primi.

Numeri perfetti.

Un numero naturale n>1 è detto perfetto se n coincide con la somma dei suoi divisori <n.

Per esempio n=6 è perfetto in quanto 6=1+2+3; n=8 non è perfetto in quanto 81+2+4.

Se per ogni naturale n>1 definiamo la funzione (n) uguale alla somma di tutti i divisori di n (incluso n), si ha che un naturale n>1 è perfetto se e solo se (n)=2n.

Se n è un naturale >1, e se la fattorizzazione di n in prodotto di potenze di primi distinti è:

n= p p ₁ ^k

₂ ^k

.... p _r ^k

(p i primi distinti, k i >0)

allora (per la fattorizzazione unica) ogni divisore d di n ha la forma:

d= p p ₁ ^h

₂ ^h

.... p _r ^h

con 0  h i  k i per ogni i=1,….,r

dunque si ha la seguente formula per il calcolo di (n):

(n) = ^



 r

k h 0 i1

rh 2h 1h

i i

r 2 1

p ....p p

Teorema.

Se n,m sono naturali >1 coprimi, si ha (nm)=(n)(m).

Dimostrazione:

Se le fattorizzazioni di n,m in prodotto di potenze di primi distinti sono rispettivamente:

n= p ₁ ^{k 1} p ₂ ^{k 2} ....p _r ^{k r} m= p _{r  1} ^{k r  1} p _{r  2} ^{k r  2} ....p _s ^{k s}

(i fattori primi di n sono distinti da quelli di m perché n, m sono coprimi) la fattorizzazione di nm in prodotto di potenze di primi distinti è:

nm= p ₁ ^{k 1} p ₂ ^{k 2} ....p _r ^{k r} p _{r  1} ^{k r  1} p _{r  2} ^{k r  2} ....p _s ^{k s} e per la proprietà distributiva si ottiene:

(n)(m)=  



   

i

i i i

s 1 r r

1

k h

0 0 h k

s h 1 h

h r h r

1 ....p )( p ....p )

p

( = 





s 2 1

k h 0

r h 2 h

1 h p ....p

p =(nm).

Vedremo che vi è uno stretto legame fra la teoria di numeri perfetti e quella dei numeri di Mersenne.

Cominceremo con la dimostrazione del seguente risultato di Euclide:

Teorema (Euclide).

Se il numero di Mersenne M k =2 ^k -1 è primo, il numero n=2 ^k-1 (2 ^k -1)=2 ^k M è perfetto (e ovviamente pari).

Dimostrazione.

Essendo M k dispari, i numeri 2 ^k-1 , M k sono coprimi, e per un risultato precedente si ha:

(n)=(2 ^k-1 )(M k ).

Essendo M k primo si ha (M k )=1+M k =1+(2 ^k -1)= 2 ^k .

I divisori di 2 ^k-1 sono le potenze 2 ⁰ , 2 ¹ , …., 2 ^k-1 , dunque (2 ^k-1 )= 2 ⁰ +2 ¹ +2 ² +….+2 ^k-1 =2 ^k -1 (dove si è sfruttata l’identità (x-y)(x ^k-1 +x ^k-2 y+….+xy ^k-2 + y ^k-1 ) per x=2, y=1).

In totale si ottiene (n)=2 ^k (2 ^k -1)=2[2 ^k-1 (2 ^k -1)]=2n ed n è perfetto.

Eulero dimostrò il viceversa:

Teorema (Eulero).

Se n è un numero naturale pari perfetto, allora n è della forma n=2 ^k-1 M k dove M k =2 ^k -1 è un numero di Mersenne primo.

Dimostrazione:

Poiché n è pari, se 2 ^t (con t>0) è la massima potenza di 2 che divide n, si può scrivere n=2 ^t m con m dispari.

Poniamo k=t+1>1, in modo che n=2 ^k-1 m.

Essendo m dispari, i numeri 2 ^k-1 , m sono coprimi, e dunque (n)=(2 ^k-1 )(m).

Come nella dimostrazione del Teorema precedente si ha (2 ^k-1 )=2 ^k -1.

Poiché n è perfetto per ipotesi, si ottiene 2 ^k m=2n=(n)=(2 ^k-1 )(m)=(2 ^k -1)(m).

Dunque 2 ^k -1 è divisore del prodotto 2 ^k m; ma 2 ^k , 2 ^k -1 sono coprimi (perché consecutivi), quindi 2 ^k -1 è divisore del fattore m, e si ha m=(2 ^k -1)M, con M naturale divisore di m.

Sostituendo si ha: 2 ^k m=2 ^k (2 ^k -1)M=(2 ^k -1)(m), da cui (m)=2 ^k M.

Si ha allora m+M=(2 ^k -1)M+M=2 ^k M=(m).

Essendo m,M entrambi divisori di m, ed essendo (m) la somma di tutti i divisori di m, concludiamo che m,M sono gli unici divisori di m (e dunque necessariamente M=1), ossia m è primo ed inoltre:

m=(2 ^k -1)M=(2 ^k -1)=M k , ed n=2 ^k-1 m=2 ^k-1 M k , come voleva la tesi.