Cryptography Reference
In-Depth Information
experience heretofore with addition and subtraction, the classical algorithms
for multiplication and division have execution times that are quadratic in the
number of digits of the arguments, and it is not for nothing that Donald Knuth
asks in one of his chapter headings, “How fast can we multiply?”
In the literature there have been published various procedures for rapid
multiplication of large and very large integers, among which are some rather
difficult methods. An example of this is the procedure developed by A. Schönhage
and V. Strassen for multiplying large numbers by application of fast Fourier
transforms over finite fields. The running time in terms of the number of digits
n
in the arguments is bounded above by
O
(
n
log
n
log log
n
)
(see [Knut], Section
4.3.3). These techniques encompass the fastest known multiplication algorithms,
but their advantage in speed over the classical
O
n
2
methods comes into play
only when the number of binary digits is in the range 8,000-10,000. Based on the
demands of cryptographic systems, such numbers, at least for the present, are far
beyond the range envisioned in the application domain of our functions.
For our realization of multiplication for the FLINT/C package we would like
first to use as a basis the grade school method based on “Algorithm M” given
by Knuth (see [Knut], Section 4.3.1), and we shall make an effort to achieve as
efficient an implementation of this procedure as possible. Then we shall occupy
ourselves in a close examination of the calculation of squares, which offers great
potential for savings, and for both cases we shall finally look at the multiplication
procedure of Karatsuba, which is asymptotically better than
O
n
2
.
2
The
Karatsuba multiplication arouses our curiosity, since it seems simple, and one
could pleasantly occupy a (preferably rainy) Sunday afternoon trying it out. We
shall see whether this procedure has anything to contribute to the FLINT/C
library.
4.2.1 The Grade School Method
We are considering multiplication of two numbers
a
and
b
with representations
m
−
1
a
i
B
i
,
a
=(
a
m
−
1
a
m
−
2
...a
0
)
B
=
0
≤ a
i
<B,
i
=0
n
−
1
b
i
B
i
,
b
=(
b
n
−
1
b
n
−
2
...b
0
)
B
=
0
≤ b
i
<B,
i
=0
to the base
B
. According to the procedure that we learned in school, the product
ab
can be computed for
m
=
n
=3
as shown in Figure 4-1.
2
When we say that the calculation time is asymptotically better, we mean that the larger the
numbers in question, the greater the effect. One should not fall victim to premature euphoria,
and for our purposes such an improvement may have no significance whatsoever.
