Cryptography Reference
In-Depth Information
so the overall complexity of the algorithm including the computation of the roots
remains
L
)
.
The other major component of QS is the linear algebra step, where the null
space of a matrix of approximate size
K
1
+
o
(
1
(
)
n
F
2
is computed. One alterna-
tive is to use Gaussian elimination, whose complexity is
O
×
K
over
K
3
(
)
(see [60, Sect. 6.1.3]
1
/
2
for a discussion of this and references). As we have seen
K
=
O
(
L
(
n
)
)
,giv-
)
and raises the overall complexity of QS. As discussed in [60], this is not a prob-
lem in practice for numbers which are not too large but, for really large factoriza-
tions, there are other methods that perform the linear algebra step without increas-
ing the above estimate for the complexity of QS. These methods take advantage
of the fact that the matrix obtained is very sparse, which allows the use of spe-
cial encoding methods that also reduce the amount of storage required. In partic-
ular, the
block Lanczos method
and the
Wiedemann method
runintime
O
3
/
2
1
+
o
(
1
ing a complexity of
O
(
L
(
n
)
)
for this step, which is higher than
L
(
n
)
)
where
N
is the number of nonzero entries in the matrix. Clearly, this matrix has
at most
O
(
KN
(
ln
n
)
nonzero entries per row, for a total of
O
(
K
ln
n
)
nonzero entries
K
2
ln
n
. Since
K
2
and hence a running time for these methods of
O
(
)
=
O
(
L
(
n
))
K
2
1
+
o
(
1
)
we have that
O
(
·
polylog
(
n
))
=
L
(
n
)
and hence, with these meth-
)
, which is subexponential
according to Definition 2.13. We emphasize again that this is only a heuristic
estimate although, as already mentioned, the running times obtained in practice
agree.
Exercise 6.23
Show that if instead of the sieve we use trial division to find the
relations, which means that the work per
z
-value is
1
+
o
(
1
ods, the overall complexity of QS is still
L
(
n
)
(instead of
ln ln
B
) and we use the above argument, we obtain that, after minimizing
B
2
u
u
,the
optimal value of
B
is ab
o
ut
B
(
B
/
ln
B
)
·
polylog
(
n
)
2
√
2
an
d
the complexity of the Factor Base
1
/
=
(
)
L
n
√
2
√
2
+
o
(
1
)
.
algorithm is then
L
(
n
)
·
polylog
(
n
)
=
L
(
n
)
Exercise 6.24
Modify the previous implementation
o
f the factor base method so
that it uses the smoothness bound
B
2
√
2
for a suitable constant
c
,as
suggested by the previous exercise. Make an experimental study of running times
for integers of several sizes in the 2
15
1
/
=
c
·
L
(
n
)
2
30
range, in order to determine the optimal
..
value for
c
.
After the preceding discussion, we are now ready to give a schematic description
of the QS algorithm. We stress that this is a basic scheme and many improvements
are possible:
