Cryptography Reference
In-Depth Information
tried to factor each of them by using all the primes in the factor base. But, instead
of doing this, we may consider all the polynomial values corresponding to an in-
terval together and find which ones are divisible by a given prime in the factor
base.
Following an idea of C. Pomerance, inspired by an earlier algorithm due to
Schroeppel, this can be accomplished by means of a sieve similar to the Eratos-
thenes sieve we used to generate small primes. The reason this is possible is the fact
that the numbers where we try to find the smooth values are a sequence of values
of a polynomial and in this sequence the locations of the multiples of a prime
p
follow a regular pattern, exactly as happens in the sieve of Eratosthenes. Consider
the polynomial
Q
=
√
n
2
(
t
)
=
(
t
+
b
)
−
n
, where
b
, that we used to generate the
z
-values
z
t
=
Q
(
t
)
. Then
Q
(
a
)
≡
0
(
mod
p
)
if and only if
Q
(
a
+
sp
)
≡
0
(
mod
p
)
for every integer
s
. Thus the idea is to fix an interval
[−
M
,
M
]
and, for each prime
p
in the factor base, divide
Q
(
t
)
by the highest possible power of
p
(without try-
ingtodividethose
Q
that are not multiples of
p
) until all the
B
-smooth values
have been factored. But how do we determine the
t
(
t
)
∈[−
M
,
M
]
such that
p
divides
Q
(
t
)
? We first determine the integers
t
∈[
0
,
p
−
1
]
such that
Q
(
t
)
is divisible by
p
, and this is easy to do for we only have to solve the equation
Q
(
t
)
≡
0
(
mod
p
)
,
which we know has exactly two roots in
Z
p
if
n
is a quadratic residue modulo
p
.
These roots are quickly found by using Algorithm 2.8, and we observe that there is
only one root if we are using a multiplier
m
and
p
divides
m
(as the only square
root of 0 modulo
p
is 0 itself) but we shall explain later how to proceed with these
primes, so for now we will just assume that there is no multiplier. Once we know
the two zeros of this polynomial, say
a
,
∈ Z
p
=[
,
−
]
b
0
p
1
, the other values of
the polynomial
Q
that are divisible by
p
are found from these zeros by adding
multiples of
p
. Thus one possible way to proceed is as follows: We compute the
zeros
a
(
t
)
,
b
and, starting at them, walk through
[−
M
,
M
]
in both directions in steps
of length
p
. At each point
a
by
p
and we record the
factor
p
(or we keep a running product and multiply by
p
). We may also sieve
with higher powers of
p
or we can simply divide out the highest power of
p
at
each one of these values. After we do this with all the primes, the values that have
been completely divided out are the smooth values and we know their factorizations.
The important thing to observe is that there is no trial division in this process as
the only divisions are performed when we already know that the remainder will be
0.
+
sp
we divide
Q
(
a
+
sp
)
Now, the number of steps taken by the sieve for each
t
∈[−
M
,
M
]
is,
like in the sieve of Eratosthenes,
O
(
ln ln
B
)
(see the discussion in [60, 3.2.6])
and this is much less than the
O
(
B
/
ln
B
)
steps required for trial division—
taking into account the number of primes
B
given by the Prime Number
Theorem—per
t
-value. Thus the use of the sieve instead of trial division saves much
time.
In practice, the sieve will be done a bit differently. In order to speed it up, the
arithmetic will be done with logarithms. Exact arithmetic with logarithms involves
infinite precision but we do not aim for exactness and will be satisfied with an ap-
proximate result. For this, integer approximations for the base 2 logarithms of the
≤
