Cryptography Reference
In-Depth Information
≥
(
(
−
+
))
(
)
to be divided by an
l
-bit integer with
k
l
is
O
l
k
l
1
which is also
O
kl
>
but may be significantly less than the latter. Thus, if
a
b
, dividing
a
by
b
with
quotient
q
and remainder
r
requires time
O
.
We are now ready to introduce the important notion of
polynomial time
(or poly-
time as it is sometimes called for brevity).
(
len
(
b
)
len
(
q
))
: N → R
+
Definition 2.9
A function
f
is called polynomial (or polynomially
x
c
bounded) if
f
for some positive integer
c
. An algorithm is said to
be a
polynomial
-
time algorithm
if its running time is a polynomial function of the
input size.
(
x
)
=
O
(
)
Since we will be mainly interested in algorithms that accept integers as input we
remark that, for these algorithms, the previous definition may be reformulated as
follows:
Definition 2.10
An algorithm that accepts as input integers
n
1
,...,
n
t
(given in
positional notation) is said to
run in polynomial time
if there are non-negative integers
c
1
,...,
c
t
such that the running time of the algorithm is
c
1
len
c
2
c
t
ln
c
1
n
1
ln
c
2
n
2
···
ln
c
t
O
(
len
(
n
1
)
(
n
2
)
···
len
(
n
t
)
)
=
O
(
n
t
).
c
In particular, if the input is a unique integer
n
, the running time is
O
(
len
(
n
)
)
=
ln
c
n
(where ln
c
n
is an abbreviated notation for
c
).
O
(
)
(
ln
n
)
We will sometimes use the notation polylog
(
n
)
to denote a generic polynomial
ln
c
n
functioninln
n
, so that
O
for some constant
c
.
Note that the definition of polynomial time just means that the running time is
O
(
polylog
(
n
))
just means
O
(
)
, where
f
is a polynomial function.
We see that the algorithms corresponding to the basic arithmetic operations all
run in polynomial time. Let us give an example of an algorithm that does not.
(
f
(
len
(
n
)))
n
2
ln
2
n
Example 2.2
The usual algorithmfor computing
n
!
runs on time
O
(
)
. Indeed,
we do
n
−
2 multiplications in which one of the factors is bounded by
n
!
and the
other one bounded by
n
. The length of
n
(which is the product of fewer than
n
numbers each of which is less than or equal to
n
)is
O
!
(
n
ln
n
)
so each of these
n
−
2
n
ln
2
n
multiplications requires
O
(
)
bit operations. Thus the total time for computing
n
ln
2
n
n
2
ln
2
n
n
. Notice that this algorithm is not a polynomial-
time algorithm. If we express the running time as a function of the logarithm of
n
,
we see that this time is
O
!
is
O
(
n
)
·
O
(
)
=
O
(
)
e
2ln
n
ln
2
n
(
)
.
Definition 2.11
An algorithm that accepts an integer
n
as input runs in
exponential
time
if its running time is
O
0.
1
More
generally, we can say that an algorithm runs in exponential time when it has a time
n
c
e
c
ln
n
(
)
=
O
(
)
for some constant
c
>
1
Thus the algorithm used to compute
n
ln
2
n
n
ε
)
!
is indeed exponential because
O
(
)
=
O
(
and so
n
2
ln
2
n
n
2
+
ε
)
the running time of the algorithm is
O
(
)
=
O
(
.
