Crivello quadratico

Da Wikipedia, l'enciclopedia libera.

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 sorgente]

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 (\frac{n}{p})\neq1, dove con (\frac{n}{p}) 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}^{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=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.


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