(1)Lezione del 22 maggio 2009 L’algoritmo del crivello quadratico di Pomerance

Lezione del 22 maggio 2009

L’algoritmo del crivello quadratico di Pomerance.

Il maggior successo di questo algoritmo è stato, nel 1994, la fattorizzazione del numero RSA-129, un numero di 129 cifre (in base 10), la cui fattorizzazione nel 1977 era stato proposta come sfida dagli ideatori del sistema crittografico RSA: utilizzando per 8 mesi il lavoro in parallelo dei computers di circa 600 utenti di Internet, nell’aprile 1994 si è pervenuti alla fattorizzazione di RSA- 129 nel prodotto di 2 primi di 64 e 65 cifre.

L’algoritmo del crivello quadratico si ispira all’algoritmo di Fermat: dato un input n dispari >1, l’algoritmo di Fermat fa variare r=  n,  n+1,  n+2,….., e verifica se r²-n è un quadrato perfetto s², in modo da scrivere n come differenza di quadrati n=r²-s² e trovare poi un divisore non banale di n.

L’algoritmo del crivello quadratico, invece, dato l’input n dispari >1 da fattorizzare, cerca di trovare r,s naturali, tali che n sia divisore di r²-s², ossia tali che r²s² (mod n): l’esistenza di r,s non garantisce però l’esistenza di un divisore di n.

Se però r non é congruo s modulo n, e poniamo d=mcd(r-s,n) (supponendo r>s), si ha che d è un divisore non banale di n: infatti se per assurdo fosse d=1 (quindi n, r-s coprimi) da n(r-s)(r+s) seguirebbe n(r+s), r-s (mod n), contraddizione; se invece fosse d=n, sarebbe d=n(r-s), rs (mod n), contraddizione.

Quindi lo schema dell’algoritmo è il seguente: trovare una coppia di numeri naturali r,s (con r>s) tali che r²s² (mod n), verificare se rs (mod n), e in caso ciò non sia vero uscire con il valore mcd(r-s,n) come divisore non banale di n; se invece rs (mod n) ricercare una nuova coppia r,s.

Come però trovare r,s naturali tali che r²s² (mod n) ?

Fissiamo un naturale K e calcoliamo l’insieme di tutti i numeri primi che sianoK:

B={p1, p2, ………, pt} (B è detta una “base di fattori”).

Poiché deve essere n divisore di r²-s², si ha r²>n dunque r n (come nell’algoritmo di Fermat) Se facciamo variare r=  n,  n+1,  n+2,….. e calcoliamo in corrispondenza il numero naturale y=r²-n, otteniamo yr² (mod n): se r è “vicino” a n, il valore di y è relativamente

“piccolo”, quindi è probabile che i suoi fattori primi siano tutti in B (se K è scelto “abbastanza grande”).

Supponiamo di avere ottenuto un certo numero di valori y=y1, y2, ….., ym (in corrispondenza di valori r=r1, r2, ….., rm) tali che ogni yi abbia tutti i suoi fattori primi in B: questa fase è quella del

“crivello”.

Per ogni i=1,….,m determiniamo la fattorizzazione in prodotto di potenze di primi distinti di ogni yi

(facile da calcolare perché conosciamo i primi p1, p2, ………, pt tra i quali vi sono i fattori primi di yi):

yi = p₁^k1,ip₂^k2,i...p_t^kt,i i=1,2,…..,m

(con esponenti kj,i0: in particolare kj,i=0 se il primo pj non è presente nella fattorizzazione di yi).

Per costruzione si ha ri2yi (mod n) per ogni i=1,2,…..,m (essendo yi = ri2 – n).

Dunque si ottengono m congruenze modulo n:

r12y1 (mod n) r22y2 (mod n) ……

……

rm2ym (mod n)

Se riuscissimo a determinare alcuni dei valori yi tali che il loro prodotto sia un quadrato perfetto s², moltiplicando membro a membro le corrispondenti congruenze, alla fine otterremmo una

congruenza della forma voluta r²s² (mod n) (dove r é il prodotto dei corrispondenti ri,) e potremmo (se r non é congruo s modulo n) trovare un divisore non banale di n.

Ma nel moltiplicare valori yi fra loro, i corrispondenti esponenti kj,i delle fattorizzazioni si sommano, e poiché un naturale è un quadrato perfetto se e solo se tutti gli esponenti della sua fattorizzazione sono multipli di 2, dobbiamo cercare alcuni valori yi tali che, per ogni primo pj ,la somma dei corrispondenti esponenti kj,i sia un multiplo di 2: ma come essere certi che esistano, fra y1, y2, ….., ym, alcuni yi con tale proprietà e inoltre, se esistono, come determinarli ?

