Quadratic Sieve Method
The Quadratic Sieve (QS) algorithm is an advanced factorization technique that builds upon Fermat’s difference of squares method. It exploits quadratic relationships to efficiently find factors of a given integer \( n \).
The fundamental idea is to identify two numbers \( x \) and \( y \) such that:
\[ x^2 \equiv y^2 \pmod{n} \]
while ensuring that \( x \not\equiv \pm y \pmod{n} \).
This guarantees a nontrivial factorization, since:
\[ (x - y)(x + y) \equiv 0 \pmod{n} \]
implying that at least one of these factors shares a common divisor with \( n \).
How does it work?
- Choosing the factor base \( B \)
The first step is selecting a set of small prime numbers, known as the factor base: \[ B = \{ p_1, p_2, \dots, p_k \} \] This set is chosen so that \( n \) is a quadratic residue modulo each \( p \in B \). That is, for every prime \( p \) in the factor base, the Legendre symbol must satisfy: \[ \left(\frac{n}{p}\right) = 1 \] When this condition holds, the congruence \( x^2 \equiv n \pmod{p} \) has solutions, which will be instrumental in later steps. - Generating candidate values \( b_i \)
Next, we generate a sequence of integers centered around \( \sqrt{n} \): \[ b_i = \lfloor \sqrt{n} \rfloor + i, \quad i = 1, 2, 3, \dots, T \] For each \( b_i \), we compute: \[ q(b_i) = b_i^2 - n \] These values serve as potential candidates for full factorization over the selected factor base. - Testing for smoothness
A key step in the process is determining whether each \( q(b_i) \) can be completely decomposed into primes from the factor base \( B \). If a number meets this criterion, its factorization is stored for later use. The goal is to accumulate a sufficient number of such factorizations. - Constructing a quadratic congruence
Once enough factored values of \( q(b_i) \) have been collected, we use linear algebra techniques (such as Gaussian elimination) to identify a subset of these numbers whose product forms a perfect square. In other words, we seek integer exponents \( e_i \) such that: \[ \prod_{i} q(b_i)^{e_i} = \text{perfect square} \] This step ultimately yields a congruence of the form: \[ x^2 \equiv y^2 \pmod{n} \] - Extracting the factors
At this stage, we have a relation that can be leveraged to compute nontrivial divisors of \( n \). If \( x \neq \pm y \pmod{n} \), then computing: \[ \gcd(n, x - y) \quad \text{and} \quad \gcd(n, x + y) \] reveals a nontrivial factor of \( n \).
A Practical Example
Let’s walk through the Quadratic Sieve (QS) algorithm step by step to factorize the number 2041, explaining each stage in detail.
$$ n = 2041 $$
The first step is selecting an initial factor base of small primes.
\[ B = \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29\}\]
To determine which primes should be included, we compute the Legendre symbol \( \left(\frac{2041}{p}\right) \).
If \( \left(\frac{2041}{p}\right) = 1 \), then \( p \) is included in the factor base; otherwise, it is discarded.
| Prime \( p \) | \( \left( \frac{2041}{p} \right) \) | Included in \( B \)? |
|---|---|---|
| 2 | \( 2041 \mod 8 = 1 \) | ✅ Yes |
| 3 | \( \left( \frac{2041}{3} \right) = 1 \) | ✅ Yes |
| 5 | \( \left( \frac{2041}{5} \right) = 1 \) | ✅ Yes |
| 7 | \( \left( \frac{2041}{7} \right) = 1 \) | ✅ Yes |
| 11 | \( \left( \frac{2041}{11} \right) = -1 \) | ❌ No |
| 13 | \( \left( \frac{2041}{13} \right) = 0 \) | ❌ No |
| 17 | \( \left( \frac{2041}{17} \right) = 1 \) | ✅ Yes |
| 19 | \( \left( \frac{2041}{19} \right) = -1 \) | ❌ No |
| 23 | \( \left( \frac{2041}{23} \right) = -1 \) | ❌ No |
| 29 | \( \left( \frac{2041}{29} \right) = -1 \) | ❌ No |
Note: The Legendre symbol for odd primes is computed using Euler’s criterion: \[ \left(\frac{n}{p}\right) \equiv n^{\frac{p-1}{2}} \pmod{p} \] For \( p = 2 \), the condition \( n \equiv 1 \pmod{8} \) applies. Since: $$ 2041 \equiv 1 \pmod{8} $$ 2 is included in the factor base. Similarly, for \( p = 3 \), we use Euler’s formula: \[ \left(\frac{2041}{3}\right) \equiv 2041^{\frac{3-1}{2}} \pmod{3} \] \[ \left(\frac{2041}{3}\right) \equiv 2041^1 \pmod{3} \] \[ \left(\frac{2041}{3}\right) \equiv 1 \pmod{3} \] which confirms that 3 belongs in the factor base.
The refined factor base is:
\[ B = \{2, 3, 5, 7, 17\} \]
Next, we generate candidate values \( b_i \) starting from:
\[ \lfloor \sqrt{2041} \rfloor = 45 \]
We then compute:
\[ q(b_i) = b_i^2 - 2041 \]
and check whether each \( q(b_i) \) fully factorizes over \( B \).
| \( b_i \) | \( q(b_i) = b_i^2 - 2041 \) | Factorization | Factor Base? (2,3,5,7,17) |
|---|---|---|---|
| 45 | \( -16 \) | \( (-1) \cdot 2^4 \) | ✅ Yes |
| 46 | \( 75 \) | \( 3^1 5^2 \) | ✅ Yes |
| \( 47 \) | \( 2209 - 2041 = 168 \) | \( 2^3 3^1 7^1 \) | ✅ Yes |
| \( 48 \) | \( 2304 - 2041 = 263 \) | \( \color{red}{263} \) | ❌ No |
| \( 49 \) | \( 2401 - 2041 = 360 \) | \( 2^3 3^2 5^1 \) | ✅ Yes |
| \( 50 \) | \( 2500 - 2041 = 459 \) | \( 3^3 17^1 \) | ✅ Yes |
| \( 51 \) | \( 2601 - 2041 = 560 \) | \( 2^4 5^1 7^1 \) | ✅ Yes |
| \( 52 \) | \( 2704 - 2041 = 663 \) | \( 3^1 \color{red}{13^1} 17^1 \) | ❌ No |
| 53 | \( 768 \) | \( 2^8 3^1 \) | ✅ Yes |
| \( 54 \) | \( 2916 - 2041 = 875 \) | \( 5^3 7^1 \) | ✅ Yes |
Now, we seek a subset of these values whose product forms a perfect square.
We find:
$$ q(46) = 3^1 5^2 $$
$$ q(53) = 2^8 3^1 $$
Multiplying them together:
$$ 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 $$
confirming that the product is a perfect square.
Now, we compute \( x \) and \( y \):
$$ y = 2^4 3^1 5^1 = 240 $$
$$ x = 46 \cdot 53 \pmod{2041} = 2438 \equiv 397 \pmod{2041} $$
Thus:
$$ x^2 \equiv y^2 \pmod{2041} $$
We compute the greatest common divisor:
\[ \gcd(x - y, 2041) = \gcd(397 - 240, 2041) = \gcd(157, 2041) = 157 \]
which yields one factor of 2041. Similarly:
\[ \gcd(x + y, 2041) = \gcd(397 + 240, 2041) = \gcd(637, 2041) = 13 \]
Thus, we have successfully factorized 2041:
\[ 2041 = 13 \times 157 \]
The Quadratic Sieve has efficiently decomposed \( n \) into its prime factors.
Additional Notes
Further insights into the Quadratic Sieve method.
- The Quadratic Sieve is among the most efficient algorithms for factoring moderately large integers
It performs exceptionally well for numbers up to around 100 digits. For significantly larger integers, the Number Field Sieve (NFS), the most powerful general-purpose factorization algorithm, becomes the preferred method. - Asymptotic complexity
While the Quadratic Sieve is considerably faster than older factorization methods, its runtime still grows sub-exponentially. Specifically, it operates in \( O(e^{(c + o(1)) \sqrt{\log n \log \log n}}) \), making it infeasible for extremely large numbers compared to the NFS, which has a better asymptotic complexity.
And so forth.
