A general-purpose integer factorization algorithm that searches for congruences of squares modulo the target n by collecting many values that factor completely over a chosen factor base and combining them via linear algebra to produce a square mod n.

Principle

Find integers x such that x^2 mod n is B-smooth (i.e., factors completely over a factor base); record exponent vectors mod 2 for these relations and solve a linear system to obtain a subset whose product yields a square congruence, then compute a gcd to extract factors.

Demonstration

For a moderate n, choose a factor base of small primes, sieve values of x around sqrt(n) to find B-smooth x^2 - n, collect enough relations, compute a nullspace vector mod 2, multiply corresponding relations to get y^2 ≡ z^2 (mod n) and then gcd(|y-z|, n) may produce a nontrivial factor.

Misapplication

Choosing an inadequate factor base or failing to collect sufficiently many smooth relations, or applying the quadratic sieve to sizes where the number-field sieve is asymptotically superior without justification.

Consequence

Very effective for numbers of certain intermediate sizes: significantly faster than trial division and Pollard Rho for large semiprimes up to a threshold; requires substantial memory and linear algebra but is practical and parallelizable.

Reversal

Instead of sieving a quadratic polynomial over integers, use algebraic number fields to produce smoother norms and relations (as in the number field sieve) to push the practical limit much higher.

Boundary

A general-purpose sieve suited to medium-to-large integers but outperformed asymptotically by the number field sieve for very large inputs; it assumes the ability to find many B-smooth values and excludes specialized algorithms tuned to specific structure.

Semantic Tension

Competes with the number field sieve: both collect relations and solve linear systems, but QS works with quadratic polynomials and integer factor bases while NFS exploits algebraic number fields for better asymptotic behaviour.

Synthesis

The quadratic sieve turns the problem of factoring into one of finding many smooth quadratic residues, using sieving and linear algebra to combine relations into a congruence of squares that yields nontrivial factors via gcd.