Lezione del giorno 23 aprile 2008 Teorema di Eulero-Fermat.

Teoria dei numeri

Lezione del giorno 23 aprile 2008 Teorema di Eulero-Fermat.

Siano a,n due naturali coprimi (con n>1). Allora a

1 (mod n).

Dimostrazione:

Il gruppo commutativo finito G= Z

* ha cardinalità (n), ed essendo a,n coprimi, si ha [a]G.

Per un risultato dimostrato in precedenza, ogni elemento di un gruppo finito commutativo elevato alla cardinalità del gruppo dà come risultato l’elemento neutro: nel nostro caso si ha [1]=[a]

=[a]

[a]….[a]=[aa….a]=[a

], da cui la tesi.

Corollario (Piccolo Teorema di Fermat).

Se n è un numero primo, per ogni naturale a non multiplo di n si ha a

1 (mod n).

Dimostrazione:

Essendo a non multiplo del primo n, i numeri a,n sono coprimi (perché le uniche possibilità per il mcd(a,n) sono 1, n). Poiché (n)=n-1 (perché n è primo) la tesi segue dal Teorema di Eulero- Fermat.

Test di primalità.

Un test di primalità è un algoritmo tale che, dato in input un numero naturale n>1, produca un output “n è primo” oppure “n è composto” (definendo composto un naturale >1 non primo).

Si distinguono:

- test di primalità deterministici: non vi sono elementi casuali nell’algoritmo, e l’output è “n è primo” se e solo se l’input n è un numero primo

- test di primalità probabilistici: nell’algoritmo vi è la scelta casuale di alcuni elementi, e inoltre se l’input n è un numero primo allora l’output è sempre “n è primo” (tutti i numeri primi superano il test), ma se n è composto, l’output può essere sia “n è primo” sia “n è composto”, e la probabilità che l’output sia “n è primo” (pur essendo n composto) è maggiorata da una costante C<1, indipendente dall’input n e dagli elementi casuali. Se un input n>1 supera un test di primalità probabilistico un numero k di volte (con gli elementi casuali scelti ogni volta in modo indipendente), la probabilità che il numero n sia composto si può rendere piccola a piacere (se il numero di test k è abbastanza grande), quindi si può accettare che n sia effettivamente primo, con una bassa percentuale di errore.

Il primo test ingenuo di primalità è il test (deterministico) che verifica, per d=2,….,n-1, se esiste un d divisore non banale di n: se d esiste l’output è “n è composto”, se d non esiste l’output è “n è primo”:

1) in input il naturale n>1

2) per d=2,…..,n-1 si calcola il resto r della divisione di n per d: se per qualche d si ha r=0 (dunque d è divisore non banale di n) si si esce con output “n è composto”; altrimenti si esce con output “n è primo”.

L’algoritmo si implementa effettuando alcune divisioni di n per numeri naturali d<n (ognuna di complessità polinomiale O(k

) se k=L(n) è la lunghezza binaria dell’input n), ma il numero di tali divisioni è <n<2

(perché n ha k cifre binarie) dunque il numero delle divisioni è di ordine esponenziale O(2

): quindi è un algoritmo di complessità esponenziale .

Questo test si può rendere più efficiente osservando che se esiste un divisore non banale del numero

composto n, allora esiste certamente un divisore non banale di n che sia  n (infatti se per assurdo

fosse n=bc con b,c> n , si avrebbe n>( n )

=n, contraddizione). Quindi nel test precedente si può

limitare la ricerca ai valori d con 2d n : il numero di divisioni è < n = n

<

, quindi è di ordine O

e anche tale algoritmo (sebbene più efficiente) ha complessità esponenziale.

Un altro test di primalità deterministico segue dal:

Teorema di Wilson.

Sia n> 1 un naturale . Allora: n è primo  (n-1)!-1 (mod n).

Dimostrazione:

(): Consideriamo il gruppo moltiplicativo Z

* . Se n è primo, n è coprimo con tutti i numeri 1,2,

…,n-1 (perché non sono multipli di n), dunque Z

* = {[1], [2], ….., [n-1]}.

Calcoliamo il prodotto di tutti gli elementi di tale gruppo:

[1][2] …..[n-1] = [12 …..(n-1)] = [(n-1)!].

In tale prodotto, sfruttando la proprietà commutativa, possiamo accoppiare ogni elemento [i] con il suo inverso [i]

(nel caso in cui [i][i]

) ottenendo per ogni tale coppia il prodotto =[1]: al termine di tale semplificazione il prodotto precedente si riduce a quello dei soli fattori [i] tali che [i]=[i]

, cioè tali che [i]

=[i

]=[1].

Ma per un tale i si ha n(i

-1), n(i+1)(i-1), quindi (essendo n primo) n(i+1) oppure n(i-1), ossia i1 (mod n) oppure i-1 (mod n). Si conclude che:

[(n-1)!]=[1][-1]=[-1] , da cui la tesi.

(): Sia (n-1)!+1=kn, con k intero. Se per assurdo esistesse un divisore non banale d di n, con 1<d<n, tale d sarebbe divisore di 1=kn-(n-1)! (perché d è uno dei fattori del prodotto (n-1)!) contraddizione perché d>1.

Nota: la condizione (n-1)!-1 (mod n) del Teorema di Wilson equivale a (n-1)!modn=(n-1) (in quanto -1(n-1) (mod n)).

Il Teorema di Wilson permette di costruire un test di primalità deterministico:

1) in input il naturale n>1

2) si costruisce la la successione y

,y

y

ponendo y

=1, e per i>1 y

=(iy

)modn, ottenendo alla fine il valore y

=(n-1)!modn: se y

=(n-1) si esce con output “n è primo”; altrimenti si esce con output “n è composto”.

Nel passo 2), il calcolo di (n-1)!modn comporta l’esecuzione di operazioni (prodotti e riduzioni modulo n) in numero <n< ₂

dunque in numero di ordine O(2

) se k=L(n), ed anche questo algoritmo ha complessità esponenziale.

Esporremo in seguito l’unico test di primalità di complessità polinomiale attualmente esistente: il test AKS (Agrawal, Kayal, Safena 2002).

Esaminiamo ora alcuni test di primalità probabilistici.

Il primo è il cosiddetto test di Fermat (basato sul Piccolo Teorema di Fermat): in effetti esso non è un test probabilistico a tutti gli effetti, perché vedremo che la probabilità che un numero composto superi (erroneamente) il test è maggiorata da una costante, ma ciò avviene per tutti i i numeri composti tranne che per particolari valori dell’input (i cosiddetti numeri di Carmichael).

I passi dell’algoritmo sono:

1) in input il naturale n>1

2) si sceglie casualmente un intero a con 1an-1 (detto base)

3) si calcola d=mcd(a,n); se d>1 si esce con output ”n è composto”

4) se d=1 si calcola la riduzione x=a

modn e se x1 si esce con output ”n è composto”; altrimenti si esce con output “n è primo”

Osserviamo prima di tutto che ogni input n primo supera il test: se 1an-1, certamente a non è

multiplo di n e quindi nel passo 3) si ha d=1; per il Piccolo Teorema di Fermat si ha allora x=1 e

quindi nel passo 4) si esce con output “n è primo”.