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 ${\displaystyle n>1}$.
2. Si sceglie un naturale ${\displaystyle k>0}$.
3. Si esaminano tutti i primi ${\displaystyle p\leq k}$ e si eliminano tutti i primi dispari tali che ${\displaystyle \left({\frac {n}{p}}\right)\neq 1}$, dove con ${\displaystyle \left({\frac {n}{p}}\right)}$ si intende il simbolo di Legendre, e si ottiene così la base di fattori ${\displaystyle B=\{p_{1},p_{2},\dots ,p_{t}\}}$.
4. Facendo assumere ad ${\displaystyle r}$ valori interi successivi a ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$, si trovano almeno ${\displaystyle t+1}$ valori ${\displaystyle y=r^{2}-n}$ che abbiano tutti i loro fattori primi in ${\displaystyle B}$.
5. Per ognuno dei valori ${\displaystyle y_{1},y_{2},\dots ,y_{t+1}}$ si calcola il vettore in ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{t}:v_{2}(y_{i})=(e_{1},e_{2},\dots ,e_{t})}$ dove ${\displaystyle e_{i}}$ è la riduzione modulo ${\displaystyle 2}$ dell'esponente di ${\displaystyle p_{i}}$ nella fattorizzazione di ${\displaystyle y_{i}}$.
6. Con il metodo di eliminazione di Gauss si determinano alcuni dei vettori ${\displaystyle v_{2}(y_{i})}$ che danno somma uguale al vettore nullo.
7. Si pone ${\displaystyle x}$ uguale al prodotto degli ${\displaystyle r_{i}}$ corrispondenti agli ${\displaystyle y_{i}}$ trovati nel passo 6) e si pone ${\displaystyle y}$ uguale al prodotto delle potenze di ${\displaystyle p_{1},p_{2},\dots ,p_{t}}$ con esponenti uguali alla semisomma degli esponenti della fattorizzazione degli stessi ${\displaystyle y_{i}}$.
8. Si calcola ${\displaystyle d=\mathrm {mcd} (x-y,n)}$ e se ${\displaystyle 1<d<n}$ allora ${\displaystyle d}$ è divisore non banale di ${\displaystyle n}$, altrimenti si torna al passo 2) con una scelta di ${\displaystyle k}$ più grande.

Collegamenti esterni

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

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