Teoria dei numeri e Crittografia: lezione del 18 maggio 2011

Teoria dei numeri e Crittografia: lezione del 18 maggio 2011

Continuiamo l’esposizione delle considerazioni che portano all’ algoritmo di fattorizzazione r di Pollard.

Relativamente agli indici j, k indicati nella lezione precedente (k = minimo indice tale che esiste j<k per cui b j =b k ), si ha allora:

b j =a j modp=b k =a k modp dunque:

a j  a k (mod p)

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

b i =a i modp=b r =a r modp segue:

a i  a r (mod p)

In particolare allora p è divisore comune di n e del valore assoluto della differenza ½a j -a k ê (che è un intero non negativo).

Tale differenza½a j -a k ê è in ogni caso <n (perché a j , a k sono compresi fra 0,1,…..,n-1 essendo elementi di T).

Se 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 comune di ½a j -a k êed n, dunque p½mcd(½a j -a k ê,n)=d, e dunque d è un divisore di n con d>1 (perché p divide d) e con d<n (perché d½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 = d (n/d).

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

- scegliamo una opportuna funzione F ed un seme arbitrario sT (quindi con 0sn-1) - calcoliamo i termini a j , a k della successione a i

- se a j =a k allora l’algoritmo fallisce, e si può tornare ad una diversa scelta del seme s, 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, divisore primo di n non noto a priori).

Possiamo però implementare egualmente l’algoritmo:

- facendo variare in tutti i modi possibili le coppie di indici (s, r) con 0s<r (per esempio facendo assumere alla variabile r i valori 1,2,3,…. e per ogni r facendo assumere alla variabile s i valori 0,1,

….,r-1)

- per ogni coppia (s, r) esaminando il valore½a s -a r ê e (se esso è >0) calcolando mcd(½a j -a k ê,n)=d con l’aspettativa di arrivare alla coppia corretta s=j, r=k (che ci può fornire un divisore non banale di n) in un numero di passi di ordine O(k ² ) (perché si tratta di coppie di numeri s,r  k) e quindi in un numero di passi di ordine O(p) (perché k è di ordine O( p )).

Ma essendo p n , il numero di passi dell’algoritmo avrebbe una complessità  O( n ), con una situazione non migliore di quella di altri algoritmi di fattorizzazione (come per esempio quello

“ingenuo” o quello di Fermat).

Possiamo però migliorare molto l’efficienza dell’algoritmo con il seguente ragionamento (il

cosiddetto metodo di Floyd).

Affermiamo che : esiste un numero naturale m k (dove l’indice k è quello di riferimento citato nel ragionamento iniziale) tale che b m =b 2m .

Infatti basta per esempio scegliere m=minimo naturale ³j che sia multiplo di k-j : per tale scelta di m si ha allora b m =b 2m (perché m,2m³j, e perché 2mm (mod k-j), vedere proprietà della successione b i ) , ed inoltre mk perché se fosse per assurdo m>k, allora t=m-(k-j)=(m-k)+j sarebbe un numero naturale ³j multiplo di k-j, con t<m, contro la minimalità di m.

Per tale scelta di m si ha (ragionando come sopra) che d=mcd(½a m -a 2m ê,n) è un divisore non banale di n, a patto che sia a m a 2m .

Dunque possiamo implementare una versione molto più efficiente dell’algoritmo:

- facendo variare (invece delle coppie (s,r)) l’indice i=1,2,…..

- esaminando il valore½a i -a 2i ê e (se esso è >0) calcolando mcd(½a j -a k ê,n)=d

con l’aspettativa di arrivare all’indice corretto i=m (che ci può fornire un divisore non banale di n), in un numero di passi m  k di ordine O(k) e quindi in un numero di passi di ordine O( p ) (perché k è di ordine O( p )) ossia in un numero di passi di ordine O( ⁴ n ) perché p n .

Questo porta un sostanziale miglioramento della complessità dell’algoritmo (pur rimanendo esponenziale in x=L(n)).

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 le congruenze aritmetiche, qualunque funzione polinomiale a coefficienti interi può per esempio essere utilizzata (riducendo l’immagine modulo n per restare all’interno dell’insieme T):

F(x) = (a 0 +a 1 x+….+a t x ^t )modn a i interi, t>0

Ma per sfruttare le considerazioni probabilistiche fatte nella lezione precedente, si deve anche scegliere F in modo che gli elementi di S={0,1,….,p-1} siano distribuiti in modo uniforme nella successione b i =a i modp : sperimentalmente si è visto che una funzione polinomiale quadratica del tipo F(x)=(x ² +c)modn con il termine noto c³0 produce spesso distribuzioni abbastanza uniformi dal punto di vista probabilistico. Inoltre si può scegliere c<n (non è restrittivo visto che poi si riduce modulo n).

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

1) input n intero >1

2) scelta del seme s con 0 s n-1; scelta del termine noto c con 0 c n-1 3) assegnazione alle variabili x,y dei valori iniziali x=y=s

