Cryptography Reference
In-Depth Information
e
ck
(
)
estimate of the form
O
, where
k
is the total binary length of the integers to
which the algorithm is being applied [119].
Polynomial-time algorithms are considered efficient and computational problems
that may be solved by these algorithms are considered “feasible” or even “easy”. Of
course, a specific polynomial-time algorithm might have a very large exponent and
hence not be very efficient, but, in general, almost all polynomial-time algorithms that
arise naturally have a low exponent and are really efficient. In addition, computational
problems for which no polynomial-time algorithms are known are considered hard,
and they are usually hard in practice. Thus the concept of polynomial time seems to
capture the algorithms that are efficient in practice and both concepts are regarded
as synonymous, as we will do in this topic.
Besides the problems for which only exponential-time algorithms are known,
there are other intermediate problems which are easier than exponential but harder
than polynomial time and, in fact, some of the most important “hard problems” used
in cryptography are of this type. In order to deal with algorithms whose complexity is
intermediate between polynomial and exponential, the so-called
L
-notation is often
used. Let
n
be a large positive integer that can be thought of as the input of an
algorithm,
0 a constant. We define:
Definition 2.12
The
subexponential function
with parameters
γ
a real number in the interval
[
0
,
1
]
, and
c
>
α
∈[
0
,
1
]
and
c
>
0is
e
c
(
ln
n
)
α
(
ln ln
n
)
1
−
α
L
n
[
α,
c
]=
.
e
√
(
ln
n
)(
ln ln
n
)
.
We will, in particular, write
L
(
n
)
=
L
n
[
1
/
2
,
1
]=
We see that, in particular:
e
c
(
ln ln
n
)
=
(
c
,
•
L
n
[
,
]=
)
0
c
ln
n
n
c
.
Thus an algorithm whose running time is
O
e
c
(
ln
n
)
=
•
L
n
[
,
]=
1
c
(
L
n
[
0
,
c
]
)
is a polynomial-time algo-
rithm while an algorithm with running time
O
(
L
n
[
1
,
c
]
)
is exponential. This leads
to the following definition:
Definition 2.13
An algorithmwhich takes as input a positive integer
n
runs in
subex-
ponential time
if its running time is
O
(
L
n
[
α,
c
]
)
for some 0
<α<
1.
Thus a subexponential algorithm is one whose running time is somewhat interme-
diate between polynomial and exponential or, more precisely, it is both
c
Ω((
ln
n
)
)
∈ R
+
(and hence faster than exponential). We will see that the most efficient algorithms
known for certain hard problems on which several public-key cryptographic schemes
are based run in subexponential time
2
O
∈ R
+
(and hence slower than polynomial) and
O
n
c
for every
c
(
)
, for every
c
1
/
3
.
We have mentioned that computational complexity theory tries to classify com-
putational problems and the algorithms used to solve them but we have not given a
(
L
n
[
1
/
3
,(
64
/
9
)
+
o
(
1
)
]
)
2
This estimate is
heuristic
in the sense that it relies on some widely believed but unproven conjec-
tures and it agrees well with the results obtained in practice.
