Quadratic Sieve

The Quadratic Sieve is one of the most efficient algorithms for factoring large integers up to about 100 digits. It combines elements of linear algebra and number theory to find factors by constructing a system of linear equations over a finite field. The algorithm is particularly effective for numbers that are products of two large primes of similar size.

Algorithm Overview

The Quadratic Sieve works by finding smooth numbers (numbers with only small prime factors) that are congruent to perfect squares modulo n. These relations are then used to construct a system of linear equations, whose solution leads to a non-trivial factorization of n.

Mathematical Foundation

The algorithm is based on the following principle: if we can find integers x and y such that:

and , then and are non-trivial factors of n.

Time and Space Complexity

The time complexity of the Quadratic Sieve is:

The space complexity is for storing the factor base and relations.

JavaScript Implementation

code.js
1function quadraticSieve(n) {
2    // Factor base generation
3    const factorBase = generateFactorBase(n);
4    const relations = [];
5    
6    // Sieving phase
7    const sieveArray = new Array(sieveSize).fill(0);
8    for (let i = 0; i < factorBase.length; i++) {
9        const p = factorBase[i];
10        const roots = tonelliShanks(n, p);
11        for (const root of roots) {
12            for (let j = root; j < sieveSize; j += p) {
13                sieveArray[j] += Math.log(p);
14            }
15        }
16    }
17    
18    // Finding smooth numbers
19    for (let i = 0; i < sieveSize; i++) {
20        if (Math.abs(sieveArray[i] - Math.log(i * i - n)) < threshold) {
21            const factors = factorize(i * i - n, factorBase);
22            if (factors) {
23                relations.push({
24                    x: i,
25                    factors: factors
26                });
27            }
28        }
29    }
30    
31    // Linear algebra phase
32    const matrix = buildMatrix(relations, factorBase);
33    const solution = solveLinearSystem(matrix);
34    
35    // Factorization phase
36    return findFactors(n, relations, solution);
37}
38
39// Helper function for Tonelli-Shanks algorithm
40function tonelliShanks(n, p) {
41    // Implementation of Tonelli-Shanks algorithm
42    // Returns square roots of n modulo p
43}
44
45// Helper function for matrix operations
46function buildMatrix(relations, factorBase) {
47    // Build the matrix for linear algebra phase
48}
49
50function solveLinearSystem(matrix) {
51    // Solve the system of linear equations
52}
53
54function findFactors(n, relations, solution) {
55    // Use the solution to find factors
56}

Example Usage

The Quadratic Sieve is typically used for numbers that are too large to factor with simpler methods. For example:

code.js
1const n = 1234567890123456789012345678901234567890n;
2const factors = quadraticSieve(n);
3console.log(factors);

Optimization Techniques

Several optimizations can improve the performance of the Quadratic Sieve:

1. Using multiple polynomials to increase the yield of smooth numbers
2. Implementing block sieving to improve cache efficiency
3. Using parallel processing for the sieving phase
4. Optimizing the linear algebra phase with sparse matrix techniques

Limitations

The main limitations of the Quadratic Sieve are:

• Memory requirements grow with the size of the number
• Performance degrades for numbers with more than 100 digits
• Requires careful tuning of parameters for optimal performance
• Not suitable for numbers with many small prime factors

Applications

The Quadratic Sieve is particularly useful in:

• Cryptanalysis of RSA and other cryptographic systems
• Integer factorization competitions
• Research in number theory
• Breaking cryptographic keys