quadratic sieve
Algorithm
To factor a number using the quadratic sieve, one seeks
two numbers and which are not congruent modulo
with not congruent
to modulo but
have . If two such numbers are found,
one can then say that . Then,
and must have non-trivial factors in common with .
The quadratic sieve method of factoring depends upon being able
to create a set of numbers whose factorization can be expressed
as a product of pre-chosen primes. These factorizations are
recorded as vectors of the exponents. Once enough vectors are
collected to form a set which contains a linear dependence,
this linear dependence is exploited to find two squares which
are equivalent
modulo .
To accomplish this, the quadratic sieve method uses a set of
prime numbers called a factor base. Then, it searches for
numbers which can be factored entirely within that factor base.
If there are prime numbers in the factor base, then each
number which can be factored within the factor base is stored
as a -dimensional vector where the -th component
of the
vector for gives the exponent of the -th prime from the
factor base in the factorization of . For example, if the
factor base were , then
the number would be stored as the
vector .
Once of these vectors have been collected, there must be
a linear dependence among them. The vectors are taken
modulo to form vectors in . The linear dependence
among them is used to find a combination of the vectors which
sum up to the zero vector
in . Summing these vectors
is equivalent to multiplying the ’s to which they correspond.
And, the zero vector in signals a perfect square
.
To factor , chose a factor base such that and for each odd
prime in , is a quadratic residue of . Now,
start picking near and calculate . Clearly . If can be
completely factored by numbers in , then it is called
-smooth. If it is not -smooth, then discard and
and move on to a new choice of . If it is -smooth,
then store , , and the vector of its exponents for
the primes in . Also, record a copy of the exponent vector
with each component taken modulo .
Once vectors have been recorded, there must be a linear dependence among them. Using the copies of the exponent vectors that were taken modulo , determine which ones can be added together to form the zero vector. Multiply together the that correspond to those chosen vectors—call this . Also, add together the original vectors that correspond to the chosen vectors to form a new vector . Every component of this vector will be even. Divide each element of by . Form .
Because each , . If , then find some more -smooth numbers and try again. If is not congruent to modulo , then and are factors of .
Example
Consider the number The integer nearest its square root is . Given the factor base
, the first few -smooth values of are:
2 | 3 | 5 | 7 | 13 | ||
---|---|---|---|---|---|---|
4122 | 147875 | 0 | 0 | 3 | 1 | 2 |
4159 | 454272 | 7 | 1 | 0 | 1 | 2 |
4187 | 687960 | 3 | 3 | 1 | 2 | 1 |
4241 | 1143072 | 5 | 6 | 0 | 2 | 0 |
4497 | 3380000 | 5 | 0 | 4 | 0 | 2 |
4993 | 8087040 | 9 | 5 | 1 | 0 | 1 |
Using and , one obtains:
Which results in:
From there:
It may not be completely obvious why we required that be a quadratic residue of each in the factor base . One might intuitively think that we actually want the to be quadratic residues of instead. But, that is not the case.
We are trying to express as:
where
Because we end up squaring , there is no reason that the would need to be quadratic residues of .
So, why do we require that be a quadratic residue of each ? We can rewrite the as:
If we take that expression modulo for any for which the corresponding is non-zero, we are left with:
Thus, in order for to show up in a useful
solution, must be a quadratic residue of .
We would be wasting time and space to employ other
primes in our factoring and linear combinations.
Title | quadratic sieve |
---|---|
Canonical name | QuadraticSieve |
Date of creation | 2013-03-22 12:48:14 |
Last modified on | 2013-03-22 12:48:14 |
Owner | patrickwonders (217) |
Last modified by | patrickwonders (217) |
Numerical id | 9 |
Author | patrickwonders (217) |
Entry type | Algorithm![]() |
Classification | msc 11Y05 |
Classification | msc 11A51 |