• Non ci sono risultati.

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

N/A
N/A
Protected

Academic year: 2021

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

Copied!
1
0
0

Testo completo

(1)

Teoria dei numeri

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

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

(n)

1 (mod n).

Dimostrazione:

Il gruppo commutativo finito G= Z

n

* 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]

(n)

=[a]

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

(n)

], 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

n-1

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

2

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

k

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

k

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

2

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

(2)

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

1/2

<

( 2)k

, quindi è di ordine O

( 2k)

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

n

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

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

n

* = {[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]

-1

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

-1

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

-1

, cioè tali che [i]

2

=[i

2

]=[1].

Ma per un tale i si ha n(i

2

-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

1

,y

2,…,

y

n-1

ponendo y

1

=1, e per i>1 y

i

=(iy

i-1

)modn, ottenendo alla fine il valore y

n-1

=(n-1)!modn: se y

n-1

=(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< 2

k

dunque in numero di ordine O(2

k

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

(3)

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

n-1

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

Riferimenti

Documenti correlati

Il numero dei valori possibili per la scelta dell’elemento casuale a nel test è (n-1); vediamo come possiamo valutare il numero dei valori a per i quali il test è superato, cioè

Dato un qualunque grafo semplice non orientato G, si chiama grafo duale di G il grafo semplice non orientato G’ che ha gli stessi vertici di G, ma nel quale due vertici distinti

Inserire le risposte negli spazi predisposti, accompagnandole con spiegazioni chiare e sintetiche.. NON SI ACCETTANO RISPOSTE SCRITTE SU

Il Signor Carlo scende dal tram all'incrocio di via Pietro Micca con via Antonio Giuseppe Bertola (nella mappa che vedi sotto il punto è contrassegnato da un

Dunque il problema si è ridotto alla risoluzione dell'equa- zione lineare 7x – 45y=1 in Z, più precisamente dobbiamo trovare una sua soluzione (a,b)∈ ZxZ.. (in pratica poi

Determinare quali sono i possibili numeri formati dalle due ultime cifre di N nel caso in cui N sia divisibile per 25.. Provare facendo uso della teoria della congruenza

Furthermore, it seems natural that in studying such primes we will eventually cross path with their counterpart, namely the elite primes modulo which all large enough F n are

Le coppie contigue dei tre angoli retti insistono sugli stessi archi, generando quaterne di colonne cocircolari: non ce ne sono altri dato che il trapezio in figura non ` e isoscele