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

Teoria dei numeri e Crittografia: lezione del 5 dicembre 2011

Abbiamo dimostrato il seguente:

Teorema.

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

Da tale 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 criterio di Pepin per la primalità dei numeri di Fermat:

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}

^).

Il teorema di Pepin permette di costruire un test deterministico di primalità per i numeri di Fermat F

= ₂

+1 (con r>0):

1) si calcola la riduzione 3

modFr

2) se tale riduzione è = (n -1) (ciò equivale alla congruenza 3

 ^{-1 (mod F}

)) si esce con output “F

è primo”; in caso contrario si esce con output “F

è composto”.

Poiché si può utilizzare l’algoritmo della esponenziazione modulare, la complessità di tale test è di ordine O(x

), dove x=L(F

)=2

+1 (perché ₂

< F

< ₂

).

I numeri di Fermat F

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

^,

^,..., F

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

hanno una struttura particolare, per r>1.

Teorema.

Se r>1, per ogni divisore primo p di F

= ₂

+1 si ha p  ^{1 (mod 2}

), quindi p=1+k2

con k numero naturale.

Dimostrazione:

Per ipotesi p è divisore del numero dispari F

, quindi p è primo >2. Si ha ₂

 -1 (mod p).

Essendo 2, p coprimi si ha [2]Z

* , [ ] 2

=[-1]

= [1], e se s=ord([2]) in Z

* , s è divisore di 2

, quindi s=2

con d r+1. Dimostriamo che d=r+1. Se per assurdo fosse d<r+1, sarebbe:

_{[ ] 2}

= _{([ ] 2}

₎

= _{([ ] ) 2}

=[1]

ed essendo ₂

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

Dunque d=r+1, s=2

. Ma il s=ord([2]) è divisore della cardinalità p-1 di Z

* , p-1=2

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

 ^{1 (mod p),}

[2]

=[1], dunque s=ord([2]) è divisore di (p-1)/2, cioè (p-1)/2=hs=h2

con h naturale da cui

p-1=h2

cioè la tesi.

Per trovare un divisore primo di F

(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

è divisore di F

. Il minimo valore di k per cui p=1+k2

è divisore di F

fornisce con certezza un divisore primo p di F

(se p per assurdo non fosse primo, p avrebbe un divisore primo p

<p

ma p

sarebbe a maggior ragione divisore di F

, quindi sarebbe della forma p

=1+k

2

con k

<k, contro la minimalità di k).

Dopo avere trovato un divisore primo p di F

, si può ripetere il ragionamento sul numero F

/p per

trovare altri divisori primi di F

/p (e quindi di F

) e pervenire infine alla completa fattorizzazione di

F

in prodotto di primi.