Lezione del 26 maggio 2007
Nel ragionamento alla base dell’algoritmo del crivello quadratico di Pomerance, è 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 pB 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 nr2 (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 pK, 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 pK 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=r2-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, che non consente l’esito positivo dell’algoritmo)
Prima di dare un esempio di fattorizzazione mediante l’algoritmo del crivello 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 ki 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 ki (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, …., jkm).
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 vjh 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 pK sono 2,3,5,7,11,13.
Calcoliamo per ogni primo >2 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)=(22/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)=-(22/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 4105,4106,4107,….. e per ognuno calcolando y=r2-n, si cercano t+1=6 valori y che abbiano tutti i loro fattori primi in B, e si trovano:
r1= 4122 ; y1 = 20305371132 ; v(y1)=(0,0,3,1,2), v2(y1)=(0,0,1,1,0) r2= 4159 ; y2 = 27315071132 ; v(y2)=(7,1,0,1,2), v2(y2)=(1,1,0,1,0) r3= 4187 ; y3 = 23335172131 ; v(y3)=(3,3,1,2,1), v2(y3)=(1,1,1,0,1) r4= 4241 ; y4 = 25365072130 ; v(y4)=(5,6,0,2,0), v2(y4)=(1,0,0,0,0) r5= 4497; y5 = 25305470132 ; v(y5)=(5,0,4,0,2), v2(y5)=(1,0,0,0,0) r6= 4993 ; y6 = 29355170131 ; 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=26345171131=2358720, x-y=18546971,d=mcd(18546971,n)=65537 e abbiamo trovato un divisore d=65537 non banale di n: in effetti n=65537257.
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=r2-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)0, mentre se y<0 la fattorizzazione di y comprende un fattore (-1)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 pK sono 2,3,5,7,11,13,17.
Calcolando per ognuno dei primi >2 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-26=1023 a 1049+26=1075, e per ogni r calcolando y=r2-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)1243273130170 ; v(y1)=(1,4,2,3,0,0), v2(y1)=(1,0,0,1,0,0) r2= 1033 ; y2 =-32928=(-1)1253173130170 ; v(y1)=(1,5,1,3,0,0), v2(y1)=(1,1,1,1,0,0) r3= 1043 ; y3 =-12168=(-1)1233270132170 ; v(y1)=(1,3,2,0,2,0), v2(y1)=(1,1,0,0,0,0) r4= 1047 ; y4 =-3808=(-1)1253071130171 ; v(y1)=(1,5,0,1,0,1), v2(y1)=(1,1,0,1,0,1) r5= 1049; y5 =384=(-1)0273170130170 ; v(y1)=(0,7,1,0,0,0), v2(y1)=(0,1,1,0,0,0) r6= 1061 ; y6 =25704=(-1)0233371130171 ; v(y1)=(0,3,3,1,0,1), v2(y1)=(0,1,1,1,0,1) r7= 1063 ; y6 =29952=(-1)0283270131170 ; 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=28325073130170=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=220385078132172 questa volta si ottiene, d=mcd(x-y,n)=547, divisore non banale di n.
Crittografia.
E’ la scienza che studia la possibilità che un soggetto A (mittente) spedisca un messaggio ad un utente B (destinatario) attraverso un canale di comunicazione non sicuro, in modo che un soggetto C (intruso) non sia in grado, intercettando il messaggio, di conoscere le informazioni in esso contenuto.
Anticamente il concetto di ”messaggio” era ristretto ad un messaggio alfa-numerico, cioè costituito da caratteri alfabetici, numerici, e segni di interpunzione.
Attualmente, con l’avvento dei canali digitali, il concetto di “messaggio” ha un significato più ampio: è una successione di bits 0,1 (che può rappresentare qualunque tipo di informazione, per esempio un file audio-video) che vengono trasmessi attraverso il canale.
Per trasformare un messaggio di testo in una successione di bits, si possono usare delle codifiche concordate dagli utenti: uno dei codici più usati è il codice ASCII che trasforma ogni carattere alfanumerico in un byte di 8 bits, corrispondente ad un numero binario compreso fra 0 e 255, secondo una convenzione internazionale.
La successione di bits che forma il messaggio può essere suddivisa in “blocchi” più piccoli di lunghezza prefissata, che possono essere interpretati come numeri binari di grandezza limitata.
In generale dunque si fisserà un intero N>0 e si definirà “messaggio” un qualunque numero intero x nell’insieme IN={0,1,2,……,N-1} .
