Cryptography Reference
In-Depth Information
The multiplication algorithm thus consists entirely of an outer loop for
calculating the partial products
a
i
(
b
n
−
1
b
n
−
2
...b
0
)
B
and an inner loop for
calculating the inner products
a
i
b
j
,
j
=0
,...,n
−
1
, and the values
t
and
p
i
+
j
.
The algorithm then appears as follows.
Algorithm for multiplication
1.
Set
p
i
←
0
for
i
=0
,...,n−
1
.
2.
Set
i ←
0
.
3.
Set
j ←
0
and
c ←
0
.
4.
Set
t ← p
i
+
j
+
a
i
b
j
+
c
,
p
i
+
j
← t
mod
B
,and
c ←t/B
.
5.
Set
j ← j
+1
;if
j ≤ n −
1
, go to step 4.
6.
Set
p
i
+
n
← c
.
7.
Set
i ← i
+1
;if
i ≤ m −
1
, go to step 3.
8.
Output
p
=(
p
m
+
n
−
1
p
m
+
n
−
2
...p
0
)
B
.
The following implementation of multiplication contains at its core this main
loop. Corresponding to the above estimate, in step 4 the lossless representation
of a value less than
B
2
in the variable
t
is required. Analogously to how we
proceeded in the case of addition, the inner products
t
are thus represented as
ULONG
types. The variable
t
is nonetheless not used explicitly, and the setting of
the result digits
p
i
+
j
and the carry
c
occurs rather within a single expression,
analogous to the process already mentioned in connection with the addition
function (see page 25). For initialization a more efficient procedure will be chosen
than the one shown in step 1 of the algorithm.
Function:
multiplication
int mul_l (CLINT f1_l, CLINT f2_l, CLINT pp_l);
Syntax:
f1_l, f2_l
(factors)
Input:
pp_l
(product)
Output:
E_CLINT_OK
if all is ok
E_CLINT_OFL
if overflow
Return:
