##  [Quadratic Sieve](/quadratic-sieve-0) 

 Definition

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

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

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

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

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

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

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

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

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.