Teoria dei numeri Lezione del giorno 29 aprile 2009 Abbiamo dimostrato il seguente: Teorema di Proth-Pocklington. Sia n>1 un naturale dispari, e sia 2

(1)

Teoria dei numeri

Lezione del giorno 29 aprile 2009 Abbiamo dimostrato il seguente:

Teorema di Proth-Pocklington.

Sia n>1 un naturale dispari, e sia 2^m la massima potenza di 2 che divide il numero pari n-1, in modo che sia n-1=2^mh con h naturale dispari. Se 2^m>h si ha:

n è primo  esiste un naturale a, con 1an-1, tale che a^(n-1)/2-1 (mod n)

Possiamo notare che il teorema fornisce un test di primalità deterministico (ma solo per un input n dispari tale che n-1=2^mh con h naturale dispari e con 2^m>h): tuttavia il test non ha complessità polinomiale, perché, benché testare la congruenza a^(n-1)/2-1 (mod n) sia equivalente a testare che a^(n-

1)/2modnn-1 (test che si può effettuare con complessità polinomiale servendosi dell’algoritmo di l’esponenziazione modulare), la ricerca dell’esistenza di un valore a che soddisfi tale congruenza ha complessità esponenziale (il numero dei valori possibili di a è <n<2^k se k=L(n)=lunghezza binaria di n).

Esamineremo però in seguito il caso particolare in cui il numero n>1 dispari sia tale che n-1=2^mh ma con h=1 (cioè il caso n=2^m+1), ossia il caso in cui il numero n sia un numero di Fermat: in questo caso è ovvio che 2^m>h=1, quindi si può applicare il Teorema di Proth-Pocklington, e vedremo in seguito che in tal caso basta verificare la condizione del teorema solo per a=3 per concludere con certezza che n è primo.

Otterremo quindi un test di primalità deterministico di complessità polinomiale (detto criterio di Pepin) valido solo per i numeri della forma n=2^m+1 (i numeri di Fermat).

Studiamo dunque i numeri naturali dispari n>1 della forma n=2^m+1, con m>0.

Fermat dimostrò che:

Teorema.

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

Dimostrazione:

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

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

Per assurdo supponiamo n=2^m+1 primo, e l’esponente m non potenza di 2. Se 2^r (con r0) è la massima potenza di 2 che divide r (al limite r=0), si ha m=2^rs, con s>1, s dispari.

Dall’identità algebrica precedente, con x=₂⁽²^r⁾, y=-1, si ha n=₂⁽²^r^)s+1 multiplo di x-y=₂⁽²^r⁾+1:

tale divisore di n è >1 (perché ₂⁽²^r⁾>0) ed è <n (perché 2^rs>2^r, essendo s>1), in contraddizione con l’ipotesi che n è primo.

Visto il risultato precedente, studieremo solo i numeri di Fermat della forma Fr = ₂⁽²^r⁾+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 Fr = ₂⁽²^r⁾+1 fosse primo.

In effetti per r<5 i valori F0=3, F1=5, F2=17, F3=257, F4=65.537 sono numeri primi.

Ma per r=5 il numero F5=4.294.967.297 non è primo, essendo divisibile per il numero primo 641.

(2)

Quindi Fermat si sbagliava: inoltre a tutt’oggi per nessun r5 si è trovato un Fr che sia primo, e si congettura che un tale Fr non esista (F33 è 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 Fr, dobbiamo però introdurre il concetto di resto quadratico modulo un numero primo.

Resti quadratici.

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

Si ha allora a,p coprimi, dunque [a] appartiene al gruppo moltiplicativo Zp* degli elementi invertibili di Zp.

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] Zp* e si ha [a]=[b²]=[b]²: in pratica a è resto quadratico modulo p se e solo se [a] è un quadrato perfetto in Zp* (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 Z7* = {[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 Z2*={[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^(p-1)/21 (mod p) Dimostrazione:

() Per ipotesi esiste [b]  Zp* tale che [a]=[b]². Per il Piccolo Teorema di Fermat si ha:

[1]=[b]^p-1=[a]^(p-1)/2 e si ottiene la tesi.

() Per il Teorema di Gauss, il gruppo Zp* è ciclico, generato da un elemento [x] di periodo uguale alla cardinalità (p-1) di Zp*.

Ogni elemento di Zp* è potenza di [x], e in particolare [a]=[x]^t .

Per ipotesi si ha [1]=[a]^(p-1)/2=([x]^(p-1)/2)^t=[x]^t(p-1)/2, dunque t(p-1)/2 è multiplo del periodo (p-1) di [x], cioè t è multiplo di 2, t=2k, da cui ([x]^k)²=[x]^t=[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à polinomiale (utilizzando l’esponenziazione modulare per verificare se a^(p-1)/2modp=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^(p-1)/2 ? Per il Piccolo Teorema di Fermat si ha (a^(p-1)/2)²1 (mod p), dunque, per una proprietà già osservata durante il test di Rabin-Miller, si ha a^(p-1)/21 (mod p), e per il criterio di Eulero si conclude che a^(p-1)/2-1 (mod p).

Quindi la situazione è la seguente:

a è resto quadratico modulo p  a^(p-1)/21 (mod p)

(3)

a non è resto quadratico modulo p  a^(p-1)/2-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^(p-1)/2(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)^(p-1)/2a^(p-1)/2b^(p-1)/2(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) è impossibile 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 >1 non multiplo di p, e fattoriziamo a in prodotto di potenze di primi distinti:

a = p₁^k¹p₂^k²....p_r^k^r (notare che ogni pi p dunque pi non è multiplo di p, ed esiste (pi/p)) Per la 2) si ha :

(a/p) = 

 r

1 i

i/p)kⁱ (p

Ma nella formula precedente: se ki è pari (p_i/p)^kⁱ = (1)^kⁱ =+1, e se ki è dispari (p_i/p)^kⁱ =(pi/p), dunque in totale si ha :

(a/p) = ^_

r

k i1

i

/p) (p dispari

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