(r) è la funzione di Eulero) si abbia: (x+a)

Lezione del 20 maggio 2008

Il test di primalità AKS si basa sul seguente risultato (di cui diamo solo l’enunciato):

Teorema AKS.

Siano n un intero >2, ed r un naturale coprimo con n, tale che ord

n>log

n (dove ord

n indica il periodo di [n] nel gruppo Z

*) . Supponiamo inoltre che per ogni intero a tale che 1a

n log (r) ₂



(dove

è la funzione di Eulero) si abbia:

(x+a)

x

+a (mod x

-1, n)

Allora: se n ha un fattore primo p>

, si ha che n è potenza di p.

Il test AKS si implementa nel modo seguente, dato in input un naturale n>1:

1) si testa se n è una potenza di base naturale con opportuno esponente naturale >1: in caso affermativo si esce con output “n è composto”, altrimenti si prosegue al passo successivo

2) Si cerca il minimo naturale r coprimo con n tale che ord

n>log

n

3) Se esiste un divisore d di n, con d<n, nell’intervallo [2,

] si esce con output “n è composto”

4) Se per ogni naturale a con 1a

si ha (x+a)

x

+a (mod x

-1, n) si esce con output

“n è primo”, altrimenti si esce con output “n è composto”

Verifichiamo prima di tutto che il test AKS è un test di primalità deterministico, quindi che un input n supera il test se e solo se n è primo.

Sia dunque n primo. Il passo 1) viene superato da n, in quanto n, essendo primo, non è potenza di base naturale con esponente naturale opportuno >1.

Il passo 3) viene superato da n in quanto n non ha divisori propri diversi da 1 e da n.

Infine nel passo 4) si esce certamente con output “n è primo” come conseguenza dell’implicazione () dell’ultimo teorema dimostrato (prima del Teorema AKS) in cui l’ipotesi a,n coprimi era superflua: infatti da tale implicazione hsegue (x+a)

x

+a (mod n) e dunque a maggior ragione (x+a)

x

+a (mod x

-1, n).

Viceversa se n è un input che fornisce output “n è primo”, dimostriamo che n è primo.

Per assurdo supponiamo che n superi il test AKS ma n non sia primo, e sia p un divisore primo di n, con p<n.

Poiché n supera il passo 1), si ha che n non è potenza di base naturale con esponente naturale >1.

Poiché n supera il passo 3), il divisore primo p è >

e per il Teorema AKS si conclude che n è potenza di p, con esponente naturale >1 (perché p<n), in contraddizione con il superamento del passo 1).

Il problema della complessità di calcolo del test AKS è interamente legato al naturale r trovato nel passo 2) (della cui esistenza ancora non siamo neanche formalmente certi).

Sarà utile il seguente risultato (di cui diamo solo l’enunciato):

Lemma AKS.

Se n>2 è un numero naturale, esiste un naturale rlog

n+1 coprimo con n, tale che ord

n>log

n (dove ord

n è il periodo di [n] nel gruppo moltiplicativo Z

*).

Dunque r esiste certamente, e inoltre il minimo r con le proprietà richieste è di ordine polinomiale

rispetto alla lunghezza binaria k dell’input n (perché n<2

, log

n<k, esiste rk

+1, e il minimo r è

dunque di ordine O(k

)).

Dimostriamo allora che il test di primalità AKS ha globalmente complessità polinomiale nella lunghezza binaria k dell’input n.

Abbiamo già visto in una lezione precedente che il passo 1) si esegue con complessità polinomiale, con un test che verifica se n è potenza di opportuna base naturale ed opportuno esponente >1. . La ricerca di r nel passo 2) si effettua facendo assumere ad r i valori successivi r=2,3…. e ad ogni valore testando se r,n sono coprimi (algoritmo Euclideo), e se il periodo di [n] nel gruppo Z

* è

>log

n (calcolando le potenze [n]

con 1ilog

n e verificando che nessuna coincida con [1]):

poiché come visto il numero di valori di r da testare (per trovare quello utile) è di ordine O(k

), anche questo passo 2) ha complessità polinomiale.

Nel passo 3), l’esistenza di un divisore d di n, con d<n, nell’intervallo [2,

] si effettua facendo assumere al naturale d tutti i valori in [2,

] e per ognuno testando se d é un divisore di n con d<n (il numero dei valori d da testare è <

<rlog

n<rk, quindi di ordine O(k

)).

Nel passo 4), per ogni naturale a con 1a

si testa se (x+a)

x

+a (mod x

-1, n) (il numero dei valori a da testare è come sopra di ordine O(k

)): tale congruenza si verifica calcolando le riduzioni modulo (x

-1, n) di ambo i membri (per il primo membro (x+a)

si usa l’esponenziazione modulare per i polinomi, di complessità polinomiale) e confrontando le riduzioni ottenute.

Poiché tutti i passi dell’algoritmo AKS sono di complessità polinomiale, lo stesso si può dire per l’intero algoritmo.

Algoritmi di fattorizzazione.

Sono algoritmi che, dato in input un naturale n>1, calcolano tutti i fattori primi di n: a tutt’oggi non è stato trovato un algoritmo di fattorizzazione di complessità polinomiale.

Un algoritmo di fattorizzazione in genere cerca di decomporre n nel prodotto n=ab, dove a,b sono naturali (non necessariamente primi) tali che 1<a,b<n (se a,b non esistono, si conclude che n è primo). Una volta trovati a,b l’algoritmo viene riapplicato separatamente ad a,b per decomporli ulteriormente (se possibile): dopo un numero finito di ripetute applicazioni dell’algoritmo, si perviene al calcolo dei fattori primi di n.

Ovviamente un algoritmo “ingenuo” di fattorizzazione consiste (come nel test ingenuo di primalità) nel testare, per ogni naturale a in [2,

], se a è divisore di n, e in caso affermativo porre b=n/a: il numero dei test da effettuare è di ordine esponenziale O(

) se k è la lunghezza binaria di n.

Questo algoritmo trova un fattore a di n in tempi di calcolo ragionevoli solo se n ha un fattore relativamente “piccolo”.

Illustriamo ora un algoritmo di fattorizzazione che invece è efficiente se n ha un fattore relativamente “grande”.

Algoritmo di fattorizzazione di Fermat.

Supponiamo l’input n dispari: non è una limitazione in un algoritmo di fattorizzazione perché se n è pari, con successive divisioni per 2 si può fattorizzare n nella forma n=2

m, con m dispari, e sostituire m al posto di n come input.

L’algoritmo si basa sul seguente risultato, il quale dimostra che fattorizzare n nel prodotto di 2 numeri naturali equivale sostanzialmente a rappresentare n come differenza di 2 quadrati:

Teorema (Fermat).

Sia n un naturale dispari, e siano:

S = { (a,b)NxN / ab, n=ab }

T = { (r,s)ZxZ / r>s0, n=r

-s

}

Allora la funzione f : S  T definita da f(a,b)=((a+b)/2,(a-b)/2) è biunivoca.

Dimostrazione:

Si verifica facilmente che f(a,b)T se (a,b)S.

Per dimostrare che f è biunivoca, basta costruire la funzione inversa: definiamo f

: T  S ponendo f

(r,s)=(r+s,r-s) (si verifica facilmente che f

(r,s)S se (r,s)T).

Si verifica infine che le composizioni ff

, f

f sono le funzioni identiche di T ed S.

Come conseguenza del teorema precedente, è possibile implementare un algoritmo di fattorizzazione: dato in input un intero dispari n>1, per trovare una fattorizzazione di n nel prodotto di 2 numeri naturali a,b, basta trovare una coppia (r,s)T (quindi r,s interi, r>s0, tali che n=r

-s

) e porre (a,b)=f

(r,s)=(r+s,r-s) (vedere la dimostrazione della surgettività di f nel teorema).

Per trovare una coppia (r,s)T, possiamo fissare un intero r>0, e cercare un intero s0 tale che si abbia r

-n=s

: se r

-n =0 allora s=0, n=r

, a=b=r; se invece r

-n >0 si può usare il test già esaminato in precedenza per verificare se il numero naturale r

-n è un quadrato perfetto di base naturale opportuna s.

Dovendo essere r

-n=s

0, si ha r

, dunque il valore minimo da fissare per r è r=

.

Per quanto riguarda il valore massimo di r, notiamo che al crescere di r, cresce il valore corrispondente di a (se esiste) nella coppia (a,b): se r

>r, e se n=r

-s

=r

-s

, allora s

>s, dunque a=r+s<a

=r

+s

. Poiché in una fattorizzazione non banale di n (dispari) certamente é an/3 (perché n=ab con b3), e ricordando che r=(a+b)/2, si ottiene che il valore massimo per r è la parte intera di [(n/3)+3]/2=(n+9)/6.

Dunque, l’algoritmo di fattorizzazione di Fermat si può implementare nel modo seguente:

- input n intero dispari >1

- per r=

, 

 +1,……, (n+9)/6 si testa se r

-n è un quadrato perfetto di base s0 e in caso affermativo si esce con output “n=ab dove a=r+s, b=r-s”

- se nel ciclo precedente nessun test ha avuto esito positivo, si esce con output “n è primo”

Notiamo che ogni passo del ciclo ha complessità polinomiale (test del quadrato perfetto già illustrato in una lezione precedente), ma il numero dei passi è maggiorato da funzioni esponenziali nella lunghezza binaria k di n (perché n<2

,

<

).

