Proseguendo con le considerazioni che porteranno all’algoritmo di fattorizzazione  di Pollard, ricordiamo che, dato il numero naturale n>1 da fattorizzare (supponendo n non primo), dato un suo divisore primo p

(1)

Teoria dei numeri

Lezione del giorno 20 maggio 2009

Algoritmo di fattorizzazione  di Pollard.

Proseguendo con le considerazioni che porteranno all’algoritmo di fattorizzazione  di Pollard, ricordiamo che, dato il numero naturale n>1 da fattorizzare (supponendo n non primo), dato un suo divisore primo p

n

(non conosciuto a priori), considerati gli insiemi:

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

e una funzione F: T  T che soddisfa: F(xmodp)=F(x)modp per ogni xT, costruita la successione {a

k

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

a

0

=s; a

k

=F(a

k-1

) per ogni k>0 (dove sT è un “seme” fissato) e in corrispondenza la successione {b

k

} di elementi di S:

b

k

=a

k

modp

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

k

, se k è il minimo indice tale che b

j

=b

k

per un opportuno j<k (tale k è di ordine O(

^p

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

i

=b

r

.

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

b

j

=a

j

modp=b

k

=a

k

modp a

j

a

k

(mod p)

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

b

i

=a

i

modp=b

r

=a

r

modp a

i

a

r

(mod p)

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

j

-a

k

ê.

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

j

, a

k

sono compresi fra 0,1,…..,n-1 essendo elementi di T).

Se tale differenza a

j

-a

k

è 0 (cioè se a

j

=a

k

) non abbiamo alcuna informazione.

Ma se ½a

j

-a

k

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

j

-a

k

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

j

-a

k

ê,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

j

-a

k

ê<n): abbiamo in tale caso risolto il problema di fattorizzare n, trovando un suo divisore non banale d e potendo fattorizzare n come prodotto di n per n/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

j

, a

k

- se a

j

=a

k

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

- se invece a

j

a

k

calcolando mcd(½a

j

-a

k

ê,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

i

=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

i

, a

r

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 O(

^p²

) cioè di ordine O(p) (perché si tratta di coppie di numeri k che è di ordine O(

p

)).

Ma essendo p

n

, l’algoritmo avrebbe una complessità O(

n

) non migliore di quella di altri algoritmi (per esempio di quello “ingenuo” che ricerca di un divisore non banale di non superiore a

n

).

(2)

Possiamo però 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

m

=b

2m

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

m

-a

2m

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

m

a

2m

.

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

i

, a

2i

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

i

=a

i

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  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

1

, y=a

2

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

2

, y=a

4

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

i

, y=a

2i

)

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

(se a

i

=a

2i

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

m

-a

2m

ê,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 (per esempio dopo che il ritorno all’istruzione 4) è stato effettuato un certo numero

fissato di volte senza che l’algoritmo abbia avuto successo).

(3)

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.

Esempio.

Consideriamo l’input n=108953 nell’algoritmo di fattorizzazione  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: notiamo che (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

²