Per risolvere tale problema, possiamo appunto usare la teoria degli spazi vettoriali.

Supponiamo che il numero m degli elementi yi che abbiamo trovato sia maggiore del numero t di primi nella “base di fattori” B (per es. m=t+1).

Associamo ad ogni yi la t-upla di interi non negativi formata ordinatamente dagli esponenti kj,i che compaiono nella fattorizzazione di yi:

yi  v(yi) = (k1,i , k2,i ,…….., kt,i)

Se poi riduciamo tutti gli esponenti modulo 2, otteniamo una t-upla di termini 0 o 1:

yi  v2(yi) = (k1,imod2, k2,imod2 ,…….., kt,imod2)

Possiamo trattare v2(yi) come vettore dello spazio vettoriale Z2t sul campo Z2 = {0,1}.

Cercare fra y1,….., ym, alcuni yi il cui prodotto sia un quadrato perfetto, equivale, per le considerazioni precedenti, a cercare una somma di alcuni dei vettori v2(y1),…..,v2(ym) che dia il vettore nullo in Z2t.

Poiché m>t, e poiché t è la dimensione dello spazio Z2t, i vettori v2(yi) (con i=1,2,…,m) sono linearmente dipendenti, dunque esiste una loro combinazione lineare a coefficienti 0,1 non tutti nulli che dà il vettore nullo e se consideriamo solo i termini di tale combinazione che hanno coefficiente 1, otteniamo una somma di alcuni dei vettori v2(y1),…..,v2(ym) che dia il vettore nullo, e raggiungiamo il nostro obiettivo.

Dopo avere trovato questi vettori, se consideriamo i corrispondenti elementi fra y1,…..,ym siamo certi che il loro prodotto è un quadrato perfetto s² (dove la base s si ottiene facilmente dividendo per 2 tutte le componenti della t-upla ottenuta sommando le t-uple relative v(yi), e attribuendo i risultati come esponenti dei numeri primi p1, p2, ………, pt); si avrà inoltre r²s² (mod n) dove r è il prodotto dei valori ri corrispondenti agli elementi yi trovati.

Le somme di alcuni fra i vettori v2(yi) che danno come risultato il vettore nullo (0, 0, …., 0) si possono calcolare con il metodo di eliminazione di Gauss (che poi illustreremo): per ognuna di tali somme si trova la congruenza relativa r²s² (mod n), e se r non è congruo s modulo n, si è trovato un divisore non banale di n.

Nel ragionamento precedente è essenziale la scelta strategica della base di fattori B: se essa contiene molti primi, vi sono più probabilità di trovare “molti” valori yi che abbiano tutti i loro fattori primi in B, ma può diventare più complesso l’uso del metodo di eliminazione di Gauss, perché aumenta il numero di vettori v2(yi) da manipolare (ricordiamo che devono essere in numero >B).

Possiamo però osservare che ogni primo pB che non sia “superfluo” (cioè che sia effettivamente divisore di qualcuno dei valori yi) deve essere tale che n sia un resto quadratico modulo p : infatti essendo yi=ri2-n si ha nr² (mod p), se p è divisore di yi .

Per la teoria dei resti quadratici, sappiamo che, essendo n dispari, n è resto quadratico modulo 2;

invece per un primo dispari p, si ha che n è resto quadratico modulo p se e solo se (n/p)=1 (simbolo di Legendre), almeno se n non è multiplo di p (ma se n è multiplo di p, abbiamo già un divisore non banale di n).

Dunque, nel costruire la base di fattori B, possiamo fissare una grandezza massima K, calcolare tutti i primi pK, ed escludere da B tutti i primi p dispari tali che (n/p)1 : il calcolo di (n/p) si fa con i soliti algoritmi, coinvolgendo numeri non molto grandi, anche se n è grande, in quanto sappiamo che (n/p)=(nmodp/p).

L’algoritmo del crivello quadratico di Pomerance si può allora implementare nel modo seguente:

1) input n dispari >1 2) si sceglie un intero K>0

3) si esaminano tutti i primi pK e si eliminano tutti i primi dispari p tali che (n/p)1, costituendo la base di fattori B={p1, p2, ………, pt}

