 ])p11(730[log  ])p11(2m[log

Teoria dei numeri

Lezione del giorno 18 maggio 2009

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 _e ^{ n (} _2m ^{n - 1)} (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 _2m ⁿ

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} ^ _2m ⁿ

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  ^2m[log

⁽ ₁  ¹ _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, di ordine 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  e} ^ ₇₃₀ ⁿ

; 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 è  ^730[log

⁽ ₁  ¹ _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

= ₂ ^{( 2}

⁾ +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.

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

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

a

=s; a

=F(a

) per ogni k>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 k 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 (b

=b

con j<k) è dal punto di vista probabilistico di ordine O(S

)=O(p

).

Se b

=b

con j<k, allora b

=b

(perché b

=a

modp=F(a

)modp=F(a

modp)=F(b

)= F(b

)=b

);

analogamente si ha b

=b

e in generale (per induzione):

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

Analogamente si ha b

= b

e in generale (per induzione):

b

=b

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

Poiché i+t(k-j) rappresenta il generico indice ri che sia congruo i modulo (k-j) otteniamo il seguente risultato:

comunque presi due indici i,rj, se ir (mod k-j) allora b

=b

.

In pratica la successione b

diventa ciclica con “periodo” k-j, nel senso che dal termine di indice j in poi i termini coincidono ogni k-j posizioni.

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