Cryptography Reference
In-Depth Information
used. For this and other related issues see, e.g., the discussion following Algorithm
6.1.1 in [60], where the authors say:
“The optimal B-value is more of an art than
a science, and is perhaps best left to experimentation”
. We also remark that, from
version 12 onwards, Maple has an excellent implementation of the quadratic sieve
(the multiple polynomial version that we will mention later) which constitutes the
core of the
ifactor
function and is used to factor the most difficult numbers.
Maple's implementation is very fast, among other things because the most critical
parts are written in C, but this makes it difficult to learn much by looking at the Maple
code. A description of this implementation can be found in [40].
In the implementation that follows we will use several of the functions previ-
ously defined for the factor base method, namely,
FactorBase
,
g
,
MultSelect
,
FBTrialDivision
,
Dependencies
and
FindFactors
. So we start with a
function called
Initialization
, which has three required input parameters:
n
(for the number being factored),
c
and
cutoff
. The values assigned to these pa-
rameters will be furnished by the main function of the algorithm,
QS
, to be defined
later, where there will be two optional parameters corresponding to the last two para-
meters of
Initialization
.
c
is used when computing the smoothness bound
B
,
which has the form
c
2
, where the value assigned to the constant
c
can be set
through the parameter
c
. The value assigned to
cutoff
is used to determine which
small primes in the factor base will not be used for sieving, namely, those that are
less than or equal to the value of
cutoff
, plus the prime divisors of the multiplier
independently of their size. The output of this function is a list of the following 11
values:
1
/
·
L
(
n
)
1.
m
: The multiplier.
2.
mn
: The product of the multiplier by the integer
n
being factored.
3.
B
: The smoothness
bou
nd
B
.
4.
b
:Thevalueof
√
mn
.
5.
M
: Half the size of the sieving interval
.
6.
fb
: The factor base given as a one-dimensional array.
7.
sievingprimes
: The array containing the primes used for sieving.
8.
svplogs
: An array with the integer approximations of the binary logarithms
of the sieving primes.
9.
nsvp
: The number of sieving primes.
10.
polroots
: A 2-dimensional array containing the roots of the polynomial
Q
[−
M
,
M
]
2
mn
modulo the sieving primes.
11.
sievearray
: A one-dime
nsio
nal array of length 2
M
(
t
)
=
(
t
+
b
)
−
+
1 filled with an integer
M
√
mn
approximation of log
2
(
)
minus the expected contribution of the small
primes not used for sieving.
The multiplier, the smoothness bound and the factor base are computed in a way
similar to that used for the factor base method. The value of
M
, which determines
the length of the sieving interval, is chosen somewhat lower than suggested by our
previous discussion in order to allow the algorithm to deal with larger numbers
without hitting memory limits. The roots of the polynomials are computed with
