Cryptography Reference
In-Depth Information
x
ln
x
π(
)
≤
π(
)
∼
π(
)
∼
(
)
9. If
x
denotes the number of primes
x
, then
x
and
x
li
x
,
)
=
x
2
dt
where li
ln
t
is the “logarithmic integral”. This is the
Prime Number
Theorem
(PNT) which is important for cryptography and is explained in more
detail in Chap.
6
(see Theorem 6.2).
(
x
Exercise 2.3
(i) Prove that if
f
is a polynomial of degree
d
with positive leading coefficient,
then
f
x
d
=
Θ(
)
.
.
(iii) Using l'Hôpital's rule, prove that lim
x
→∞
(ii) Prove that len
(
n
)
=
Θ(
ln
n
)
ln
x
x
ε
=
0 for any positive
ε
, and hence
x
ε
)
.
(iv) Prove that if lim
x
→∞
that ln
x
=
o
(
f
(
x
)
)
=
c
where
c
is any non-negative constant, then
g
(
x
f
=
O
(
g
)
and hence that, in particular,
f
∼
g
implies
f
=
Θ(
g
)
.
2.3.2 Efficient Computation and
P
Versus
NP
Herewe give a brief overviewof complexity theory, focusing on some aspects of cryp-
tologic interest. For detailed analyses of the complexity of many number-theoretic
algorithms we refer to [180] and for a general presentation of complexity theory
to [6].
As already mentioned, we are going to use the asymptotic notation to express
estimates of the running times of some number-theoretic algorithms which have
important cryptologic applications. For this we need to count the number of “ele-
mentary operations” performed as a function of input size. The algorithms we are
going to deal with will typically accept an integer (or several integers) as input,
so the input size(s) will be the binary length(s) of the involved integer(s). We will
assume our integers are given in binary and the basic operations will be the arithmetic
operations with integers of one bit (see [118, 180] for details). This means that our
estimates will be
bit complexity
estimates.
It is not difficult to see that performing addition of two integers
n
,
m
can be done in
O
(
max
{
len
(
n
),
len
(
m
)
}
)
bit operations (where len
(
n
)
denotes, as before, the binary
length of
n
) which is the same as
O
. Indeed, this follows from the
fact that to perform the addition, we scan the binary representation of both integers
from right to left adding bit by bit with carry. The same running time estimate applies
to subtraction and, for multiplication, note that in order to multiply a
k
-bit integer
m
by an
l
-bit integer
n
by means of the usual grade-school algorithm, we have to
perform at most
l
(
max
{
ln
n
,
ln
m
}
)
−
1 additions each of which requires
k
bit operations, obtaining
the estimate
O
.
We should mention here that there are faster algorithms for multiplication,
although their advantage is only realized in practice when multiplying very large
numbers. Thus, for example, the multiplication algorithm of Schönhage and Strassen
(see, for example, [6, 180]) can multiply two
k
-bit numbers in time
O
(
kl
)
or, in terms of the logarithms,
O
(
ln
m
ln
n
)
(
)
k
ln
k
ln ln
k
k
2
k
1
+
ε
)
(
)
(
which is better than the previous estimate of
O
as it is even better than
O
for any
ε>
0. The running time of division with remainder, where a
k
-bit integer is
