Cryptography Reference
In-Depth Information
squaring. For the case of nonrecursive multiplication the functions
kmul()
and
ksqr()
use the auxiliary functions
mult()
and
sqr()
, in which multiplication and
squaring are implemented as
kernel functions
without the support of identical
argument addresses (accumulator mode) or reduction in the case of overflow.
Karatsuba multiplication of two numbers
a_l
and
b_l
with
2
k
digits each to base
B
Function:
void kmul (clint *aptr_l, clint *bptr_l,
int len_a, int len_b, CLINT p_l);
Syntax:
aptr_l
( pointer to the least-significant digit of the factor
a_l
)
bptr_l
(pointer to the least-significant digit of the factor
b_l
)
len_a
(number of digits of
a_l
)
len_b
(number of digits of
b_l
)
Input:
p_l
(product)
Output:
void
kmul (clint *aptr_l, clint *bptr_l, int len_a, int len_b, CLINT p_l)
{
CLINT c01_l, c10_l;
clint c0_l[CLINTMAXSHORT + 2];
clint c1_l[CLINTMAXSHORT + 2];
clint c2_l[CLINTMAXSHORT + 2];
CLINTD tmp_l;
clint *a1ptr_l, *b1ptr_l;
int l2;
if ((len_a == len_b) && (len_a >= MUL_THRESHOLD)
&& (0 == (len_a & 1)) )
{
If both factors possess the same even number of digits above the value
MUL_THRESHOLD
, then recursion is entered with the splitting of the factors into two
halves. The pointers
aptr_l
,
a1ptr_l
,
bptr_l
,
b1ptr_l
are passed to the corre-
sponding least-significant digits of one of the halves. By not copying the halves,
we save valuable time. The values
c
0
and
c
1
are calculated by recursively calling
kmul()
and then stored in the
CLINT
variables
c0_l
and
c1_l
.
