When seeking to factor a number N, one would be delighted to know that N = a^2 - b^2. Using the high school algebra identity we have the factorization N = (a+b)(a-b) which is often a non-trivial factorization. Every odd composite N can be factored this way, and there is a bona fide factorization method with this spirit. A naive random search for a and b would not be efficient, so the first clever thing that needs to be done is accelerate the search using residue information from the rejected candidates. We will also see how the method neatly makes use of sieving the values of quadratic polynomials to get algorithmic speedups, hence the name ´Quadratic Sieve Factorization´.

The method is historically prominent as a fast, subexponential factoring algorithm. It is also a direct ancestor to the more complex number field sieve algorithm. We will understand how the quadratic sieve factorization method works, why it works well and natural ways to organize the computation.