Quadratic Sieve
The quadratic sieve finds x with x^2≡y^2 (mod n), so gcd(x±y,n) may reveal a factor; it is the fastest factoring method below 100 digits.
Purpose
To factor integers of medium size (~100 digits) as fast as possible.
Mechanism
Find many x_i such that x_i^2 mod n is B-smooth, then use linear algebra over GF(2) to combine them so the product of squares is a perfect square. The combination yields X^2≡Y^2 (mod n), and gcd(X±Y,n) may be non-trivial.
Use cases
- Integer factorization
- Cryptanalysis
- Number-theoretic algorithms