Notiamo anche, come già premesso, che il test di Fermat trova un fattore non banale di n in tempi ragionevoli se n ha un fattore abbastanza “ grande” cioè 

, perché in tale caso, se n=ab, anche b

, dunque r=(a+b)/2

, ossia il valore r che nel ciclo permette di trovare la fattorizzazione di n è “vicino” alla radice quadrata di n, e dunque (partendo dal valore iniziale r=

) tale valore viene trovato relativamente “presto”.

Esempio.

Se l’input é n=6077, 

=78, (n+9)/6=1014, il ciclo si dovrà eseguire per r=78, 79,…., 1014 e si ha:

r=78  r

-n =7 (non quadrato) r=79  r

-n =164 (non quadrato) r=80  r

-n =323 (non quadrato) r=81  r

-n =484 =22

ottenendo la fattorizzazione n=ab dove a=r+s=81+22=103, b=r-s=81-22=59.

Algoritmo di fattorizzazione  di Pollard.

Premettiamo alcune considerazioni su un argomento di Calcolo delle Probabilità.

Siano n,m numeri naturali con 1<n<m, S un insieme finito di cardinalità m e sia data una successione finita di n termini scelti in S (anche non distinti):

a

, a

, ……, a

in modo che gli a

siano scelti random in modo “uniforme” (dal punto di vista della probabilità) fra gli elementi di S (nel senso che per ogni indice i, ogni elemento dell’insieme S ha la stessa probabilità di essere scelto come elemento a

).

Calcoliamo la probabilità che almeno 2 degli elementi della successione coincidano.

Calcoliamo dapprima la probabilità che tutti gli elementi della successione siano distinti.

Fissato a

, la probabilità che a

sia diverso da a

è (m-1)/m; fissati a

,a

distinti, la probabilità che a

sia diverso da a

e da a

è (m-2)/m , quindi la probabilità che a

, a

, a

siano tutti distinti è il prodotto [(m-1)/m][(m-2)/m]=(1-1/m)(1-2/m)

Iterando il ragionamento si ottiene che la probabilità che a

, a

, ….., a

siano tutti distinti è il prodotto:

(1-1/m)(1-2/m)……(1-(n-1)/m).

Dallo sviluppo in serie e

=1+x+x

/2!+…, possiamo approssimare 1+x con la funzione e

, di modo che ogni fattore del prodotto precedente è approssimato (ponendo x= -i/m con i=1,….,n-1) dalla funzione e

. Dunque il prodotto è approssimato dalla funzione

(tenendo conto che la soma 1+2+….+(n-1) coincide con n(n-1)/2): per n “grande” possiamo approssimare n(n-1) con n

, di modo che la probabilità che tutti gli elementi della successione siano distinti è approssimata dalla funzione

e^

e dunque la probabilità che almeno 2 degli elementi a

, a

, ….., a

coincidano è (con approssimazione) la seguente funzione di n,m:

p(n,m) 

Se allora fissiamo un valore di probabilità p con 0<p<1, il numero n degli elementi di una successione per i quali sia p la probabilità che fra essi almeno 2 coincidano è approssimativamente:

n 

In particolare per esempio se fissiamo una probabilità del 50% (p=0.5), si ottiene n  1,77

, mentre se se fissiamo una probabilità del 90% (p=0.9), si ottiene n  2,14

.

Dunque se scegliamo in successione in modo “random” elementi dell’insieme S:

a

, a

, a

, ………..

il minimo indice n per cui l’elemento a

coincide con almeno uno degli elementi che lo precedono è, dal punto di vista probabilistico, di ordine O(

).

Un’applicazione di tale teoria é appunto il cosiddetto “paradosso dei compleanni”: se sono scelte random un numero n di persone con 1<n<365, la probabilità che almeno 2 fra esse compiano gli anni nello stesso giorno e mese dell’anno è 

; inoltre, fissato un valore di probabilità p con 0<p<1, il numero n di persone (scelte random) per le quali la probabilità che fra esse almeno 2 compiano gli anni nello stesso giorno e mese dell’anno è 

(tutto questo supponendo che giorno e mese di nascita degli esseri umani siano distribuiti in modo uniforme fra i 365 giorni dell’anno, il che non è vero in pratica).

Per esempio se la probabilità fissata è del 50% (p=0,5), n 

 23: scegliendo 23 persone in modo random, la probabilità che fra esse almeno 2 compiano gli anni nello stesso giorno e mese dell’anno è  50% (abbastanza paradossale…..).

Scegliendo invece 50 persone in modo random, la probabilità che almeno 2 fra esse compiano gli

anni nello stesso giorno e mese dell’anno è addirittura  97%.