Teoria dei numeri e Crittografia: lezione del 21 dicembre 2011 Relativamente agli indici j, k costruiti nella lezione precedente (k = minimo indice tale che esiste j<k per cui b

(1)

Teoria dei numeri e Crittografia: lezione del 21 dicembre 2011

Relativamente agli indici j, k costruiti 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 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, ossia 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 nella forma = 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

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

i

modp (e quindi conoscere p, divisore primo di n, non noto a priori).

Possiamo però implementare egualmente l’algoritmo nel modo seguente:

- 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 (cioè se a

s

a

r

) 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à di ordine 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 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

.

(2)

Infatti basta per esempio scegliere m coincidente con il 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,3,....

- esaminando il valore½a

i

-a

2i

ê e se esso è >0 (cioè se a

i

a

2i

) 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 poi l’immagine modulo n perché il valore assunto appartenga all’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 della funzione F(x)=(x

²

+c)modn 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

Nota: la doppia assegnazione del valore di y ha il seguente scopo: 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 del seme s e del termine noto c) 6) se xy calcolare d=mcd(ïx-yï,n)

7) se d=1 tornare al passo 4)

Nota: 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)”

(3)

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.

L’algoritmo di fattorizzazione r di Pollard (formulato nel 1975) ha avuto il suo più grande successo nel 1980, quando ha permesso di calcolare la fattorizzazione del numero di Fermat F

8

=

₂⁽²⁸⁾

+1 (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 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).

(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 fattorizza in prodotto di potenze di primi distinti nel modo seguente:

p-1 = p p

₁^k¹ ₂^k²

.... p

_r^k^r

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

ki

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

Nota: 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 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).

Facciamo delle considerazioni sull’algoritmo (p-1) di Pollard, sopra illustrato:

1) L’algoritmo è efficiente soprattutto per input n che abbiano almeno un

divisore primo p tale che nella fattorizzazione di (p-1) di in prodotto di potenze di primi distinti p-

1 = p p

₁^k¹ ₂^k²

.... p

_r^k^r

le potenze p

_i^kⁱ

siano relativamente “piccole” (così è più probabile che p

_i^kⁱ

 B per

ogni i=1,….,r).

(5)

2) Il valore di B nel passo 2) deve essere “abbastanza grande” ma non può essere “troppo grande”, perché il numero k calcolato nel passo 3) potrebbe diventare enorme, e calcolare d nel passo 6) potrebbe essere troppo oneroso in termini di potenza e lunghezza di calcolo

3) Nel passo 6) potrebbe essere oneroso calcolare d=mcd(a

^k

-1,n), perché l’esponente k spesso è molto grande. Si può però risolvere tale problema nel modo seguente: si calcola (in modo efficiente con l’esponenziazione modulare) la riduzione b=a

^k

modn (che è un numero <n) e si possono presentare 2 casi: se b>1, si ha d=mcd(a

^k

- 1,n)=mcd(b-1,n) (segue facilmente da a

^k

b (mod n)) ; se invece b=1, allora n½a

^k

-1, dunque d=mcd(a

^k

-1,n)=n.

4) Infine notiamo che, oltre alla scelta di k=B! nel passo 3), si possono effettuare scelte più convenienti. Se per esempio è noto l’insieme di tutti i numeri primi  B:

{p

1

, p

2

,……., p

r

}

ed è quindi possibile ricavare l’insieme delle massime potenze di tali primi che siano  B : { p

₁^k¹

, p

₂^k²

,...., p

_r^k^r

}

è possibile allora assumere k = p p

₁^k¹ ₂^k²

.... p

_r^k^r

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

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

i

, ognuno con esponente k

i

, quindi p p

₁^k¹ ₂^k²

.... p

_r^k^r

è certamente 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 ha b=a

^k

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

^k

-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 invece manteniamo la scelta precedente B=10, k=2520 e modifichiamo il valore ponendo a=12 si ha:

b=12

²⁵²⁰