Cryptography Reference
In-Depth Information
that
x
t
n
is of order of magnitude
n
1
/
2
+
ε
where
−
ε>
0 is small, we can revise
the previous heuristic estimate replacing
n
by
n
1
/
2
in the value of
u
, leading to
u
2ln
B
.
If
K
is the size of the factor base, then we have to find about
K
relations and,
heuristically,
n
will be a quadratic residue modulo about half of the primes
≈
ln
n
/
≤
B
,
so that by the Prime Number Theorem
K
2ln
B
. On the other
hand, the complexity of the sieve is similar to that of the Eratosthenes sieve, namely,
ln ln
B
per sieved value. This leads to the following estimate of the amount of work
for the sieving stage of the algorithm: we expect to try
u
u
values to get one
B
-
smooth value and we require about
K
smooth values, so the total sieving work will
be
W
≈
π(
B
)/
2
≈
B
/
Ku
u
Bu
u
(
B
)
≈
(
ln ln
B
)
≈
(
ln ln
B
)/
2ln
B
. This expression is dominated by
the factor
Bu
u
which is much larger than
2ln
B
so we will try to find the
value of
B
(as
a function of
n
) that minimizes the term
Bu
u
. Defining, as before,
L
(
ln ln
B
)/
(
√
(
a
,weex-
(
x
)
=
exp
ln
x
)(
ln ln
x
))
and
a
=
ln
B
/
ln
L
(
n
)
, so that
B
=
L
(
n
)
a
√
(
press
Bu
u
as a function of
n
and
a
. Since ln
B
=
a
ln
L
(
n
)
=
ln
n
)(
ln ln
n
)
we have:
ln
n
ln ln
n
.
ln
n
2ln
B
=
ln
n
1
2
a
=
2
a
√
(
)
=
u
ln
n
)(
ln ln
n
1
1
Then, taking logarithms we obtain ln
u
=
2
(
ln ln
n
)
−
2
(
ln ln ln
n
)
−
ln 2
a
≈
ln
n
ln ln
n
1
1
2
a
2
(
ln ln
n
)
since the other terms are much smaller; hence
u
ln
u
≈
·
1
1
4
a
. Therefore,
u
u
e
u
ln
u
1
/
4
a
and hence
Bu
u
2
(
ln ln
n
)
=
ln
L
(
n
)
=
=
L
(
n
)
≈
1
4
a
. Thus we have to minimize the exponent
a
a
1
/
4
a
a
+
1
L
(
n
)
·
L
(
n
)
=
L
(
n
)
+
4
a
and
by the standard calculus procedure we see that in the interval
(
0
,
1
)
the minimum
2
.
From this we conclude that we should choose the smoothness bound
B
equal
to about
L
1
1
/
value occurs at
a
=
2
, which corresponds to
B
=
L
(
n
)
1
/
2
and that, since in this case we also have
u
u
1
/
2
,the
(
n
)
≈
L
(
n
)
amount of work for the sieving is
W
(
B
)
≈
L
(
n
)
. This leads to a running time es-
ln
c
n
e
c
ln ln
n
timate of
O
(
L
(
n
)
·
polylog
(
n
))
which, sin
ce po
lylog
(
n
)
=
O
(
)
=
O
(
)
c
ln ln
n
ln
n
, where
c
ln ln
n
ln
n
for a constant
c
, and
e
c
ln ln
n
=
L
(
n
)
=
o
(
1
)
(so that
o
(
)
), gives that the complexity of the sieving step of the al-
1
polylog
(
n
)
=
L
(
n
)
1
+
o
(
1
)
. On the other hand, this also gives an estimate for the size of
gorithm is
L
(
n
)
to be sieved. It should contain about
Ku
u
values which, with
the interval
[−
M
,
M
]
u
u
1
/
2
and
K
2ln
B
gives
Ku
u
B
≈
≈
L
(
n
)
≈
B
/
≈
L
(
n
)/
ln
L
(
n
)
. Thus we should
take
M
.
To estimate the complexity of QS we have to take into account other steps of the
algorithmwhich were not considered in the preceding argument. First of all, we have
to compute the roots of
Q
≈
L
(
n
)/
2ln
L
(
n
)
for each prime
p
in the factor base, which
can be done in time polynomial in the size of
p
(and hence in the size of
n
)using
Algorithm 2.8. Since there are fewer than
B
(
t
)
≡
0
(
mod
p
)
2
primes in the factor base and
the complexity of Algorithm 2.8 is, as seen above,
L
1
/
≈
(
)
L
n
o
(
1
)
, this computation has
(
)
n
1
/
2
+
o
(
1
)
, a term swallowed by the complexity of the sieving step,
complexity
L
(
n
)
