Crivello quadratico
![Abbozzo](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0e/Puzzle_stub.svg/45px-Puzzle_stub.svg.png)
Questa voce sull'argomento teoria dei numeri è solo un abbozzo.
Contribuisci a migliorarla secondo le convenzioni di Wikipedia.
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:
- Viene dato in input il numero naturale dispari .
- Si sceglie un naturale .
- Si esaminano tutti i primi e si eliminano tutti i primi dispari tali che , dove con si intende il simbolo di Legendre, e si ottiene così la base di fattori .
- Facendo assumere ad valori interi successivi a , si trovano almeno valori che abbiano tutti i loro fattori primi in .
- Per ognuno dei valori si calcola il vettore in dove è la riduzione modulo dell'esponente di nella fattorizzazione di .
- Con il metodo di eliminazione di Gauss si determinano alcuni dei vettori che danno somma uguale al vettore nullo.
- Si pone uguale al prodotto degli corrispondenti agli trovati nel passo 6) e si pone uguale al prodotto delle potenze di con esponenti uguali alla semisomma degli esponenti della fattorizzazione degli stessi .
- Si calcola e se allora è divisore non banale di , altrimenti si torna al passo 2) con una scelta di più grande.
Collegamenti esterni
- (EN) Eric W. Weisstein, Crivello quadratico, su MathWorld, Wolfram Research.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)