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[modifica | modifica wikitesto]

L'algoritmo consta di 8 passi:

Viene dato in input il numero naturale dispari $n>1$ .
Si sceglie un naturale $k>0$ .
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}\}$ .
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$ .
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}$ .
Con il metodo di eliminazione di Gauss si determinano alcuni dei vettori $v_{2}(y_{i})$ che danno somma uguale al vettore nullo.
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}$ .
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.