log)( nr log)( nr

Teoria dei numeri e Crittografia: lezione del 17 maggio 2011

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

E’ fondamentale il seguente risultato (di cui diamo solo l’enunciato):

Lemma AKS.

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

n)

 coprimo con n, tale che ord

n>(log

n)

(ricordiamo che per ogni numero reale x il simbolo x indica il “tetto” di x, ossia il minimo intero che sia ³ x).

Dunque il naturale r di cui si parla nel passo 2) esiste certamente, e inoltre il minimo r con le proprietà richieste è  x

dove x=L(n) (ciò segue da n<2

, log

n<x, r<(log

n)

+1< x

+1).

Dimostriamo allora che il test di primalità AKS ha globalmente complessità non superiore alla polinomiale nella lunghezza binaria x dell’input n: in pratica dimostriamo che ognuno dei passi può essere eseguito con un algoritmo di complessità non superiore alla polinomiale.

Abbiamo già visto in una lezione precedente che il passo 1) si esegue con complessità non superiore alla 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 ord

n=ord([n]

)>(log

n)

: per quest’ultima verifica si calcolano le potenze [n

]

(esponenziazione modulare) con 1 i (log

n)

e verificando per ogni i che nessuna coincida con [1]). Poiché (conseguenza del Lemma AKS) il numero di valori di r da testare (per trovare quello utile) è  x

anche questo passo 2) ha complessità non superiore alla 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 è <n ed è un divisore di n (algoritmo della divisione): il numero dei valori d da testare è < 

<

r

x < x

x < x

, dunque anche questo passo 3) ha complessità non superiore alla polinomiale.

Infine nel passo 4), per ogni naturale a con 1 a  

si testa se è valida la congruenza:

(x+a)

mod(x

-1) (x

+a)mod(x

-1) (mod m)

Ognuna di tali congruenze riguarda polinomi di grado < r, quindi equivale alla verifica di un numero < r di congruenze aritmetiche, dove r x

(come osservato sopra).

Infine il numero di tali congruenze è  

< r

x < x

x < x

dunque anche questo passo 4) ha complessità non superiore alla polinomiale.

Nota: nonostante il test AKS sia di complessità “efficiente”, i suoi tempi di esecuzione , per input molto grandi, sono alti, e lo rendono non applicabile dal punto di vista pratico.

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à non superiore alla polinomiale.

Un algoritmo di fattorizzazione in genere cerca ottenere un obiettivo intermedio: decomporre l’input 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 con 2 a 

, se a è divisore di n, e in caso affermativo porre n=

ab (dove b=n/a): il numero dei test da effettuare è però di ordine esponenziale O( ₂

) se x=L(n) è la lunghezza binaria di n (perché 2

 x< 2

dunque

 n <

).

Questo algoritmo trova un divisore 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 è prodotto di 2 divisori relativamente “grandi” e “vicini fra loro”.

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

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 un algoritmo (già esaminato in una delle precedenti lezioni) 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³ n , dunque il valore minimo da fissare per r è r= n . (è il cosiddetto “tetto” di n , ossia il minimo intero ³ n ).

Per quanto riguarda il valore massimo di r, notiamo che al crescere di r, cresce il valore di s (se

esiste) perché r

-n=s

con n costante, dunque cresce il corrispondente valore di a=r+s (se esiste)

nella coppia (a,b). Poiché a³b, n=ab, in una fattorizzazione non banale di n (dispari) il valore

(teorico) minimo di b è b=3, in corrispondenza del quale il valore (teorico) massimo di a è a=n/3:

poichè r=(a+b)/2, si ottiene che il valore massimo (teorico) per r è [(n/3)+3]/2=(n+9)/6, dunque si può limitare la ricerca di r a valori (n+9)/6 .

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

- input n intero dispari >1

- per r= n ,  n  +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”

La complessità di tale algoritmo di Fermat è alta: il numero di valori r da testare è di ordine:

O((n+9)/6- n )=O(n)=O(2

) se x=L(n)

anche se ogni singolo test per verificare se r

-n è un quadrato perfetto si può effettuare con l’algoritmo visto in una lezione precedente, di complessità  O(x

) .

Notiamo anche, come già premesso, che il test di Fermat trova un fattore non banale di n in tempi ragionevoli se n è prodotto di 2 divisori a,b abbastanza “vicini fra loro” perché in tale caso a,b  n , dunque r=(a+b)/2 n , ossia il valore r che nel ciclo permette di trovare la fattorizzazione di n è

