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 .
  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.


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