Cryptography Reference
In-Depth Information
Integers are represented as a sequence of binary words. Operations like add or multiply
may correspond to many bit or word operations. The
length
of an unsigned integer
a
represented in binary is
+
=
log
2
(
a
)
1if
a
0
len(
a
)
=
1
if
a
=
0
.
For a signed integer we define len(
a
)
1.
The complexity of algorithms manipulating integers depends on the length of the inte-
gers; hence, one should express the complexity in terms of the function len. However, it is
traditional to just use log
2
or the natural logarithm log.
=
len(
|
a
|
)
+
∈ N
=
=
Exercise 2.2.1
Show that, for
a
,len(
a
)
O
(log(
a
)) and log(
a
)
O
(len(
a
)).
Lemma 2.2.2
Let a,b
∈ Z
be represented as a sequence of binary words.
1. It requires O
(log(
a
))
bit operations to write a out in binary.
2. One can compute a
)
bit operations.
3. One can compute ab in O
(log(
a
) log(
b
))
bit operations.
4. Suppose
±
b in O
(max
{
log(
a
)
,
log(
b
)
}
|
a
|
>
|
b
|
. One can compute q and r such that a
=
bq
+
r and
0
≤
r<
|
b
|
in
O
(log(
b
)log(
q
))
=
O
(log(
b
)(log(
a
)
−
log(
b
)
+
1))
bit operations.
Proof
Only the final statement is non-trivial. The school method of long division computes
q
and
r
simultaneously and requires
O
(log(
q
)log(
a
)) bit operations. It is more efficient
to compute
q
first by considering only the most significant log
2
(
q
) bits of
a
, and then to
compute
r
as
a
bq
. For more details see Section 4.3.1 of [
308
], Section 2.4 of [
220
]or
Section 3.3.4 of [
497
].
−
2.2.1 Faster integer multiplication
An important discovery is that it is possible to multiply integers more quickly than the
“school method”. General references for this subject include Section 9.5 of [
150
], Section
4.3.3 of [
308
], Section 3.5 of [
497
] and Section 1.3 of [
95
].
Karatsuba multiplication
is based on the observation that one can compute (
a
0
+
2
n
a
1
)(
b
0
+
2
n
b
1
), where
a
0
,a
1
,b
0
and
b
1
are
n
-bit integers, in three multiplications of
n
-bit integers rather than four.
Exercise 2.2.3
Prove that the complexity of Karatsuba multiplication of
n
bit integers is
O
(
n
log
2
(3)
)
O
(
n
1
.
585
) bit operations.
[Hint: Assume
n
is a power of 2.]
=
Toom-Cook multiplication
is a generalisation of Karatsuba. Fix a value
k
and suppose
a
k
2
kn
and similarly for
b
. One can think of
a
and
b
as being
polynomials in
x
of degree
k
evaluated at 2
n
and we want to compute the product
c
a
1
2
n
a
2
2
2
n
a
=
a
0
+
+
+···
=
ab
,
