Se tale numero è l’input dell’algoritmo  di Pollard, con seme s=0 l’algoritmo trova un fattore primo di n dopo 110 iterazioni.

Lezione del 21 maggio 2009

Un input notevole che si può usare 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 è l’input dell’algoritmo  di Pollard, con seme s=0 l’algoritmo trova un fattore primo di n dopo 110 iterazioni.

Facendo variare il valore del seme fra 0 e 100000, la media delle iterazioni è circa 246 (con un massimo di 500): notare che il valore (atteso dal punto di vista probabilistico)

è compreso fra 304 e 305.

Algoritmo di fattorizzazione (p-1) di Pollard.

Supponiamo che il numero n da fattorizzare abbia un fattore primo p tale che, nella decomposizione di (p-1) in prodotto di potenze di primi distinti:

p-1 = p

p

....p

le potenze p

non siano troppo “grandi”, nel senso che sia p

 B per ogni i=1,…,r, dove B è un naturale fissato a priori nell’algoritmo.

Sia k un numero naturale divisibile per tutti i numeri naturali  B (per esempio k=B!): essendo in particolare ogni p

 B si ha che ogni p

è divisore di k, dunque, essendo ovviamente i p

^{a 2} a 2 coprimi, anche il loro prodotto (p-1) è divisore di k, cioè k=(p-1)c, con c naturale.

Se allora a>1 è un naturale coprimo con n, certamente a non è multiplo di p, dunque per il Piccolo Teorema di Fermat:

a

 1 (mod p)  a

= (a

)

 1 (mod p)

Essendo a

-1>0 (perché a>1) se poniamo d=mcd(a

-1,n) si ha d>1 (perché p è divisore comune di a

-1,n, quindi p è divisore di d), e se è anche d<n abbiamo trovato un divisore non banale di n.

Possiamo allora implementare un algoritmo di fattorizzazione come segue:

1) in input n>1 naturale 2) si fissa un naturale B

3) si calcola un naturale k multiplo di tutti i naturali  B (per esempio k=B!) 4) si sceglie un intero a con 2an-1

5) se d

=mcd(a,n)>1, si esce con output “d

è un divisore non banale di n” (infatti d

a<n) 6) se invece a,n sono coprimi, si calcola d=mcd(a

-1,n)

7) se 1<d<n, si esce con output “d è un divisore non banale di n”

8) se d=1 oppure d=n si torna al passo 4), per una nuova scelta di a (dopo un certo numero di

“fallimenti” si può anche prevedere un ritorno al passo 2) con una scelta di una costante B più grande)

Ovviamente se B nel passo 2) è scelto abbastanza “grande”, è più probabile che nella fattorizzazione di (p-1) (dove p è fattore primo di n) tutte le potenze dei fattori primi siano B, e quindi (per il ragionamento precedente) il caso d=1 nel passo 8) non si può presentare, cioè nel passo 8) si trova un divisore non banale di n, tranne che nel caso d=n (questo è un caso che si può presentare e non è possibile prevederlo a priori).

D’altra parte B non può essere scelto troppo “grande”, perché il numero k

calcolato in 3) potrebbe diventare di grandezza eccessiva e calcolare d nel

passo 6) potrebbe essere oneroso in termini di potenza e lunghezza di calcolo.

Notiamo anche che nel passo 6) possiamo semplificare i calcoli con la seguente osservazione: se calcoliamo (con l’esponenziazione modulare) la riduzione b=a

modn si possono presentare 2 casi: se b>1, si ha d=mcd(a

-1,n)=mcd(b-1,n):

infatti da a

-1b-1 (mod n) segue che i divisori comuni di a

-1,n sono tutti e soli i divisori comuni di b-1,n; se invece b=1, allora n è divisore di a

-1, dunque d=mcd(a

-1,n)=n.

Quindi nel passo 6) si può usare l’esponenziazione modulare per calcolare prima a

modn e poi ricavare d (anche se l’esponente k, come detto, può essere molto “grande” e quindi l’esponenziazione modulare può avere alta complessità).

Infine, se è disponibile un archivio di tutti i numeri primi  B, ed è quindi possibile ricavare l’elenco completo delle massime potenze di tali primi che siano  B, siano esse:

p

, p

,...., p

è possibile allora assumere come valore di k nel passo 3) il prodotto p

p

....p

ottenendo tra l’altro un valore in genere molto minore di B!.

Basta infatti osservare che p

p

....p

è in effetti multiplo di ogni naturale x B: infatti ogni naturale x B nella sua fattorizzazione in prodotto di potenze di primi distinti coinvolge alcuni dei p

, ognuno con esponente k

, quindi p

p

....p

è multiplo di x

Per esempio se B=10, allora B!=3628800, mentre il prodotto delle massime potenze di primi che siano  10 é 2

3

57=2520 (valore molto minore), ed è egualmente un numero multiplo di tutti i naturali  10.

Esempio.

Input n=2047: scegliamo B=10, k=2520 (vedere sopra), e fissiamo per esempio a=2: ovviamente 2, 2047 sono coprimi.

Calcolando con l’esponenziazione modulare, si verifica che b=a

modn=2, dunque, per quanto detto sopra, d=mcd(2

-1,2047)=mcd(b-1,2047)=mcd(1,2047)=1, quindi l’algoritmo non ha successo (il fatto che d=1 implica che il valore B fissato non è abbastanza alto: quando B è un valore “buono” sappiamo che l’algoritmo può fallire solo se mcd(a

-1,n)=n).

Se (sempre con a=2) scegliamo un valore più alto di B, per esempio B=11, il valore di k è k=2

3

5711=27720, e in questo caso b=2

mod2047=1, dunque, per quanto detto sopra, d=mcd(2

-1,2047)=2047=n, e di nuovo l’algoritmo non ha successo (ma stavolta per la scelta di a).

Se scegliamo invece il valore a=12 (sempre con B=10, k=2520) si ha:

b=12

mod2047=357, d=mcd(b-1,2047)=mcd(356,2047)=89

e l’algoritmo trova un divisore non banale 89 di n=2047 (in effetti 2047=8923).