Cryptography Reference
In-Depth Information
factor base primes are used and divisions of the polynomial values by the primes
in the factor base are replaced by subtractions of these logarithms, which is a much
more efficient method for two reasons: subtraction is much faster than division and
the numbers involved are much smaller. Therefore, in order to do the sieving, a
[−
M
,
M
]
array is initialized and, for each index
t
∈[−
M
,
M
]
, the integer approx-
imation of the binary logarithm of
Q
(
t
)
is stored (in practice, the sieving interval
[−
may be divided into smaller subintervals to save storage space). Then,
during the sieve,
round
(
M
,
M
]
log
2
(
p
))
is subtracted from the array entries for the val-
ues of
t
such that
p
divides
Q
. If the sieve were an exact process then, once
sieving is finished, the smooth values would correspond to the
t
-values for which
the corresponding array entry is 0. But this is not the case because approximations
for the logarithms are used and, moreover, small primes in the factor base will
not be used for sieving since they are the most time-consuming while their loga-
rithms contribute little to the sum. Higher powers of factor base primes will not
be used for sieving either, and to compensate for all these inaccuracies a certain
threshold
T
will be set and the array scanned for values below this threshold. The
indices
t
corresponding to these values will have a high probability that
Q
(
t
)
is
B
-smooth and these will be submitted to trial division. Thus we do not get rid of
trial division completely but many fewer numbers will have to be tried. The final
part of the algorithm proceeds exactly as in the factor base method we discussed.
Because the core of this algorithm consists of sieving the values of the quadratic
polynomial
Q
(
t
)
(
t
)
, the algorithm receives the generic name of
quadratic sieve
or, for
short, QS.
6.4.7.1 The Complexity of the Quadratic Sieve
Let us now look more closely at the parameters involved in the algorithm in order to
give an idea of its complexity and also to have some guidelines for its implementation.
The starting point for this is a result of Canfield-Erdös-Pomerance according to
which, if
ψ(
x
,
y
)
denotes the number of
y
-smooth positive integers less than or
equal to
x
, and
u
=
ln
x
/
ln
y
, then
x
1
/
u
xu
−
u
(
1
+
o
(
1
))
ψ(
x
,
y
)
=
ψ(
x
,
)
=
as
u
0, see the discus-
sions in [60, pp. 48-49, 264-265] and [194, Sect. 4.4]). This suggests that the
“probability” that an integer of the form
x
2
mod
n
is
B
-smooth is about
u
−
u
,
with
u
→∞
and
u
<(
1
−
ε)
ln
x
/
ln ln
x
(for any fixed
ε>
ln
B
, but this is only a heuristic conjecture as the above men-
tioned result applies to all integers up to a certain bound and not to a special
subset. However, experience has shown that, in practice, the method works pretty
much as predicted by this conjecture. On the other hand, if we consider the
z
-
values
Q
=
ln
n
/
which we have to factor in order to obtain the
B
-smooth numbers
required to factor
n
, we see that they are of the form
x
t
(
t
)
−
n
and, when
n
is
large, much smaller than
n
and, in fact, much closer to
√
n
. Then, if we assume
