Teoria dei numeri e Crittografia: lezione del 19 maggio 2011

Teoria dei numeri e Crittografia: lezione del 19 maggio 2011

Facciamo delle ultime considerazioni sull’algoritmo (p-1) di Pollard, illustrato nella lezione precedente.

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

.... p

le potenze p

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

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

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

-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

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

- 1,n)=mcd(b-1,n) (come si dimostra facilmente da a

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

-1, dunque d=mcd(a

-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

, p

,……., p

}

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

^{, p}

^{,...., p}

}

è possibile allora assumere k = p p

.... p

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

, ognuno con esponente k

, quindi p p

.... p

è 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

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

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>1 dispari, 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 un input n>1 dispari da fattorizzare, cerca di trovare r, s naturali, tali che r

s

(mod n): l’esistenza di r,s non garantisce però sempre l’esistenza di un divisore proprio di n (come invece avveniva nell’algoritmo di Fermat).

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), da cui 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 d=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 tali che r

s

(mod n) ?

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

B={p

, p

, ………, p

} (B è detta una “base di fattori”).

Facciamo variare r=  n ,  n +1,  n +2,…. e calcoliamo in corrispondenza il numero naturale y=r

-n (nel caso banale in cui tale numero è 0, si ha n=r

e si è trovato un divisore non banale r di n) : si ha yr

(mod n): se r è “vicino” a n , il valore di y è relativamente “piccolo”, quindi è probabile che i suoi fattori primi siano tutti nella base di fattori B (se K è scelto

“abbastanza grande”).

Supponiamo di avere costruito un certo numero di valori y=y

, y

, ….., y

(in corrispondenza di valori r=r

, r

, ….., r

) tali che ogni y

abbia tutti i suoi fattori primi in B: questa fase è quella cosiddetta del “crivello” (vedremo in seguito una scelta opportuna per il numero m degli elementi y

da costruire).

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

(facile da calcolare perché conosciamo i primi p

, p

, ………, p

tra i quali vi sono i fattori primi di y

):

y

= p

p

... p

i=1,2,…..,m

(con esponenti k

0: in particolare k

=0 se il primo p

non è presente nella fattorizzazione di y

).

Per costruzione si ha r

y

(mod n) per ogni i=1,2,…..,m (essendo y

= r

– n).

Dunque si ottengono m congruenze modulo n:

r

y

(mod n)

r

y

(mod n)

……

……

r

y

(mod n)

Se riuscissimo a determinare alcuni dei valori y

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 r

,) e potremmo (se r non é congruo s modulo n) trovare un divisore non banale di n.

Ma nel moltiplicare valori y

fra loro, i corrispondenti esponenti k

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 y

tali che, per ogni primo p

,la somma dei corrispondenti esponenti k

sia un multiplo di 2: ma come essere certi che esistano, fra y

, y

, ….., y

, alcuni y

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 y

che abbiamo trovato sia maggiore del numero t di primi nella “base di fattori” B , per es. m=t+1 (questa è la scelta “opportuna” per m).

Associamo ad ogni y

la t-upla di interi non negativi formata ordinatamente dagli esponenti k

che compaiono nella fattorizzazione di y

:

y

 v(y

) = (k

, k

,…….., k

)

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

y

 v

(y

) = (k

mod2, k

mod2 ,…….., k

mod2)

Possiamo trattare v

(y

) come vettore dello spazio vettoriale Z

sul campo Z

= {0,1} (dove identifichiamo [0] con 0, [1] con 1 e nel fare i calcoli sulle classi utilizziamo le riduzioni modulo 2).

Cercare (fra y

,….., y

) alcuni y

il cui prodotto sia un quadrato perfetto, equivale, per le considerazioni precedenti, a cercare (fra i vettori v

(y

),….., v

(y

)) una somma di alcuni dei vettori che dia il vettore nullo in Z

.

Poiché m>t, e poiché t è la dimensione dello spazio Z

, i vettori v

(y

) (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 vettori di tale combinazione che hanno coefficiente non nullo (quindi coefficiente =1), otteniamo una somma di alcuni dei vettori v

(y

),

…..,v

(y

) che dia il vettore nullo, e raggiungiamo il nostro obiettivo.

Dopo avere trovato questi vettori, se consideriamo i corrispondenti elementi (fra y

,…..,y

) 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(y

), e attribuendo i risultati come esponenti dei numeri primi p

, p

, ………, p

); si avrà inoltre r

