Cryptography Reference
In-Depth Information
complexity
O
(
c
f
(
n
)
) where
c
is constant and
f
(
n
) is more than constant but less
than linear are called
superpolynomial
. It is generally accepted that modern-day
cryptanalytic techniques for breaking known ciphers are of superpolynomial-
time complexity, but nobody has been able to prove that polynomial-time algo-
rithms for cryptanalyzing ciphers do not exist.
Another notion of time is
expected running time
, which means the
expectation
(in the probability sense) of the runtimes over all the possible inputs, expressed
as a function of the input size (see Appendix E). This means that one needs to
estimate the probability that a given input occurs, not an easy task in general.
For instance, there is expected polynomial time, which we first encounter on
page 109 in reference to symmetric-key cryptosystems.
The running time of an algorithm is sometimes diGcult to determine. When
this is the case, one may be forced to settle for approximations for the running
time, called the
asymptotic running time
, which is a measure of how the running
time of the algorithm increases as the size of the input increases without bound.
In calculating complexity using the Big O notation, the following properties
are essential.
Theorem A.33
(
Properties of the Big O Notation)
Suppose that
f,g
are positive real-valued functions.
+
, then
cO
(
g
)=
O
(
g
)
.
(a)
If
c
∈
R
(b)
O
(max
{
f,g
}
)=
O
(
f
)+
O
(
g
)
.
(c)
O
(
fg
)=
O
(
f
)
O
(
g
)
.
Proof
. See [169, Theorem 1.24, page 50].
✷
To get some idea of what the various classes of complexity analysis mean
in “real-world” terms, let us look at times related to some of these classes.
Suppose that the unit of time on the computer at our disposal is a microsecond
(a millionth (1
/
10
6
) of a second). Assuming an input of
n
=10
6
bits, then
a constant algorithm (complexity
O
(1)) would take a microsecond to execute,
since the number of bit operations is one. A linear algorithm (complexity
O
(
n
))
would take a second, since the number of bit operations is 10
6
.
A quadratic
algorithm (complexity
O
(
n
2
)) would take 11
.
5741 = 10
12
/
(10
6
3600) days,
since there are 10
12
bit operations, and a cubic algorithm (complexity
O
(
n
3
))
would take 31
,
709 = 10
18
/
(10
6
·
24
·
365) years, since the number of bit
operations is 10
18
. By the time we get to exponential algorithms, we are looking
at times astronomically larger than the age of the known universe. Hence, a
problem is called
intractable
if no polynomial-time algorithm could possibly
solve it, whereas one that can be solved using a polynomial-time algorithm is
called
tractable
. (By a
problem
, we mean a general question to be answered. A
decision problem
is one whose solution is “yes” or “no.” A problem may possess
parameters
whose values are left unspecified, and an
instance
of a problem is
achieved by specifying values for those parameters.)
·
24
·
3600
·
Search WWH ::
Custom Search