4) facendo assumere ad r valori interi successivi  n, si trovano almeno t+1 valori y=r²-n che abbiano tutti i loro fattori primi in B (per evitare che tale ricerca non abbia successo e si entri in un loop senza fine, si può porre un limite superiore ai valori assunti da r, e una volta raggiunto tale limite si ritorna al passo 2) con una scelta di K più grande)

5) per ognuno dei valori y1, y2, ….., yt+1 si calcola il vettore in Z2t: v2(yi) = (e1, e2, ……, et) dove ei è la riduzione modulo 2 dell’esponente di pi nella fattorizzazione di yi

6) con il metodo di eliminazione di Gauss si determinano alcuni dei vettori v2(yi) che danno somma uguale al vettore nullo

7) si pone x uguale al prodotto degli ri corrispondenti agli yi trovati nel passo 6) e si pone y uguale al prodotto delle potenze di p1, p2 ,…, pt con esponenti uguali alla semisomma degli esponenti della fattorizzazione degli stessi yi

8) si calcola d=mcd(x-y,n) e se 1<d<n si esce con “d è divisore non banale di n” altrimenti si torna al passo 2) con una scelta di K più grande (si è verificato certamente il caso x congruo

y modulo n)

Prima di dare un esempio di fattorizzazione mediante l’algoritmo del crivelo quadratico, diamo alcuni cenni del metodo di eliminazione di Gauss, applicato in particolare sul campo Z2 = {0,1} . Data una matrice con righe ed m colonne (supponendo n<m), il metodo cerca di costruire una matrice “ridotta” con le seguenti proprietà:

- in ogni riga non identicamente nulla, la colonna che contiene il primo valore =1 (pivot) non contiene altri valori non nulli oltre il pivot

- in ogni riga non identicamente nulla, il pivot si trova a destra rispetto a tutti gli eventuali pivot delle righe precedenti

Per ottenere la matrice ridotta, i passi sono i seguenti:

1) porre i=1 (indice di riga), j=1 (indice di colonna)

2) se esiste nella colonna j e in una delle righe k con ki un valore =1, allora scambiare la riga i con la riga k (in modo che tale valore =1 si porti nella colonna j, riga i, costituendo il pivot);

se tale valore =1 non esiste allora andare al passo 5) (per incrementare l’indice j di colonna) 3) annullare tutti i valori =1 nella colonna j, tranne il pivot della riga i: per fare ciò basta

sostituire ogni riga ki (che contenga un valore 1 nella colonna j) con la somma di tale riga k e della riga i (ricordando che 1+1=0 in Z2)

4) incrementare l’indice di riga i ponendo i=i+1, e se i>n allora uscire; altrimenti proseguire con il passo 5)

5) incrementare l’indice di colonna j ponendo j=j+1, e se j>m allora uscire; altrimenti tornare al passo 2)

Se sono dati m vettori in Z2t con m>t:

v1 = (a11, a21, …….., at1) v2 = (a12, a22, …….., at2)

…..

…..

vm = (a1m, a2m, …….., atm)

per determinare quali somme di alcuni dei vi danno il vettore nullo si procede nel modo seguente.

A partire dalla matrice txm che ha come colonne le coordinate dei vettori vi : M = (aij) i=1,….,t, j=1,…..,m

si costruisce, con il metodo di Gauss, la matrice ridotta Mr e si individuano le colonne di Mr che non contengono nessun pivot, siano esse le colonne j1, j2, …., jk (con 1 j1, j2, …., jkm).

Per ognuno degli indici di colonna jh (con h=1,…,k) si costruisce una somma di vettori scelti fra i vi

con il seguente criterio: uno degli addendi è il vettore vj_h e gli altri addendi sono i vettori vj con indice j diverso da j1, j2, …., jk e tali che vi sia valore =1 nella riga j, colonna jh .

Le somme di alcuni dei v1, v2, …., vm che danno il vettore nullo sono appunto le k somme costruite sopra e le loro possibili combinazioni lineari con coefficienti 0,1.

Esempio.

Sia m=6, t=5, e siano dati i seguenti 6 vettori in Z25: v1 = (0,0,1,1,0)

v2 = (1,1,0,1,0) v3 = (1,1,1,0,1) v4 = (1,0,0,0,0) v5 = (1,0,0,0,0) v6 = (1,1,1,0,1)

La matrice originaria delle colonne di coordinate dei vettori é la seguente:

0 1 1 1 1 1 0 1 1 0 0 1 1 0 1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 1

Procedendo con il metodo di Gauss, costruiamo la matrice ridotta.

