Cryptography Reference
In-Depth Information
method. This variant includes
partial-partial relations
, i.e., relations corresponding
to values of
t
such that
Q
(
)
can be fully factored over the factor base plus two large
primes less than a given bound. The double large-prime method works similarly to
the single large-prime variation but with some additional complications derived from
the fact that the remaining cofactor in the interval
t
B
3
, after the primes in the
factor base have been factored out, can be either a prime or a product of two large
primes exceeding
B
. If the cofactor belongs to the interval
(
B
,
]
B
2
(
1
,
]
then it must be
B
2
B
3
prime, and if it belongs to
then a fast pseudoprimality test is applied to it.
If it passes the test it is discarded (as it is too large) but if proved composite then
it is factored by a method like Pollard rho, giving a partial-partial relation. Finally,
these double partial relations are combined by a cycle-finding algorithm in order to
produce additional full relations (see [60, 194] and their references for details).
(
,
]
6.4.9.2 The Multiple Polynomial Quadratic Sieve
+
√
n
In th
e
basic QS algorithm the values
x
2
−
n
, where
x
=
t
is an
in
teger close
to
√
n
, are searched for
B
-smooth values. But as
x
goes away from
√
n
, the size of
x
2
n
increases making it less likely to be
B
-smooth. This makes the size of the sieve
interval
−
grow very fast, which has a considerable impact on performance.
A nice solution to this problem was proposed, independently, by Davis, Holdridge,
andMontgomery, and it consi
st
s of using a family of polynomials instead of the single
polynomial
Q
[−
M
,
M
]
+
√
n
2
(
)
=
(
)
−
n
. Using multiple polynomials leads to much
shorter sieve intervals and the number of relations found per sieved value is much
higher; the resulting algorithm is known as the
multiple polynomial quadratic sieve
(MPQS). We refer to [60] for the details on MPQS and the Montgomery method, as
well as for the so-called
self initialization
, which is a clever method to minimize the
amount of work done when generating the multiple polynomials used by MPQS and
finding their zeros, and gives rise to the
self-initializing quadratic sieve
algorithm
(SIQS, for short). The time savings provided by MPQS and SIQS with respect to the
basicQS are important in practice and a “thought experiment” presented in [60, 6.1.5]
suggests that MPQS should run about 17 times as fast as the basic QS method when
n
is a 100-digit number. Apart from being more efficient, MPQS and SIQS have
another important advantage over basic QS: the use of multiple polynomials makes
them easily parallelizable.
The previous implementation of QS can be modified without too much difficulty
to become an implementation of SIQS with the large prime variation, able to fac-
tor integers of more than 70 decimal digits, but it cannot go much further beyond
that size because then the linear algebra step as implemented here requires a lot of
memory.
7
Making these modifications could be a fine—and challenging—exercise
for the reader wishing to a
cquire a deeper understanding of the method.
t
t
7
To overcome this difficulty a more efficient encoding of the binary matrix—such as storing eight
entries per byte—should be used or, better still, sparse encoding in the form of a listing where
the positions of the 1s appear, since most of the coefficients are 0. This also requires the use of a
sparse-matrix method to compute the null space.