s

(mod n) dove r è il prodotto dei valori r

corrispondenti agli elementi y

trovati.

Per trovare le somme di alcuni fra i vettori v

(y

) che danno come risultato il vettore nullo si può utilizzare il cosiddetto “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 y

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 m di vettori v

(y

) da manipolare (ricordiamo che deve essere m>B).

Possiamo però osservare che ogni primo pB che non sia “superfluo” (cioè che sia effettivamente divisore di qualcuno dei valori y

) deve essere tale che n sia un resto quadratico modulo p : infatti essendo y

=r

-n si ha nr

(mod p), se p è divisore di y

.

Per la teoria dei resti quadratici, sappiamo che, essendo l’input n dispari, n è sempre resto

quadratico modulo 2 (quindi il primo 2 non è mai “superfluo” in B); 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>2 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 p>2 tali che (n/p)1, costituendo la base di fattori B={p

, p

, ………, p

}

4) facendo assumere ad r valori interi successivi  n , si trovano 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 y

, y

, ….., y

si calcola la fattorizzazione in primi ed il vettore in Z

: v

(y

) = (e

, e

, ……, e

)

dove e

è la riduzione modulo 2 dell’esponente di p

nella fattorizzazione di y

6) con il metodo di eliminazione di Gauss si determinano alcuni dei vettori v

(y

) che danno somma uguale al vettore nullo

7) si pone r uguale al prodotto degli r

corrispondenti agli y

trovati nel passo 6) e si pone s uguale al prodotto delle potenze di p

, p

,…, p

ognuna con esponente uguale alla semisomma degli esponenti presenti nella fattorizzazione degli stessi y

8) si calcola d=mcd(x-y,n) e se 1<d<n si esce con “d è divisore non banale di n ed n=d(n/d)”

altrimenti si torna al passo 2) con una scelta di K più grande (si è verificato evidentemente il caso x y (mod n) e l’algoritmo non ha avuto successo).

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 Z

= {0,1} . Data una matrice con n 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 Z

)

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

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

Se sono dati m vettori in Z

con m>t:

v

= (a

, a

, …….., a

) v

= (a

, a

, …….., a

)

…..

…..

v

= (a

, a

, …….., a

)

per determinare quali somme di alcuni dei v

danno il vettore nullo si procede nel modo seguente.

A partire dalla matrice txm che ha come colonne le coordinate dei vettori v

: M = (a

) i=1,….,t, j=1,…..,m

si costruisce, con il metodo di Gauss, la matrice ridotta M

e si individuano le colonne di M

che non contengono nessun pivot, siano esse le colonne j

, j

, …., j

(con 1 j

, j

, …., j

m).

Per ognuno degli indici di colonna j

(con h=1,…,k) si costruisce una somma di vettori scelti fra i v

con il seguente criterio: uno degli addendi è il vettore v

e gli altri addendi sono i vettori v

con indice j diverso da j

, j

, …., j

e tali che vi sia valore =1 nella riga j, colonna j

.

Le somme di alcuni dei v

, v

, …., v

che danno il vettore nullo sono appunto le k somme costruite in tal modo e anche tutte le possibili combinazioni lineari di tali somme con coefficienti 0,1.

Esempio.

Sia m=6, t=5, e siano dati i seguenti 6 vettori in Z

: v

= (0,0,1,1,0)

v

= (1,1,0,1,0) v

= (1,1,1,0,1) v

= (1,0,0,0,0) v

= (1,0,0,0,0) v

= (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 v

+v

(l’indice 4 è l’unico 5,6 tale che vi sia valore =1 nella riga 4, colonna 5), mentre la seconda è la somma v

+v

(l’indice 3 è l’unico 5,6 tale che vi sia valore =1 nella riga 3, colonna 5).

Le 2 somme precedenti v

+v

, v

+v

e la loro (unica) combinazione lineare a coefficienti 0,1:

(v

+v

)+(v

+v

)

sono tutte le possibili somme di alcuni dei v

che danno il vettore nullo.

Esempio di fattorizzazione con il crivello quadratico.

Input n=16843009, con  n =4104.

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)