“vicino” a n , e dunque (partendo dal valore iniziale r= n ) 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!+x

/3!+…, poiché x

/2!+x

/3!+…0 per x che diverge,

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

e

(tenendo conto che 1+2+….+(n-1)=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

n

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)  1

e



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  1

2 [log ( )]

e

1

m  p

In particolare per esempio se fissiamo una probabilità del 50% (p=0.5), si ottiene n  1,77 m , mentre se se fissiamo una probabilità del 90% (p=0.9), si ottiene n  2,14 m .

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 con probabilità alta a piacere, di ordine O( m )=O(m

).

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 è  1

n

e

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

730[log ( )]

e

1

 p

(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  ^{730[log 2]}

 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%.

Introduciamo ora l’ Algoritmo di fattorizzazione  di Pollard.

Tale algoritmo (1975) ha avuto il suo più grande successo nel 1980, quando ha permesso di calcolare la fattorizzazione del numero di Fermat F

=

+1 (di cui con il test di Pepin si era già dimostrata la non primalità), trovando un fattore (primo) di 16 cifre, con un cofattore di 62 cifre (che nel 1981 è stato dimostrato primo anch’esso).

Il metodo  di Pollard si basa sulle seguenti considerazioni.

Supponiamo di volere fattorizzare un numero intero n>1, cercando un divisore non banale di n (se esiste, cioè se n non è primo).

Sappiamo che n ha certamente un divisore primo p n , e formalmente (pur non conoscendo p a priori) consideriamo gli insiemi:

S={0,1,2,…,p-1} T={0,1,2,…,n-1}S

Sia poi F: T  T una funzione che soddisfa: F(xmodp)=F(x)modp per ogni xT (vedremo in seguito scelte opportune per F ) .

Fissato un elemento sT (seme), costruiamo una successione a

di elementi di T (con i=0,1,2,….) ponendo induttivamente:

a

=s; a

=F(a

) per ogni i>0

(in pratica a partire dal seme s, si applica successivamente più volte F per ottenere i termini seguenti)

In corrispondenza (utilizzando le riduzioni modulo p) possiamo costruire una successione b

di elementi di S ponendo b

=a

modp .

Ora supponiamo che gli elementi di S siano distribuiti in modo uniforme (dal punto di vista probabilistico) nella successione b

(cioè che per ogni i la probabilità che un elemento di S coincida con b

sia uguale per tutti gli elementi).

Per le considerazioni svolte in precedenza (paradosso dei compleanni), il minimo indice k per cui b

coincide con uno dei termini che lo precedono (cioè b

=b

per un opportuno j<k) è dal punto di vista probabilistico di ordine O(S

)=O(p

).

Poichè b

=a

modp=F(a

)modp=F(a

modp)=F(b

), e analogamente b

=F(b

), da b

=b

segue b

=b

. Per induzione si ottiene facilmente:

b

=b

per ogni m³0 (*)

Se fissiamo un qualunque indice i³j si ha allora, applicando la (*) con m=i-j):

b

=b

=b

=b

Per induzione si ottiene facilmente:

b

=b

per ogni t³0 (fissato l’indice i³j)

Comunque presi allora due indici i,r con i,r³ j, se ir (mod k-j) si ha b

=b

(in pratica la successione b

dall’indice j in poi diventa ciclica con “periodo” k-j, nel senso che dal termine di indice j in poi i termini coincidono ogni k-j posizioni): infatti basta porre (se per esempio r³i)

(r-i)=t(k-j) con t³0

e da quanto precede segue appunto b

=b

=b

Esempio:

se j=3, k=9, la successione diventa ciclica con periodo 6 dal termine di indice 3 in poi: infatti dall’indice j=3 in poi, due qualunque termini della successione, i cui indici differiscano per un multiplo di k-j=6 (cioè i cui indici siano congrui modulo 6), coincidono fra loro.

Rappresentando graficamente la situazione, si ottiene (per j=3, k=9):

b

=b

=b

=….

b

=b

=b

=…. b

=b

=b

=….

b

b

=b

=b

=….

b

b

=b

=b

=….

b

b

Notare la forma geometrica che richiama la struttura della lettera greca  (da cui il nome

dell’algoritmo).