Cryptography Reference
In-Depth Information
All function until
n
c
are polynomial, whereas all other functions (i.e.,
n
ln
n
,
c
n
,
n
n
,and
c
c
n
) are super-polynomial.
Definition 6.4 (Polynomial-time algorithm)
An algorithm is called
polynomial-
time
if its worst-case running time function is polynomial in the input size. Any
algorithm whose running time cannot be bounded by a polynomial is called
super-
polynomial-time
.
Consequently, the worst-case running time of a polynomial-time algorithm is
of the form
O
(
n
c
),where
n
is the input size and
c
is a constant. The most important
examples of super-polynomial-time algorithms are exponential-time algorithms (i.e.,
algorithms that run in time exponential in the input size). The worst-case running
time of such an algorithm is of the form
O
(
c
n
).
In complexity theory, one considers polynomial-time algorithms (be they
deterministic or probabilistic) as being efficient and super-polynomial-time (e.g.,
exponential-time) algorithms as being inefficient. This is particularly true if the
polynomials are of small degrees (e.g.,
c
10). In practice, however, a super-
polynomial-time algorithm may be quite practical for the input size of interest, and a
polynomial-time algorithm may be completely impractical. Note, for example, that
n
1000
≤
n
ln ln ln
n
for all
n
that can ever be of relevance. Consequently, one has to
be careful when one applies complexity-theoretic arguments.
Last but not least, it is important to note that there are algorithms that
are super-polynomial-time but not exponential-time. Some of these algorithms are
subexponential-time as specified in Definition 6.5.
Definition 6.5 (Subexponential-time algorithm)
An algorithm is
subexponential-
time
if its worst-case running time function is of the form
e
o
(
n
)
,where
n
is the input
size.
A subexponential-time algorithm runs asymptotically much slower than a
polynomial-time algorithm, but it runs much faster than an exponential-time algo-
rithm. There are subexponential-time algorithms for many computational problems
that are relevant in cryptography, including, for example, integer factorization and
computing discrete logarithms. To discuss the efficiency of these algorithms, one
often uses the
running time function
L
n
[
a, c
] that is defined as follows:
L
n
[
a, c
]=
O
(
e
(
c
+
o
(1))(ln
n
)
a
(ln ln
n
)
1
−
a
)
The function has two parameters (i.e.,
a
and
c
). In general, the smaller
a
and
c
are, the more efficient the corresponding algorithms are. The parameter
a
∈
[0
,
1] is
