Teoria dei numeri e Crittografia: lezione dell’ 11 maggio 2011 Studiamo dunque i numeri naturali dispari n>1 della forma n=2m+1

Teoria dei numeri e Crittografia: lezione dell’ 11 maggio 2011

Studiamo dunque i numeri naturali dispari n>1 della forma n=2

+1, con m>0.

Fermat dimostrò che:

Teorema.

Se n=2

+1 (con m>0), e se n è primo, allora necessariamente l’esponente m è una potenza di 2 della forma m=2

, con r0.

Dimostrazione:

Per ogni naturale s>1 vale la seguente identità algebrica:

(x

-y

)=(x-y)(x

+x

y+….+xy

+y

)

(facilmente dimostrabile utilizzando la I

forma del principio di induzione).

Quindi (x-y)(x

-y

) per ogni naturale s>1.

Per assurdo supponiamo n=2

+1 primo, e l’esponente m non potenza di 2. Se 2

(con r0) è la massima potenza di 2 che divide r (al limite r=0), si ha m=2

s, con s>1, s dispari.

Dall’identità algebrica precedente, applicata con x= ₂

, y=-1, si ha che x-y= ₂ ⁽²

⁾ +1n= ₂

+1:

tale divisore x-y= ₂ ⁽²

⁾ +1 di n è >1 (perché ₂ ⁽²

⁾ >0) ed è <n= ₂

+1 (perché 2

s>2

, essendo s>1), in contraddizione con l’ipotesi che n è primo.

Visto il risultato precedente, studieremo solo i numeri di Fermat della forma F

= ₂

+1 (al variare dell’intero r0), cercando quali fra essi sono numeri primi.

Notizie sullo stato attuale delle ricerche si possono trovare all’indirizzo:

www.prothsearch.net/fermat.html

Fermat congetturò che per ogni intero r0 il numero F

= ₂ ⁽²

⁾ +1 fosse primo.

In effetti per r<5 i valori F

=3, F

=5, F

=17, F

=257, F

=65.537 sono numeri primi.

Ma per r=5 il numero F

=4.294.967.297 non è primo, essendo divisibile per il numero primo 641.

Quindi Fermat si sbagliava: inoltre a tutt’oggi per nessun r5 si è trovato un F

che sia primo, e si congettura che un tale F

non esista (F

è il numero di Fermat con r minimo del quale non si conosce la primalità o la non primalità).

Per dimostrare il criterio di Pepin per i numeri di Fermat F

, dobbiamo però introdurre il concetto di resto quadratico modulo un numero primo.

Resti quadratici.

Siano p un numero primo, a un numero naturale non multiplo di p.

Si ha allora mcd(a,p)=1, dunque [a] appartiene al gruppo moltiplicativo Z

* degli elementi invertibili di Z

.

Diremo che a è un resto quadratico modulo p se esiste un naturale b tale che ab

(mod p) (quindi se a è un “quadrato modulo p”). Notiamo che in tal caso anche il naturale b è ovviamente non multiplo di p, dunque [b] Z

* e si ha [a]=[b

]=[b]

: in pratica a è resto quadratico modulo p se e solo se [a] è un quadrato perfetto in Z

* (quindi la proprietà di essere un resto quadratico modulo p è relativa alla classe di congruenza modulo p, non al singolo naturale a).

Esempio.

Troviamo quali numeri naturali (non multipli di p=7) sono resti quadratici modulo 7.

Si ha Z

* = {[1], [2], [3], [4], [5], [6]}, e i quadrati delle classi sono [1]

=[6]

=[1],

[2]

=[5]

=[4], [3]

=[4]

=[2].

Quindi i resti quadratici modulo 7 sono i numeri naturali a tali che a1,2,4 (mod 7).

Per p=2 la situazione dei resti quadratici è banale: si ha Z

*={[1]}, [1]

=[1], e tutti i naturali coprimi con 2 (cioè dispari) sono resti quadratici modulo 2.

Quindi studieremo la teoria dei resti quadratici solo nel caso di un numero primo p>2 (quindi p dispari).

Criterio di Eulero.

Sia p>2 un primo ed a un naturale non multiplo di p. Allora:

a è resto quadratico modulo p  a

1 (mod p) Dimostrazione:

() Per ipotesi esiste [b]  Z

* tale che [a]=[b]

. Per il Piccolo Teorema di Fermat si ha:

[1]=[b]

=[a]

e si ottiene la tesi.

() Per il Teorema di Gauss, il gruppo Z

* è ciclico, generato da un elemento [x] di periodo uguale alla cardinalità (p-1) di Z

*.

Ogni elemento di Z

* è potenza di [x], e in particolare [a]=[x]

.

Per ipotesi si ha [1]=[a]

=([x]

)

=[x]

