Il metodo del crivello quadratico
L'algoritmo del crivello quadratico (QS, Quadratic Sieve) è un miglioramento del metodo delle differenze di quadrati di Fermat e si basa sulla ricerca di relazioni quadratiche che permettono di trovare i fattori di un numero \( n \).
L'obiettivo è trovare due numeri \( x \) e \( y \) tali che:
\[ x^2 \equiv y^2 \pmod{n} \]
ma con \( x \not\equiv \pm y \pmod{n} \).
Questo porta a una fattorizzazione, poiché:
\[ (x - y)(x + y) \equiv 0 \pmod{n} \]
Quindi uno dei due fattori deve condividere un fattore primo con \( n \).
Come funziona?
- Scelta della base di fattorizzazione \( B \)
Si sceglie un insieme di primi piccoli \( B = \{ p_1, p_2, \dots, p_k \} \), chiamato base di fattorizzazione, tale che \( n \) sia un residuo quadratico rispetto a ciascuno di essi. Questo significa che, per ogni \( p \in B \), il simbolo di Legendre deve essere: \[ \left(\frac{n}{p}\right) = 1 \] Se questa condizione è verificata, il numero \( n \) ammette soluzioni della congruenza \( x^2 \equiv n \pmod{p} \), che saranno usate nei passaggi successivi. - Generazione dei candidati \( b_i \)
Si scelgono interi della forma: \[ b_i = \lfloor \sqrt{n} \rfloor + i, \quad i = 1, 2, 3, \dots, T \] e si calcolano i corrispondenti valori di: \[ q(b_i) = b_i^2 - n \] Questi numeri saranno testati per vedere se si fattorizzano completamente nella base \( B \). - Test di fattorizzabilità
Si verifica se ogni \( q(b_i) \) può essere scomposto solo con i primi della base \( B \). Per ogni \( b_i \) che soddisfa questa condizione, si memorizza la sua scomposizione. Si annotano i numeri che passano il test. - Costruzione di una relazione quadratica
Una volta raccolti abbastanza numeri \( q(b_i) \) che si fattorizzano su \( B \), si usa l’eliminazione di Gauss per trovare un insieme di esponenti tali che il prodotto dei corrispondenti \( q(b_i) \) dia un quadrato perfetto. In pratica, si trovano coefficienti \( e_i \) tali che: \[ \prod_{i} q(b_i)^{e_i} = \text{quadrato perfetto} \] Questa combinazione di numeri genera una relazione della forma: \[ x^2 \equiv y^2 \pmod{n} \] - Calcolo dei fattori
A questo punto, si ha una relazione che può essere risolta per trovare i divisori di \( n \). Se \( x \neq \pm y \pmod{n} \), allora il massimo comun divisore (MCD) di \( n \) con \( x - y \) e \( x + y \) fornisce un fattore non banale di \( n \).
Un esempio pratico
Utilizzo il metodo del crivello quadratico (Quadratic Sieve, QS) per trovare la fattorizzazione del numero 2041 spiegando ogni passaggio nel dettaglio.
$$ n = 2041 $$
Per prima cosa scelgo una base iniziale di numeri primi molto piccoli.
\[ B = \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29\}\]
Poi verifico quali numeri primi devono essere inclusi, calcolando il simbolo di Legendre \( \left(\frac{2041}{p}\right) \).
Se \( \left(\frac{2041}{p}\right) = 1 \) il numero primo viene incluso nella base di fattorizzazione, altrimenti viene scartato.
| Primo \( p \) | \( \left( \frac{2041}{p} \right) \) | Incluso in \( B \)? |
|---|---|---|
| 2 | \( 2041 \mod 8 = 1 \) | ✅ Incluso |
| 3 | \( \left( \frac{2041}{3} \right) = 1 \) | ✅ Incluso |
| 5 | \( \left( \frac{2041}{5} \right) = 1 \) | ✅ Incluso |
| 7 | \( \left( \frac{2041}{7} \right) = 1 \) | ✅ Incluso |
| 11 | \( \left( \frac{2041}{11} \right) = -1 \) | ❌ Escluso |
| 13 | \( \left( \frac{2041}{13} \right) = 0 \) | ❌ Escluso |
| 17 | \( \left( \frac{2041}{17} \right) = 1 \) | ✅ Incluso |
| 19 | \( \left( \frac{2041}{19} \right) = -1 \) | ❌ Escluso |
| 23 | \( \left( \frac{2041}{23} \right) = -1 \) | ❌ Escluso |
| 29 | \( \left( \frac{2041}{29} \right) = -1 \) | ❌ Escluso |
Nota. Il simbolo di Legendre si calcola sui numeri dispari usando la formula di Eulero \[ \left(\frac{n}{p}\right) \equiv n^{\frac{p-1}{2}} \pmod{p} \] Nel caso particolare del numero primo $ p = 2 $ si usa la formula $ n \equiv 1 \mod 8 $. Ad esempio, in questo caso $$ 2041 \equiv 1 \mod 8 $$ Quindi, il numero 2 è incluso nella base di fattorizzazione B. Nel caso del numero $ p = 3 $, invece, uso la formula di Eulero per calcolare il simbolo di Legendre \[ \left(\frac{2041}{3}\right) \equiv 2041^{\frac{3-1}{2}} \pmod{3} \] \[ \left(\frac{2041}{3}\right) \equiv 2041^{\frac{2}{2}} \pmod{3} \] \[ \left(\frac{2041}{3}\right) \equiv 2041 \equiv 1 \pmod{3} \] Quindi, il numero 3 è incluso nella base di fattorizzazione, e via dicendo.
Ora la base di fattorizzazione è composta solo dai numeri primi che hanno soddisfatto la verifica iniziale.
\[ B = \{2, 3, 5, 7, 17 \} \]
A questo punto posso generare dei candidati \( b_i \) a partire dal numero intero seguente:
\[ \lfloor \sqrt{2041} \rfloor = 45 \]
Quindi, calcolo \( q(b_i) = b_i^2 - n \) per diversi valori di \( b_i \).
\[ q(b_i) = b_i^2 - 2041 \]
Poi fattorizzo i valori di \( q(b_i) \) per verificare quali si scompongono esclusivamente nella base \( B = \{2, 3, 5, 7, 17\} \).
| \( b_i \) | \( q(b_i) = b_i^2 - 2041 \) | Fattori | B-numero (2,3,5,7,17) |
|---|---|---|---|
| \( 45 \) | \( 2025 - 2041 = -16 \) | \( (-1) \cdot 2^4 \) | ✅ si |
| \( 46 \) | \( 2116 - 2041 = 75 \) | \( 3^1 5^2 \) | ✅ si |
| \( 47 \) | \( 2209 - 2041 = 168 \) | \( 2^3 3^1 7^1 \) | ✅ si |
| \( 48 \) | \( 2304 - 2041 = 263 \) | \( \color{red}{263} \) | ❌ no (escluso) |
| \( 49 \) | \( 2401 - 2041 = 360 \) | \( 2^3 3^2 5^1 \) | ✅ si |
| \( 50 \) | \( 2500 - 2041 = 459 \) | \( 3^3 17^1 \) | ✅ si |
| \( 51 \) | \( 2601 - 2041 = 560 \) | \( 2^4 5^1 7^1 \) | ✅ si |
| \( 52 \) | \( 2704 - 2041 = 663 \) | \( 3^1 \color{red}{13^1} 17^1 \) | ❌ no (escluso) |
| \( 53 \) | \( 2809 - 2041 = 768 \) | \( 2^8 3^1 \) | ✅ si |
| \( 54 \) | \( 2916 - 2041 = 875 \) | \( 5^3 7^1 \) | ✅ si |
Una volta esclusi i valori di \( q(b_i) \) che non si fattorizzano con la base, cerco una combinazione tra i numeri ammessi (B-numeri) tali che il prodotto dei \( q(b_i) \) sia un quadrato perfetto.
Nota.Se non avessi trovato almeno due valori il cui prodotto fosse un quadrato perfetto, avrei dovuto generare altri valori \( q \) o, eventualmente, ampliare la base \( B \) con ulteriori numeri primi.
Analizzando i valori, trovo che il prodotto di questi due numeri è un quadrato perfetto
$$ q(46) = 3^1 5^2 $$
$$ q(53) = 2^8 3^1 $$
Infatti, moltiplicandoli tra loro gli esponenti dei fattori sono tutti pari
$$ q(46) \cdot q(53) = (3^1 5^2) \cdot (2^8 3^1 ) = 2^8 3^2 5^2 = ( 2^4 3^1 5^1 )^2 $$
Nota. Se avessi trovato un valore $ q=0 $ avrei trovato già un valore \( b_i \) che è divisore di $ n=2041 $.
Ho trovato una combinazione di numeri $ q(46) \cdot q(53) $ che, moltiplicati insieme, formano un quadrato perfetto.
Ora posso costruire la relazione quadratica necessaria per fattorizzare $ 2041 $ con il crivello quadratico.
Procedo con il calcolo di x e y.
$$ y = 2^4 3^1 5^1 = 240 $$
$$ x = 46 \cdot 53 \pmod{2041} = 2438 \equiv 397 \pmod{2041} $$
Quindi, ho trovato che $ y=240 $ e $ x=397 $
Questi due numeri soddisfano la relazione nella forma:
\[ x^2 \equiv y^2 \pmod{n} \]
A questo punto posso calcolare il massimo comune divisore di $ x-y $ ( oppure $ x+y $ ) e $ n=2041 $.
\[ MCD(x - y, 2041) = \gcd(397 - 240, 2041) = \gcd(157, 2041) = 157 \]
In questo modo ho trovato un fattore del numero 2041.
In alternativa avrei anche potuto calcolare \[ MCD(x + y, 2041) = \gcd(397 + 240, 2041) = \gcd(637, 2041) = 13 \]
Una volta trovato un fattore ( $ 157 $ ) del numeri da fattorizzare, posso trovare l'altro facilmente
$$ \frac{2041}{157} = 13 $$
Quindi, i fattori di 2041 sono 13 e 157.
\[ 2041 = 13 \times 157 \]
Ho così ottenuto la fattorizzazione completa di \( 2041 \):
Note
Alcune note aggiuntive sul metodo del crivello quadratico.
- Il crivello quadratico è uno dei più efficienti per la fattorizzazione di numeri interi di medie dimensioni
E' molto efficiente per numeri fino a 100 cifre, e per numeri ancora più grandi esiste un miglioramento chiamato Crivello dei campi di numeri (NFS, Number Field Sieve). - Costo computazionale esponenziale
Come tutti gli algoritmi di fattorizzazione anche il crivello quadratico ha un costo computazionale esponenziale.
E così via.
