Matematica Discreta II
Lezione del giorno 26 novembre 2007
Esponiamo nei dettagli i passi dell’algoritmo di fattorizzazione r di Pollard (fissato per esempio il polinomio g(x)=x2+1):
1) input n intero >1
2) scelta random del seme s con 0£s£n-1
3) assegnazione alle variabili x,y dei valori iniziali x=s, y=s
4) assegnazione dei valori z=(x2+1)modn, x=z, w=(y2+1)modn, t=(w2+1)modn, y=t
(in questo modo all’inizio dell’algoritmo si ha x=F(1)(s), y=F(2)(s), e quando ritorneremo ad eseguire una seconda volta il passo 4) si avrà x=F(2)(s), y=F(4)(s), e in generale all’esecuzione numero i del passo 4) si avrà x=F(i)(s), y= F(2i)(s))
5) se x=y, tornare al passo 2)
(se F(i)(s)=F(2i)(s) 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 é minore dell’indice m tale che mcd(ïF(m)(s)-F(2m)(s)ï,n) >1, essendo, per tale indice m, (ïF(m)(s)-F(2m)(s)ïmultiplo del fattore primo minimale 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) è dello stesso ordine di grandezza di p , dove p è un fattore primo minimale di n, quindi dello stesso ordine di grandezza di 4 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 x2+1.
In questa diversa versione dell’algoritmo si dovrebbe aggiungere nel passo 2) l’istruzione di scelta random del termine noto a>0 (con a<n visto che si tratta poi di calcolare riduzioni modulo n), e modificare il passo 4) sostituendo il numero 1 con a: in effetti alcuni ragionamenti teorici, che omettiamo, portano ad escludere alcuni valori di a 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) si ha:
x=71342 y=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=50523 y=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 x=22646 y =65447
da cui x¹y, mcd(65447-22646,108953)=mcd(42801,108953)=1.
Ancora si torna al passo 4) per incrementare l’indice i:
x=108499 y=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 la decomposizione di n in fattori primi è n=108953=13×172×29.
Il divisore d=13 che abbiamo trovato in questo caso coincide con il fattore primo minimale di n, e (in accordo con le previsioni probabilistiche) si ripete 4 volte il passo 4) (notare che 13»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 (volendo anche con un diverso termine noto nel polinomio quadratico x2+1).
Esempio.
Un input che spesso viene usato per testare gli algoritmi di fattorizzazione è il numero di Jevons n=8616460799, che è il prodotto di due numeri primi p=89681, q=96079.
Se tale numero viene immesso come input dell’algoritmo r di Pollard, con seme s=0 l’algoritmo trova un fattore primo di n dopo 110 iterazioni (passo 4)).
Facendo variare il valore del seme fra 0 e 100000, la media delle iterazioni è circa 246 (con un massimo di 500): notare che 4 n è compreso fra 304 e 305, mentre p è circa 300.
