Cryptography Reference
In-Depth Information
15
Factoring and discrete logarithms
in subexponential time
One of the most powerful tools in mathematics is linear algebra, and much of mathematics
is devoted to solving problems by reducing them to it. It is therefore natural to try to solve
the integer factorisation and discrete logarithm problems (DLP) in this way. This chapter
briefly describes a class of algorithms that exploit a notion called “smoothness”, to reduce
factoring or DLP to linear algebra. We present such algorithms for integer factorisation, the
DLP in the multiplicative group of a finite field and the DLP in the divisor class group of a
curve.
It is beyond the scope of this topic to give all the details of these algorithms. Instead,
the aim is to sketch the basic ideas. We mainly present algorithms with nice theoretical
properties (though often still requiring heuristic assumptions) rather than the algorithms
with the best practical performance. We refer to Crandall and Pomerance [
150
], Shoup [
497
]
and Joux [
283
] for further reading.
The chapter is arranged as follows. First, we present results on smooth integers, and
then sketch Dixon's random squares factoring algorithm. Section
15.2.3
then summarises
the important features of all algorithms of this type. We then briefly describe a number of
algorithms for the discrete logarithm problem in various groups.
15.1 Smooth integers
Recall from Definition
12.3.1
that an integer is
B
-smooth if all its prime divisors are at
most
B
. We briefly recall some results on smooth integers; see Granville [
243
] for a survey
of this subject and for further references.
Definition 15.1.1
Let
X,Y
∈ N
be such that 2
≤
Y<X
. Define
(
X,Y
)
=
#
{
n
∈ N
:1
≤
n
≤
X, n
is
Y
-smooth
}
.
It is important for this chapter to have good bounds on
(
X,Y
). Let
u
=
log(
X
)
/
log(
Y
)
X
1
/u
and
X
Y
u
. There is a
(as usual log denotes the natural logarithm) so that
u>
1,
Y
=
=
function
ρ
:
R
>
0
→ R
>
0
called the
Dickman-de Bruijn function
(for the exact definition
of this function see Section 1.4.5 of [
150
]) such that, for fixed
u>
1,
(
X,X
1
/u
)
∼
Xρ
(
u
),
