Cryptography Reference
In-Depth Information
Remarks 2.1
1. The big-
O
notation denotes a binary relation between the functions
f
and
g
that
is not symmetric in general, i.e.
f
=
O
(
g
)
does not imply
g
=
O
(
f
)
or, in
oth
er
words,
f
=
O
(
g
)
does not imply
f
=
Ω(
g
)
. For example, we have that
x
√
x
x
2
(interpreting these e
x
pressions as functions in the obvious way)
but it is not true that
x
2
=
O
(
)
x
√
x
=
O
(
)
. In general, the idea of using the big-
O
,
g
should be a simpler function
than
f
that gives us a good approximation to how fast
f
grows asymptotically.
2. The functions in Definition 2.8 can be functions of several variables, i.e., defined
over subsets
X
notation is that, whenever we write
f
=
O
(
g
)
k
. Then we write, for example,
f
,
Y
⊆ N
=
O
(
g
)
if there is a
k
, with
positive constant
c
and an integer
t
such that for all
(
x
1
,...,
x
k
)
∈ N
x
i
≥
t
,1
≤
i
≤
k
, the following conditions hold:
a.
(
x
1
,...,
x
k
)
∈
X
∩
Y
, i.e., both functions are defined on
(
x
1
,...,
x
k
)
,
b.
f
(
x
1
,...,
x
k
)
≤
cg
(
x
1
,...,
x
k
)
.
Examples 2.1
1. If
f
is a polynomial of degree
d
with positive leading coefficient (see Sect.
2.8.2
for the definition of leading coefficient), then
f
x
d
x
d
.
2. If
f
and
g
are polynomials of the same degree and with the same (positive) leading
coefficient, then
f
=
O
(
)
and, in fact,
f
=
Θ(
)
g
.
3. If
f
and
g
are polynomials with positive leading coefficient and the degree of
f
is smaller than the degree of
g
, then
f
∼
=
(
)
o
g
.
(
)
4. When we write
O
g
, this expression denotes an anonymous function
f
such
that
f
=
O
(
g
)
and similarly for the other symbols in Definition 2.8. Thus
O
(
1
)
denotes a function bounded by a constant and
o
(
1
)
denotes a function that tends
to zero as
x
tends to infinity. For example,
f
(
x
)
∼
g
(
x
)
is equivalent to
f
(
x
)
=
(
1
+
o
(
1
))
g
(
x
)
.
x
ε
)
x
ε
)
5. If
ε
is a positive constant, then ln
x
=
O
(
and, in fact, ln
x
=
o
(
too. This
ln
x
is because lim
x
→∞
x
ε
=
0, i.e., the logarithmic function grows slower than any
positive power.
6. If
b
is an integer
denotes the length of the
b
-adic expansion of
x
(i.e., the number of base-
b
digits of
x
), then
f
≥
2 and
f
(
x
)
(
x
)
=
O
(
ln
x
)
. This is because,
ln
x
ln
b
by Theorem 2.3,
f
1. This can be
interpreted as: “the number of digits grows like the logarithm” (and the logarithm
base does not matter because logarithms to different bases are proportional). In
fact, it is clear that we also have that
f
(
x
)
=
log
b
x
+
1
≤
log
b
x
+
1
=
+
(
x
)
=
Θ(
ln
x
)
.
7. The length of an integer
n
, denoted len
(
n
)
is the number of bits of
n
and, according
to the preceding example, len
(
n
)
=
Θ(
ln
n
)
, so that len
(
n
)
and ln
n
can be
interchanged when appearing within the big-
O
notation.
8. The big-
O
notation will be used to estimate the running time of algorithms as
a function of the input size. When the input is an integer, the input size is, by
definition, len
. Thus the running times of these algorithms will be estimated
as functions of len
(
n
)
(
n
)
or, equivalently, of ln
n
.
