Cryptography Reference
In-Depth Information
The large drop in performance of the Karatsuba functions for smaller
numbers that was remarked on in the first edition of this topic has in the
meantime been eliminated. Yet there is still potential for improvement. The
observable discontinuity in the calculation times of
kmul_l()
indicates that the
recursion breaks off earlier than specified by the threshold value if the factors of a
recursion step do not have an even number of digits. In the worst case this occurs
right at the beginning of the multiplication, and even for very large numbers we
are no better off than we were in the standard case. It would seem worthwhile,
then, to extend the Karatsuba functions to be able to process arguments with
differing numbers of digits and odd numbers of digits.
At the Max Planck Institute in Saarbrücken, J. Ziegler [Zieg] developed a
portable implementation of Karatsuba multiplication and squaring for a 64-bit
CPU (Sun Ultra-1) that overtakes the conventional method at 640 binary digits.
With squaring an improvement in performance of 10% occurred at 1024 binary
digits and 23% at 2048 binary digits.
C. Burnikel and J. Ziegler [BuZi] have developed an interesting recursive
division procedure based on Karatsuba multiplication that from about 250
decimal digits on is increasingly faster than the school method.
Once again, however, the Karatsuba functions have no particular advantage
for our cryptographic applications without considerable optimization, for which
reason we shall prefer to fall back on the functions
mul_l()
and
sqr_l()
, which
realize the conventional procedures (and their variants in assembly language
optimized by hand; see Chapter 19). For applications for which the Karatsuba
functions seem suited one could simply substitute those functions for
mul_l()
and
sqr_l()
.
4.3 Division with Remainder
And marriage and death and division
Make barren our lives.
—Algernon Charles Swinburne, “Dolores”
We still need to place the last stone in our edifice of the fundamental arithmetic
processes on large numbers, namely, division, which is the most complex of them
all. Since we are calculating with natural numbers, we have only natural numbers
at our disposal to express the results of a division. The principle of division that
we are about to expound will be called
division with remainder
. It is based on the
following relation. Given
a, b ∈
Z
,
b>
0
, there are unique integers
q
and
r
that
satisfy
a
=
qb
+
r
with
0
≤
r<b
.Wecall
q
the
quotient
and
r
the
remainder
of
the division of
a
by
b
.
