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\le k$ e si eliminano tutti i primi dispari tali che $\left(\frac{n}{p}\right)\ne 1$, dove con $\left(\frac{n}{p}\right)$ 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\mathbb{Z}{)}^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=\mathrm{m}\mathrm{c}\mathrm{d}(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.

Collegamenti esterni

• Template:Collegamenti esterni