, dunque t(p-1)/2 è multiplo del periodo (p-1) di [x], cioè t è multiplo di 2, t=2k, da cui ([x]

)

=[x]

=[a], ed a è resto quadratico modulo p.

Come conseguenza del criterio di Eulero, si ha che la verifica se a è resto quadratico modulo p si può effettuare con un algoritmo di complessità non superiore alla polinomiale, utilizzando l’esponenziazione modulare per verificare se a

modp=1).

Osservazione: Se p>2 é un primo ed a un naturale non multiplo di p, e se a non è resto quadratico modulo p, cosa possiamo dire di a

?

Per il Piccolo Teorema di Fermat si ha (a

)

1 (mod p), dunque, per una proprietà già osservata durante il test di Rabin-Miller, si ha a

1 (mod p), e per il criterio di Eulero si conclude che a

1)/2

 -1 (mod p).

Quindi la situazione è la seguente:

a è resto quadratico modulo p  a

1 (mod p) a non è resto quadratico modulo p  a

-1 (mod p)

Introduciamo allora il simbolo di Legendre (a/p), definito solo per p primo >2 ed a naturale non multiplo di p:

(a / p) = +1 se a è resto quadratico modulo p (a / p) = -1 se a non è resto quadratico modulo p Proprietà:

Sia p primo >2.

1) Se a è un naturale non multiplo di p si ha a

(a / p) (mod p) Discende banalmente da quanto osservato sopra.

2) Se a,b sono naturali non multipli di p (quindi anche ab non è multiplo di p):

(ab / p)=(a / p)(b / p).

Infatti per la proprietà 1) si ha (ab / p)(ab)

a

b

(a / p)(b / p) (mod p), ma i valori possibili di ognuno dei 2 numeri (a / p)(b / p), (ab / p) sono 1, dunque la congruenza precedente è in effetti un’eguaglianza (perché la congruenza 1 -1 (mod p) non è vera nel caso p>2).

3) Se a,b sono naturali non multipli di p e se ab (mod p) allora (a / p)=(b / p).

Discende banalmente dall’osservazione che la proprietà di essere resto quadratico dipende solo

dalla classe di congruenza modulo p.

Siano dunque p>2 un primo, a >1 un numero naturale non multiplo di p, e fattorizziamo a in prodotto di potenze di primi distinti:

a = p p

.... p

(notare che ogni p

 p dunque p

non è multiplo di p, ed esiste (p

/ p)) Per la 2) si ha :

(a / p) =

1

( / )

r k

i i

p p



Ma nella formula precedente: se k

è pari ^{( / ) p p}

= ( 1) ^k

=+1, e se k

è dispari ^{( / ) p p}

=(p

/ p) (sempre perché (p

/ p)= 1) , dunque in totale si ha :

(a / p) =

1

( / )

i

r i k disparii

p p



Dunque il calcolo di (a / p) si riconduce al calcolo di (q / p) dove q è un primo p.

Affronteremo prima il caso q=2 e poi il caso q>2 (quindi il caso q dispari).

Teorema.

Se p è primo >2 si ha: (2 / p) = _{( 1) }

Dimostrazione:

Essendo p dispari, p-1 è pari. Elenchiamo tutti i (p-1)/2 numeri naturali pari  (p-1) in due modi diversi:

2,4,6 …… , (p-5),(p-3), (p-1) (ordine naturale)

(p-1), 2, (p-3), 4, 6, (p-5) ……. (ultimo, primo, penultimo, secondo, terzultimo, terzo……) Rispetto al secondo ordinamento valgono banalmente le seguenti (p-1)/2 congruenze modulo p:

p-11(-1)

(mod p) 22(-1)

(mod p) p-33(-1)

(mod p) 44(-1)

(mod p) etc…..

Se moltiplichiamo membro a membro tali congruenze, a primo membro si otterrà il prodotto di tutti i numeri naturali pari  (p-1) ossia il numero:

24…..(p-3)(p-1)=(21)(22)…..(2(p-3)/2)(2(p-1)/2)=2

[(p-1)/2]!

mentre a secondo membro si otterrà il numero:

(1 2 …. (p-1)/2)  (-1)

= [(p-1)/2]! ( 1) 

(dove si è sfruttata, per k=(p-1)/2, la nota proprietà: k(k+1)/2 è la somma dei primi k naturali).

Si ottiene dunque la congruenza modulo p:

2

[(p-1)/2]!  [(p-1)/2]! ( 1) 

(mod p) Da ciò si ha che:

p è divisore di [(p-1)/2]![ 2

- _{( 1) }

]

ma p non è divisore di [(p-1)/2]! (perché [(p-1)/2]! é un prodotto di naturali tutti <p dunque tutti non multipli di p), e allora p è divisore della differenza [ 2

- ( 1) 

], ossia :

2

 ( 1) 

(mod p)

Per la proprietà 1) del simbolo di Legendre, si ha (2 / p)  ( 1) 

(mod p)

I due membri di tale congruenza sono uguali a 1, dunque non possono essere diversi far loro ( la

congruenza +1-1 (mod p) non è vera perché p>2) e si ha la tesi.

Dal Teorema precedente segue in pratica che (2 / p)= 1 a secondo se (p

-1)/8 è pari o dispari. Ma considerando la classe [p] in Z

si ha [p]=[t] con t=1,3,5,7 (perché p è dispari), p=t+8k con k naturale. Si ha allora:

(p

-1)/8 = (t

-1)/8+(8k

+2tk)

Dunque (p

-1)/8 è pari se e solo se (t

-1)/8 è multiplo di 2, e ciò avviene solo per t=1,7.

Riassumendo:

(2 / p)=+1 se (p

-1)/8 è pari cioè se p1,7 (mod 8) (2 / p)= -1 se (p

-1)/8 è dispari cioè se p3,5 (mod 8)

Per il calcolo del simbolo di Legendre (q / p) nel caso di q, p primi distinti > 2 può essere utile il seguente Teorema (di cui si omette la dimostrazione):

Legge di reciprocità quadratica di Gauss.

Se p,q sono primi >2 distinti si ha:

(p / q)(q / p) = (-1)

Si può allora calcolare uno dei numeri (p / q), (q / p) conoscendo l’altro: infatti moltiplicando l’eguaglianza precedente per esempio per (p / q) (ricordando che (p / q)

=(1)

=1) si ha

(q / p) = (-1)

(p / q)

Tutte le considerazioni già fatte permettono di costruire un algoritmo per il calcolo di (a / p), quando p>2 è un primo ed a>1 è un numero naturale qualunque non multiplo di p:

- si rende a<p sostituendo a con la sua riduzione modulo p (per la proprietà 3) del simbolo di Legendre)

- si fattorizza a in prodotto di potenze di primi distinti:

a = p p

.... p

(p

primi distinti , tutti p perché p non è divisore di a) in modo da avere:

(a / p) =

1

( / )

i

r i k disparii

p p



e ricondurre il calcolo di (a / p) al calcolo di (p

/ p) - se p

=2 si usa la formula già dimostrata per (2 / p)

- se p

>2, si usa la legge di reciprocità quadratica per ricavare (p

/ p) in funzione di (p / p

), ed essendo p>p

si riduce p modulo p

, si fattorizza tale riduzione in prodotto di primi, e si itera il procedimento.

L’algoritmo precedente riconduce il calcolo a numeri sempre più piccoli: al limite alla fine si tratta di calcolare un simbolo di Legendre del tipo (2 / p)= ( 1) 

o (1/p)=1 (perché 11

(mod p)).

Esempio:

Calcoliamo (338/131).

Riducendo 338 modulo 131 si ottiene 76, quindi si deve calcolare (76/131).

I fattori primi di 76 sono 2 (con molteplicità 2) e 19 (con molteplicità 1), quindi (76/131)=(19/131).

Per la legge di reciprocità quadratica (essendo [(19-1)/2][(131-1)/2] dispari): (19/131)=-(131/19).

Riducendo 131 modulo 19 si ottiene 17, da cui (131/19)=(17/19).

Per la legge di reciprocità quadratica (essendo [(17-1)/2][(19-1)/2] pari): (17/19)=(19/17).

Riducendo 19 modulo 17 si ottiene 2, da cui (17/19)=(2/17).

Infine (2/17)=+1 (perché 171 (mod 8)).

Riassumendo si ha (338/131)= -1 (quindi 331 non è resto quadratico modulo 131).

Siamo ora in grado di dimostrare il:

Teorema di Pepin.

Il numero di Fermat F

= ₂

+1 (con r>0) è un numero primo  3

 ^{-1 (mod F}

⁾

Dimostrazione:

(): Basta applicare l’implicazione () del Teorema di Proth-Pocklington, con n=F

, h=1, a=3 (): Essendo 3, F

primi dispari distinti (perché F

>3 essendo r>0), per la legge di reciprocità quadratica si ha:

(3 / F

) = (F

/ 3) ( 1)



Ma (F

-1)/2= ₂

è pari (perché r>0), dunque (3 / F

) = (F

/ 3).

Valgono le seguenti congruenze modulo 3:

F

= ₂ ⁽²

⁾ +1 = ₄ ⁽²

⁾ +1  ¹⁺¹  2 (mod 3)

Dunque, per la proprietà 3) del simbolo di Legendre e per la regola di calcolo di (2 / p) si ha:

(3/F

) = (F

/3) = (2/3) = (-1)

= -1 Per il criterio di Eulero si ha infine la tesi 3

F

 ^{-1 (mod F}

^).