)3(1

(1)

Teoria dei numeri

Lezione del giorno 28 aprile 2008

Abbiamo descritto il test di primalità di Fermat:

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

^n-1

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

Abbiamo anche già dimostrato che un input n primo supera il test.

Osserviamo ora che il test ha complessità polinomiale O(k

³

) se k=L(n): infatti il passo 2) si effettua con l’algoritmo Euclideo, il passo 3) con l’algoritmo dell’esponenziazione modulare.

Un numero composto supera il test quando: nel passo 3) si ha d=mcd(a,n)=1 (ossia se la base casuale a è un numero coprimo con n) e nel passo 4) si ha x=a

^n-1

modn=1.

Un input composto n che superi il test di Fermat relativamente alla scelta della base a è detto pseudoprimo nella base a (perché n “finge” di essere primo, superando il test per quella scelta di a): per quanto osservato sopra ciò equivale ad affermare che:

mcd(a,n)=1, a

^n-1

modn=1 (con 1an-1) Esempio.

Sia n=341. Sottoponiamo n al test di Fermat con la base a=2. E’ facile verificare che mcd(341,2)=1.

Inoltre 2

³⁴⁰

mod341=1 (come già calcolato nell’esempio di applicazione dell’esponenziazione modulare). Dunque n=341 é pseudoprimo nella base a=2, poiché supera il test per tale scelta di a.

Proviamo il test con la base 3 (si ha mcd(341,3)=1): analogamente a quanto fatto nel caso a=2, con l’esponenziazione modulare si ha

y

1

= (1

²

3

^a⁸

) mod341=3 ;y

2

= (3

²

3

^a⁷

) mod341=9 ;y

3

= (9

²

3

^a⁶

) mod341=243;

y

4

= (243

²

3

^a⁵

) mod341=56 ;y

5

= (56

²

3

^a⁴

) mod341=201 ;y

6

= (201

²

3

^a³

) mod341=163 ;

y

7

= (163

²

3

^a²

) mod341=254 ;y

8

= (254

²

3

^a¹

) mod341=67 ;y

9

= (67

²

3

^a⁰

) mod341=56=2

³⁴⁰

mod341 Poiché 2

³⁴⁰

mod3411, n=341 non supera il test nella base a=3, dunque é composto: in effetti 341=1131 .

Calcoliamo un maggiorante per la probabilità che un numero composto n superi il test di Fermat.

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è il numero delle possibili basi in cui n è pseudoprimo:

Teorema.

Sia n un numero naturale, e supponiamo che esista almeno un naturale b, con 1bn-1, mcd(b,n)=1, tale che b

^n-1

modn1. Allora il numero dei naturali a tali che 1an-1, mcd(a,n)=1, a

^n-1

modn=1 (cioè il numero delle basi in cui n è pseudoprimo) è (n)/2.

Dimostrazione.

(2)

Sia S = {aN / 1an-1, mcd(a,n)=1, a

^n-1

modn=1}, e sia b come nell’enunciato. Al variare di aS, consideriamo l’insieme T delle riduzioni modulo n dei prodotti ab:

T = { (ab)modn / aS }

Tali elementi in T, al variare di aS, sono distinti: infatti se per assurdo (ab)modn=(cb)modn con a,cS distinti, si avrebbe nel gruppo moltiplicativo Z

n

* [a][b]=[c][b], e per la legge di cancellazione [a]=[c], contraddizione perché a,c sono distinti nell’intervallo [1,n-1], quindi le classi di congruenza [a],[c] sono distinte. Dunque S,T hanno stessa cardinalità.

Gli elementi di T sono coprimi con n : se t=(ab)modnT, allora in Z

n

si ha [t]=[a][b] Z

n

* perché [a],[b] Z

n

*, dunque mcd(t,n)=1. Inoltre gli elementi di T sono nell’intervallo [1,n-1] (perché riduzioni modulo n).

Per ogni t=(ab)modnT, si ha t

^n-1

a

^n-1

b

^n-1

b

^n-1

quindi t

^n-1

modn=b

^n-1

modn1, ossia tS. Dunque S,T sono insiemi disgiunti, entrambi contenuti nell’insieme dei naturali dell’intervallo [1,n-1] coprimi con n: dunque la cardinalità di S è  della metà del numero di questi naturali cioè è (n)/2, come si voleva dimostrare.

Dal Teorema precedente segue che, se n è un naturale composto, e se soddisfa le ipotesi del Teorema precedente, la probabilità che n superi il test di Fermat (per una scelta casuale della base a) è 1/2. Infatti il numero dei valori a (compresi fra 1 ed n-1) per cui n supera il test è (n)/2(n- 1)/2, e la probabilità che a sia scelto casualmente fra questi valori è allora [(n-1)/2]/(n-1)=1/2.

Ripetendo k volte il test, ogni volta con una scelta casuale indipendente del valore della base a, la probabilità che un numero composto (soddisfacente le ipotesi del Teorema) superi tutte le volte il test di Fermat è 1/2

^k

, quindi tale probabilità può essere resa piccola a piacere (per k sufficientemente grande).

Per esempio se k=100 tale probabilità è 1/2

¹⁰⁰

1/10

³⁰

.

Dunque se l’input n supera k volte il test di Fermat, con k abbastanza grande, possiamo affermare che n è primo, con una probabilità di errore molto bassa, eccetto che nel caso in cui n sia un numero composto che non soddisfa le ipotesi del Teorema precedente.

Problema: cosa avviene se il numero naturale n composto non soddisfa le ipotesi del Teorema precedente ? Esistono tali numeri n ?

Per un naturale n composto che non soddisfa le ipotesi del Teorema precedente si ha che non esiste nessun naturale b, con 1bn-1, mcd(b,n)=1, tale che b

^n-1

modn1, dunque per ogni intero a tale che 1an-1, mcd(a,n)=1, si ha sempre a

^n-1

modn=1. Quindi n è pseudoprimo in tutte le basi a tali che 1an-1, mcd(a,n)=1, che sono in numero di (n).

Per un tale n, la probabilità che n superi il test è (n)/(n-1) , e se usiamo la formula per calcolare

(n) conoscendo i fattori primi distinti p

1

,p

2

,…,p

r

di n, otteniamo che tale probabilità è :

(n)/(n-1)  (n)/n =(1-1/p

1

)(1-1/p

2

)...(1-1/p

r

)

Se i fattori primi p

i