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 $\left({\frac {n}{p}}\right)\neq 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 {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.

Collegamenti esterni

• (EN) Eric W. Weisstein, Crivello quadratico, su MathWorld, Wolfram Research.