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

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)\neq1, 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 (\Z/2\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.


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