= -(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:

r

= 4122 ; y

= 2

3

5

7

13

; v(y

)=(0,0,3,1,2), v

(y

)=(0,0,1,1,0) r

= 4159 ; y

= 2

3

5

7

13

; v(y

)=(7,1,0,1,2), v

(y

)=(1,1,0,1,0) r

= 4187 ; y

= 2

3

5

7

13

; v(y

)=(3,3,1,2,1), v

(y

)=(1,1,1,0,1) r

= 4241 ; y

= 2

3

5

7

13

; v(y

)=(5,6,0,2,0), v

(y

)=(1,0,0,0,0) r

= 4497; y

= 2

3

5

7

13

; v(y

)=(5,0,4,0,2), v

(y

)=(1,0,0,0,0) r

= 4993 ; y

= 2

3

5

7

13

; v(y

)=(9,5,1,0,1), v

(y

)=(1,1,1,0,1)

Cerchiamo alcuni degli v

(y

) 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 v

(y

)+ v

(y

)=(0,0,0,0,0)

v

(y

)+ v

(y

)=(0,0,0,0,0)

v

(y

)+ v

(y

)+ v

(y

)+ v

(y

)=(0,0,0,0,0)

In corrispondenza della prima somma si trovano per esempio i valori r=r

r

=20905691, s=2

3

5

7

13

=2358720, r-s=18546971,d=mcd(r-s,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 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” y

.

Il problema è che, nel calcolare un prodotto degli y

che sia un quadrato perfetto (con la regola dei vettori di esponenti) l’eventuale segno negativo di alcuni y

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 convenzionale 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 anche un fattore (-1)

, mentre se y<0 la fattorizzazione di y comprende anche un fattore (-1)

(oltre che 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 =1048.

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} (notare l’aggiunta di -1), di cardinalità 6.

Facendo variare r da 1048-25=1023 a 1048+25=1073, 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:

r

= 1025 ; y

= -49392=(-1)

2

3

7

13

17

; v(y

)=(1,4,2,3,0,0), v

(y

)=(1,0,0,1,0,0)

r

= 1033 ; y

= -32928=(-1)

2

3

7

13

17

; v(y

)=(1,5,1,3,0,0), v

(y

)=(1,1,1,1,0,0) r

= 1043 ; y

=-12168=(-1)

2

3

7

13

17

; v(y

)=(1,3,2,0,2,0), v

(y

)=(1,1,0,0,0,0) r

= 1047 ; y

=-3808=(-1)

2

3

7

13

17

; v(y

)=(1,5,0,1,0,1), v

(y

)=(1,1,0,1,0,1) r

= 1049; y

=384=(-1)

2

3

7

13

17

; v(y

)=(0,7,1,0,0,0), v

(y

)=(0,1,1,0,0,0) r

= 1061 ; y

=25704=(-1)

2

3

7

13

17

; v(y

)=(0,3,3,1,0,1), v

(y

)=(0,1,1,1,0,1) r

= 1063 ; y

=29952=(-1)

2

3

7

13

17

; v(y

)=(0,8,2,0,1,0), v

(y

)=(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.

Una di queste è per esempio v

(y

)+ v

(y

)+ v

(y

)=(0,0,0,0,0,0), e se si pone

r=r

r

r

=1110707425, s=2

3

5

7

13

17

=790272, r-s=1109917153, d=mcd(r-s, n)=n.

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

Ma un’altra somma è anche v

(y

)+ v

(y

)+ v

(y

)+v

(y

)+v

(y

)=(0,0,0,0,0,0), e se si pone

r=r

r

r

r

r

, s=2

3

5

7

13

17

questa volta si ottiene, d=mcd(r-s,n)=547, divisore non banale di n.

Osservazione: nell’algoritmo si può anche decidere di costruire un numero m di y

che sia >t+1

(dove t è il numero di primi nella base di fattori), perché in tal modo il numero dei vettori è più

grande, e possono essere più numerose le somme di alcuni di essi che danno il vettore nullo, con

una maggiore possibilità che una di tali somme fornisca un divisore non banale di n .