Scambio delle righe 1 e 3 : 1 0 1 0 0 1

0 1 1 0 0 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 0 0 1

Azzeramento dei valori in colonna 1 : 1 0 1 0 0 1

0 1 1 0 0 1 0 1 1 1 1 1 0 1 1 0 0 1 0 0 1 0 0 1

Azzeramento dei valori in colonna 2 : 1 0 1 0 0 1

0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1

Scambio delle righe 3 e 5 : 1 0 1 0 0 1

0 1 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0

Azzeramento dei valori in colonna 3 : 1 0 0 0 0 0

0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0

Scambio delle righe 4 e 5 : 1 0 0 0 0 0

0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0

Azzeramento dei valori in colonna 4 : 1 0 0 0 0 0

0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0

La matrice ottenuta è la matrice ridotta, in cui le colonne 5 e 6 non contengono nessun pivot, quindi dobbiamo costruire 2 somme:

la prima è la somma v4+v5 (l’indice 4 è l’unico 5,6 tale che vi sia valore =1 nella riga 4, colonna 5), mentre la seconda è la somma v3+v6 (l’indice 3 è l’unico 5,6 tale che vi sia valore =1 nella riga 3, colonna 5).

Le 2 somme precedenti e la loro combinazione lineare (v4+v5)+(v3+v6) sono tutte le possibili somme di alcuni dei vi che danno il vettore nullo.

Esempio di fattorizzazione con il crivello quadratico.

Input n=16843009, con  n=4105.

Fissiamo K=13: i numeri primi pK sono 2,3,5,7,11,13.

Calcoliamo per ognuno il simbolo di Legendre (n/p).

Si ha per esempio, essendo nmod3=1: (n/3)=(1/3)=1.

Analogamente:

nmod5=4, (n/5)=(4/5)=(2²/5)=1; nmod7=1, (n/7)=(1/7)=1, nmod13=1, (n/13)=(1/13)=1.

Ma, applicando anche la legge di reciprocità quadratica:

nmod11=7, (n/11)=(7/11)=(11/7)(-1)^60/4=-(11/7)=-(11mod7/7)=-(4/7)=-(2²/7)=-1.

Dunque dobbiamo escludere il primo 11, e la base di fattori è B={2,3,5,7,13}, di cardinalità t=5.

Facendo assumere ad r i valori 4104,4105,4106,….. e per ognuno calcolando y=r²-n, si cercano t+1=6 valori y che abbiano tutti i loro fattori primi in B, e si trovano i seguenti valori:

r1= 4122 ; y1 = 2⁰3⁰5³7¹13² ; v(y1)=(0,0,3,1,2), v2(y1)=(0,0,1,1,0) r2= 4159 ; y2 = 2⁷3¹5⁰7¹13² ; v(y2)=(7,1,0,1,2), v2(y2)=(1,1,0,1,0) r3= 4187 ; y3 = 2³3³5¹7²13¹ ; v(y3)=(3,3,1,2,1), v2(y3)=(1,1,1,0,1) r4= 4241 ; y4 = 2⁵3⁶5⁰7²13⁰ ; v(y4)=(5,6,0,2,0), v2(y4)=(1,0,0,0,0) r5= 4497; y5 = 2⁵3⁰5⁴7⁰13² ; v(y5)=(5,0,4,0,2), v2(y5)=(1,0,0,0,0) r6= 4993 ; y6 = 2⁹3⁵5¹7⁰13¹ ; v(y6)=(9,5,1,0,1), v2(y6)=(1,1,1,0,1)

Cerchiamo alcuni degli v2(yi) che diano come somma il vettore nullo con il metodo di eliminazione di Gauss: i vettori sono esattamente quelli dell’esempio precedente.

Quindi le somme da esaminare sono v2(y3)+ v2(y6)=(0,0,0,0,0)

v2(y4)+ v2(y5)=(0,0,0,0,0)

v2(y3)+ v2(y6)+ v2(y4)+ v2(y5)=(0,0,0,0,0)

In corrispondenza della prima somma si trovano per esempio i valori x=r3r6=20905691, y=2⁶3⁴5¹7¹13¹=2358720, x-y=18546971,d=mcd(18546971,n)=65537 e abbiamo trovato un divisore d=65537 non banale di n: in effetti n=65537257.

Possiamo migliorare l’efficienza dell’algoritmo del crivello quadratico.

Invece di procedere nel passo 4) con valori crescenti di r a partire da  n, possiamo scegliere un

