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.

AlgoritmoModifica

L'algoritmo consta di 8 passi:

  1. Viene dato in input il numero naturale dispari  .
  2. Si sceglie un naturale  .
  3. 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  .
  4. Facendo assumere ad   valori interi successivi a  , si trovano almeno   valori   che abbiano tutti i loro fattori primi in  .
  5. Per ognuno dei valori   si calcola il vettore in   dove   è la riduzione modulo   dell'esponente di   nella fattorizzazione di  .
  6. Con il metodo di eliminazione di Gauss si determinano alcuni dei vettori   che danno somma uguale al vettore nullo.
  7. 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  .
  8. Si calcola   e se   allora   è divisore non banale di  , altrimenti si torna al passo 2) con una scelta di   più grande.
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica