Introduciamo ora l’ Algoritmo di fattorizzazione r di Pollard.

Lezione del 21 maggio 2008

Introduciamo ora l’ Algoritmo di fattorizzazione r 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}

⁾ (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 r 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 r (da cui il nome dell’algoritmo).

Relativamente agli indici j, k indicati sopra, si ha allora:

b

=a

modp=b

=a

modp a

a

(mod p)

e comunque dati gli indici i,rj con ir (mod k-j):

b

=a

modp=b

=a

modp a

a

(mod p)

In particolare allora p è divisore comune di n e del valore assoluto della differenza ½a

-a

ê.

Tale differenza è in ogni caso <n (perché a

, a

sono <n essendo elementi di T).

Se tale differenza è 0 (cioè se a

=a

) non abbiamo alcuna informazione.

Ma se ½a

-a

ê>0, si ha che p è divisore di ½a

-a

ê e di n, dunque p è divisore del mcd(½a

-a

ê,n)=d, e dunque lo stesso d è un divisore di n con d>1 (perché p divide d) e con d<n (perché d è divisore di

½a

-a

ê<n): abbiamo in tale caso risolto il problema di fattorizzare n, trovando un suo divisore non banale d.

Se conoscessimo i valori degli indici j,k, potremmo dunque implementare un algoritmo in cui:

- scegliamo un seme casuale sT (quindi con 0sn-1) - calcoliamo i numeri a

, a

- se a

=a

allora l’algoritmo fallisce, e si può tornare alla scelta casuale del seme s, modificando tale scelta, e reiterando l’algoritmo

- se invece a

a

calcolando mcd(½a

-a

ê,n)=d otteniamo un divisore non banale di n.

Però, come già detto, non conosciamo j,k, perché dovremmo conoscere i termini della successione b

=a

modp (e quindi conoscere p).

Possiamo però implementare egualmente l’algoritmo facendo variare in tutti i modi possibili le coppie di indici i,r con 0i<r, e per ogni coppia studiare i valori a

, a

nel modo sopra indicato, con l’aspettativa di arrivare alla coppia corretta i=j, r=k in un numero di passi dello stesso ordine di grandezza di ^p

=p (perché si tratta di coppie di numeri k).

Ma essendo p n , quindi l’algoritmo avrebbe un’efficienza non migliore dell’algoritmo

“ingenuo” di ricerca di un divisore non banale di n (ricerca effettuata testando tutti i naturali da 2 a 

n ).

Ma possiamo migliorare molto l’efficienza dell’algoritmo con il seguente ragionamento (il

cosiddetto metodo di Floyd).

Sia m il minimo naturale multiplo di k-j che sia j; allora b

=b

(perché m,2mj, e perché 2mm (mod k-j)) dunque, come sopra, si ha che d=mcd(½a

-a

ê,n) è un divisore non banale di n, a patto che sia a

a

.

Possiamo notare che certamente mk (perché se fosse per assurdo m>k, allora t=m-(k-j)=(m-k)+j sarebbe un multiplo di k-j, con tj , e con t<m, contro la minimalità di m).

Dunque possiamo implementare una versione molto più efficiente dell’algoritmo facendo variare semplicemente l’indice i=1,2,….. e per ogni valore di i studiare i valori a

, a

nel modo sopra indicato, con l’aspettativa di arrivare al valore corretto i=m in un numero di passi dello stesso ordine di grandezza O( ^p ) (perché mk, e k ha come detto ordine O( ^p )), dunque in un numero di passi di ordine O( ⁴ n ) ( con notevole miglioramento nell’efficienza).

Tutto il ragionamento precedente si basa sulla scelta di una opportuna funzione F: T  T tale che F(xmodp)=F(x)modp per ogni xT: per la compatibilità di somma e prodotto con la congruenza modulo un intero, qualunque funzione polinomiale a coefficienti interi può essere utilizzata (riducendo l’immagine modulo n per restare nell’insieme T)..

Ma per sfruttare le considerazioni probabilistiche (paradosso dei compleanni), si deve anche scegliere F in modo che i termini di S={0,1,….,p-1}siano distribuiti in modo uniforme nella successione b

=a

modp : empiricamente si è visto che una funzione polinomiale quadratica del tipo F(x)=(x

+1)modn (oppure in generale F(x)=(x

+c)modn con c intero) funziona abbastanza bene.

Esponiamo dunque nei dettagli i passi di una possibile versione dell’algoritmo di fattorizzazione r di Pollard:

1) input n intero >1

2) scelta random del seme s con 0sn-1

3) assegnazione alle variabili x,y dei valori x=s, y=s

4) assegnazione dei valori x=(x

+1)modn, y=(y

+1)modn, y=(y

+1)modn

(in questo modo all’inizio dell’algoritmo si ha x=a

, y=a

, e quando ritorneremo ad eseguire una seconda volta il passo 4) si avrà x=a

, y=a

, e in generale all’esecuzione numero i del passo 4) si avrà x=a

, y=a

)

5) se x=y, tornare al passo 2)

(se a

=a

l’algoritmo é fallito, e lo si ripete con un’altra scelta casuale del seme s) 6) se xy calcolare d=mcd(ïx-yï,n)

7) se d=1 tornare al passo 4)

(se d= mcd(ïx-yï,n)=1 allora il valore dell’indice i a cui siamo pervenuti é certamente ancora <m, perché sappiamo che d=mcd(½a

-a

ê,n) è >1, essendo multiplo del fattore primo p di n: si torna allora al passo 4) per incrementare il valore dell’indice i)

8) se d>1 uscire con output “d è divisore non banale di n”

Ad ogni scelta del seme s, l’algoritmo dovrebbe pervenire ad una conclusione (fallimento con successivo cambio del seme, oppure successo con il calcolo di un divisore non banale di n) con un numero di ripetizioni del passo 4) che (dal punto di vista probabilistico) è di ordine O( ⁴ n ) (perché di ordine O( ^p ) dove p è un divisore primo di n, con p n ).

L’algoritmo ha anche il vantaggio della flessibilità, perché, oltre alla modifica del seme s (in caso di fallimento al passo 5)) si può prevedere anche la modifica del termine noto del polinomio quadratico x

+1.

In questa diversa versione dell’algoritmo si dovrebbe aggiungere nel passo 2) l’istruzione di scelta

random del termine noto c del polinomio quadratico (con 0c<n visto che si tratta poi di calcolare

riduzioni modulo n), e modificare il passo 4) sostituendo x

+1, y

+1 rispettivamente con x

+c, y

+c:

in effetti alcuni ragionamenti teorici, che omettiamo, portano ad escludere alcuni valori di c come valori “utili”.

Esempio.

Consideriamo l’input n=108953 nell’algoritmo di fattorizzazione r di Pollard.

Scegliamo per esempio il seme s=1306.

Nel passo 3) poniamo x=y=1306.

Nel passo 4) poniamo:

x=(1306

+1)mod108953=71342

y=(1306

+1)mod108953=71342,y=(71342

+1)mod108953=50523 da cui xy, mcd(71342-50523,108953)=mcd(20819,108953)=1.

Dunque (passo 7)) si torna al passo 4) per incrementare l’indice i:

x=(71342

+1)mod108953=50523

y=(50523

+1)mod108953=22646,y=(22646

+1)mod108953=108499 da cui xy, mcd(108499-50523,108953)=mcd(57976,108953)=1.

Di nuovo si torna al passo 4) per incrementare l’indice i:

x=(50523

+1)mod108953=22646

y=(108499

+1)mod108953=97164,y=(97164

+1)mod108953=65447 da cui xy, mcd(97164-65447,108953)=mcd(31717,108953)=1.

Ancora si torna al passo 4) per incrementare l’indice i:

x=(22646

+1)mod108953=108499

y=(65447

+1)mod108953=40521,y=(40521

+1)mod108953=29732 da cui xy, mcd(108499-29732,108953)=mcd(78767,108953)=13.

Abbiamo dunque trovato un divisore d=13 non banale di n=108953.

In effetti si ha la decomposizione di n in fattori primi è n=108953=13×17

×29.

Il divisore d che abbiamo trovato in questo caso coincide con un divisore primo 13 di n, e (in accordo con le previsioni probabilistiche) si ripete 4 volte il passo 4) (notare che ¹³ »3,6).

Ovviamente se in una delle iterazioni del passo 4) avessimo trovato x=y, sarebbe stato necessario

ricominciare l’algoritmo con un diverso seme s (o volendo anche con un diverso termine noto nel

polinomio quadratico x

+1).