Cryptography Reference
In-Depth Information
with four multiplications to base
B
k
and thus
n
2
=4
k
2
elementary
multiplications to base
B
. However, if we set
c
0
:=
a
0
b
0
,
c
1:=
a
1
b
1
,
c
2:=(
a
0
+
a
1
)(
b
0
+
b
1
)
− c
0
− c
1
,
then we have
ab
=
B
k
B
k
c
1
+
c
2
+
c
0
.
For calculating
ab
it now appears that only three more multiplications
by numbers to base
B
k
,or
3
k
2
multiplications to base
B
, are necessary, in
addition to some additions and shifting operations (multiplication by
B
k
can be
accomplished by left shifting by
k
digits to base
B
; see Section 7.1). Let us assume
that the number of digits
n
of our factors
a
and
b
is a power of
2
, with the result
that by recursive application of the procedure on the remaining partial products
we can end with having to carry out only elementary multiplications to base
B
,
and this yields a total of
3
log
2
n
=
n
log
2
3
≈ n
1
.
585
elementary multiplications,
as opposed to
n
2
in the classical procedure, in addition to the time for additions
and shift operations.
For squaring, this process can be simplified somewhat: With
c
0
:=
a
0
,
c
1
:=
a
1
,
c
2
:= (
a
0
+
a
1
)
2
−
c
0
−
c
1
,
we have
a
2
=
B
k
B
k
c
1
+
c
2
+
c
0
.
Furthermore, to our advantage, the factors in the squaring always have the
same number of digits, which is not generally the case in multiplication. With all
these advantages, we should, however, mention that recursion within a program
function always costs something, so that we may hope to experience a savings
in time over the classical method, which manages without the added burden of
recursion, only when the numbers get large.
To obtain information on the actual time performance of the Karatsuba
procedure the functions
kmul()
and
ksqr()
are provided. The division of the
factors into two halves takes place in situ, and so a copying of the halves is
unnecessary. But it is necessary that the functions be passed pointers to the
least-significant digits of the factors and that the numbers of digits be passed
separately.
The functions presented below in experimental form use the recursive
procedure for factors having more than a certain number of digits determined
by a macro, while for smaller factors we turn to conventional multiplication or
