The quadratic sieve is a sieving procedure that can be used in conjunction with Dixon's factorization method to factor
large numbers 
.
Pick values of 
given by
 |
(1)
|
where 
,
2, ... and 
is the floor function. We are then looking for
factors 
such that
 |
(2)
|
which means that only numbers with Legendre symbol 
(less than 
for trial divisor 
, where 
is the prime counting
function) need be considered. The set of primes
for which this is true is known as the factor base.
Next, the congruences
 |
(3)
|
must be solved for each 
in the factor base. Finally,
a sieve is applied to find values of 
which can be factored completely using only the factor base. Gaussian
elimination is then used as in Dixon's
factorization method in order to find a product of the 
s, yielding a perfect square.
The method requires about 
steps, improving on the continued
fraction factorization algorithm by removing the 2 under the square
root (Pomerance 1996). The use of multiple polynomials
gives a better chance of factorization, requires a shorter sieve interval, and is
well suited to parallel processing.
Januszewski and Heinrichs (2026) reported a GPU-based self-initializing quadratic sieve factorization of RSA-155, a 155-digit, 512-bit RSA number. They report 700.6 GPU-hours using 64 H100 GPUs for sieving and one H100 for linear algebra, and identify this as the largest quadratic-sieve factorization then known. RSA-155 had already been factored with the number field sieve in 1999, so this is an algorithm-specific record rather than a new factorization of the challenge (Januszewski and Heinrichs 2026).
A type of quadratic sieve can also be used to generate the prime numbers by considering the parabola 
. Consider the points lying on the parabola with integer
coordinates 
for 
,
3, .... Now connect pairs of integer points lying on the two branches of the parabola,
above and below the 
-axis.
Then the points where these lines intersect the
-axis correspond to composite numbers,
while those integer points on the positive 
-axis which are not crossed by any lines are prime numbers.