4) assegnazione dei valori x=(x ² +c)modn, y=(y ² +c)modn, y=(y ² +1)modn

(notare la doppia assegnazione del valore di y; in questo modo dopo la prima esecuzione del passo 4) si ha x=F(s)=F(a 0 )=a 1 , y=F(s)=F(a 0 )=a 1 , y=F(a 1 )=a 2, dopo la seconda esecuzione si ha x=F(a 1 )=a 2 , y=F(a 2 )=a 3 , y=F(a 3 )=a 4 , e in generale dopo l’esecuzione numero i del passo 4) si ha 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 di s, c) 6) se xy calcolare d=mcd(ïx-yï,n)

7) se d=1 tornare al passo 4)

(se d= mcd(ïa i -a 2i ï,n)=1 allora il valore dell’indice i a cui siamo pervenuti é certamente ancora <

del valore “opportuno” m, perché sappiamo che d=mcd(½a m -a 2m ê,n) è certamente >1: quindi si

torna al passo 4) per incrementare il valore dell’indice i)

8) se d>1 si esce con output “d è divisore non banale di n, e n=d(n/d)”

Ad ogni scelta di s, c, l’algoritmo dovrebbe pervenire ad una conclusione (fallimento 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 ).

L’algoritmo ha anche il pregio della flessibilità.

Per esempio vi sono altre “versioni” dell’algoritmo in cui al fallimento nel passo 5) segue la modifica solo del seme s, e solo dopo un certo numero di modifiche senza successo di s segue la modifica del termine noto c. In altre versioni ancora si usano funzioni F diverse da quelle indicate sopra.

Esempio.

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

Scegliamo per esempio il seme s=1306 e il termine noto c=1.

Nel passo 3) poniamo x=y=1306 (valori iniziali di x, y) Nel passo 4) si ha:

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 dal 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.

Il divisore che abbiamo trovato in questo caso coincide con un divisore primo p=13: 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 e con un diverso termine noto c.

Il numero di Jevons.

Un numero che spesso viene usato come input per testare le capacità dei vari algoritmi di fattorizzazione è il numero di Jevons n=8616460799, che è il prodotto di due numeri primi p=89681, q=96079.

Se per esempio tale numero è l’input dell’algoritmo r di Pollard, con seme s=0 e con termine noto c=1 l’algoritmo trova un fattore primo di n dopo 110 iterazioni del passo 4).

Si è verificato che, 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 è di

ordine O( ⁴ n ) , e che ⁴ n è compreso fra 304 e 305.

Algoritmo di fattorizzazione (p-1) di Pollard.

Supponiamo che il numero n da fattorizzare abbia un divisore primo p tale che (p-1) si fattorizzi in prodotto di potenze di primi distinti nel modo seguente:

p-1 = p p ₁ ^k

₂ ^k

.... p _r ^k

e supponiamo anche che B sia un naturale tale che:

p _i ^k

 B per ogni i=1,….,r (*)

Sia k un numero naturale multiplo di tutti i numeri naturali  B (per esempio k=B!, ma vedremo scelte più efficienti di k): per costruzione ogni ^p _i ^k

è divisore di k, dunque, essendo ovviamente i

k

p i 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 ^p-1  1 (mod p)  a ^k = (a ^p-1 ) ^c  1 (mod p)

Essendo a ^k -1>0 (perché a>1) se poniamo d=mcd(a ^k -1,n) si ha d>1 (perché p è divisore comune di a ^k -1,n, quindi p è divisore di d), e se è anche d<n (ma ciò non è garantito) abbiamo trovato un divisore non banale di n.

Possiamo allora implementare l’algoritmo di fattorizzazione (p-1) di Pollard come segue:

1) in input n>1 naturale

2) si fissa un naturale B “abbastanza grande” (quanto maggiore è il valore di B, tanto maggiore sarà la possibilità che per qualche fattore primo p di n sia vera la proprietà (*))

3) si calcola un naturale k multiplo di tutti i naturali  B 4) si fanno assumere ad a i valori a=2, 3, …., n-1

5) se c=mcd(a,n)>1, si esce con output “ c è un divisore non banale di n, e n=c(n/c)” (infatti si ha c a< n)

6) se a,n sono coprimi, si calcola d=mcd(a ^k -1,n)

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

8) se d=n si torna al passo 4) per scegliere un nuovo valore di a

9) se d=1 si torna al passo 2), per scegliere un valore maggiore di B (se d=1 l’algoritmo non ha avuto successo a causa dell’insufficiente grandezza di B, perché se B soddisfa (*) allora d=mcd(a ^k -1,n) >1 come visto nel ragionamento precedente);

10) se d=n si torna al passo 4) per una nuova scelta di a (l’algoritmo è fallito per quella scelta di a, ma potrebbe avere successo modificando a )

Nota: Per evitare troppe ripetizioni del passo 4), si può a priori fissare un numero massimo k di

valori di a da scegliere nel passo 4) e dopo averli esauriti prevedere un’istruzione che rimandi al

passo 2) per una scelta di un valore di B (più grande).