“intorno” di  n e considerare anche i valori di r< n : quindi il passo 4) nell’algoritmo del crivello quadratico viene sostituito dalla variabilità di r nell’intervallo [ n-c ,  n+c] con c>0 naturale fissato.

Questo ci permette di avere valori mediamente più “vicini” a  n.

Ma se r è un valore < n, il valore corrispondente y=r²-n è <0, dunque possiamo rappresentare y come y=-z, con z>0, e verificare se z abbia tutti i suoi fattori primi in B, e in caso positivo prendere y fra i valori “utili” yi.

Il problema è che, nel calcolare un prodotto degli yi che sia un quadrato perfetto (con la regola dei vettori di esponenti) l’eventuale segno negativo di alcuni yi potrebbe portare ad un segno negativo nel prodotto, e quindi ottenere invece l’opposto di un quadrato perfetto.

Ma si può ovviare a ciò introducendo nella base dei fattori B anche la base p=-1 (come se fosse un ulteriore ”primo”): tale base ha esponente dipendente solo dal segno del numero, nel senso che se y>0, allora la fattorizzazione di y comprende un fattore (-1)⁰, mentre se y<0 la fattorizzazione di y comprende un fattore (-1)¹ (e tutti gli altri fattori derivanti dalla fattorizzazione di –y>0).

In questo modo, applicando sempre la regola dei vettori di esponenti ridotti modulo 2, essendo anche la somma degli esponenti della base –1 multipla di 2, questo garantisce che il prodotto è positivo, dunque è esattamente un quadrato perfetto, e non l’opposto di un quadrato perfetto.

Esempio.

Input n = 1100017, con  n=1049.

Fissiamo K=17: i numeri primi pK sono 2,3,5,7,11,13,17.

Calcolando per ognuno il simbolo di Legendre (n/p), si verifica che (n/p)=-1 solo per p=5,11, dunque la base di fattori è B={-1,2,3,7,13,17}, di cardinalità 6.

Facendo variare r da 1049-25=1024 a 1049+25=1074, e per ogni r calcolando y=r²-n, si cercano t+1=7 valori y che abbiano tutti i loro fattori primi in B (a meno del segno), e si trovano:

r1= 1025 ; y1 =-49392=(-1)¹2⁴3²7³13⁰17⁰ ; v(y1)=(1,4,2,3,0,0), v2(y1)=(1,0,0,1,0,0) r2= 1033 ; y2 =-32928=(-1)¹2⁵3¹7³13⁰17⁰ ; v(y1)=(1,5,1,3,0,0), v2(y1)=(1,1,1,1,0,0) r3= 1043 ; y3 =-12168=(-1)¹2³3²7⁰13²17⁰ ; v(y1)=(1,3,2,0,2,0), v2(y1)=(1,1,0,0,0,0) r4= 1047 ; y4 =-3808=(-1)¹2⁵3⁰7¹13⁰17¹ ; v(y1)=(1,5,0,1,0,1), v2(y1)=(1,1,0,1,0,1) r5= 1049; y5 =384=(-1)⁰2⁷3¹7⁰13⁰17⁰ ; v(y1)=(0,7,1,0,0,0), v2(y1)=(0,1,1,0,0,0) r6= 1061 ; y6 =25704=(-1)⁰2³3³7¹13⁰17¹ ; v(y1)=(0,3,3,1,0,1), v2(y1)=(0,1,1,1,0,1) r7= 1063 ; y6 =29952=(-1)⁰2⁸3²7⁰13¹17⁰ ; v(y1)=(0,8,2,0,1,0), v2(y1)=(0,0,0,0,1,0).

Utilizzando il metodo di eliminazione di Gauss, troviamo le somme di alcuni di tali vettori che danno il vettore nullo.

Per esempio v2(y1)+ v2(y2)+ v2(y5)=(0,0,0,0,0,0), e se si pone

x=r1r2r5=1110707425, y=2⁸3²5⁰7³13⁰17⁰=790272, x-y=1109917153,d=mcd(1109917153,n)=n.

Questa somma che dà il vettore nullo non fornisce un divisore non banale di n.

Ma è anche v2(y1)+ v2(y2)+ v2(y3)+v2(y4)+v2(y6)=(0,0,0,0,0,0), e se si pone

x=r1r2r3r4r6 , y=2²⁰3⁸5⁰7⁸13²17² questa volta si ottiene, d=mcd(x-y,n)=547, divisore non banale di n.