Crivello quadratico

Il crivello quadratico è un algoritmo di fattorizzazione creato da Carl Pomerance. Questo algoritmo è particolarmente famoso perché nel 1994 ha fattorizzato il numero RSA-129, composto da 129 cifre in base dieci.

Algoritmo

L'algoritmo consta di 8 passi:

1)Viene dato in input il numero naturale dispari $n>1$.

2)Si sceglie un naturale $k>0$.

3)Si esaminano tutti i primi $p \leq k$ e si eliminano tutti i primi dispari tali che $(\frac{n}{p})\neq1$, dove con $(\frac{n}{p})$ si intende il simbolo di legendre, e si ottiene così la base di fattori $B={p_1,p_2,\dots,p_t}$.

4)Facendo assumere ad $r$ valori interi successivi a $\lfloor \sqrt{n} \rfloor$, si trovano almeno $t+1$ valori $y=r^2-n$ che abbiano tutti i loro fattori primi in B.

5)Per ognuno dei valori $y_1, y_2,\dots,y_{t+1}$ si calcola il vettore in $\mathbb{Z}_{2}^{t}: v_2(y_i)=(e_1,e_2,\dots,e_t)$ dove $e_i$ è la riduzione modulo 2 dell'esponente di $p_i$ nella fattorizzazione di $y_i$.

6)Con il metodo di eliminazione di Gauss si determinano alcuni dei vettori $v_2(y_i)$ che danno somma uguale al vettore nullo.

7)Si pone $x$ uguale al prodotto degli $r_i$ corrispondenti agli $y_i$ trovati nel passo 6) e si pone y uguale al prodotto delle potenze di $p_1,p_2,\dots,p_t$ con esponenti uguali alla semisomma degli esponenti della fattorizzazione degli stessi $y_i$.

8)Si calcola $d=mcd(x-y,n)$ e se $1<d<n$ allora $d$ è divisore non banale di $n$, altrimenti si torna al passo 2) con una scelta di $k$ più grande.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica