Cryptography Reference
In-Depth Information
We shall avoid the notation
a
for a residue class by simply omitting the bar and
letting the representative
a
denote the class of
a
, provided that there is no chance
of confusion.
The process by which the functions for modular arithmetic operate consists
essentially in carrying out the corresponding nonmodular function on the
operands and then using division with remainder to carry out a modular
reduction. However, one must note that intermediate results can grow to a size
of
2MAX
B
digits, which due to their size or, in the case of subtraction, on
account of a negative sign, cannot be represented in a
CLINT
object. We have
previously called these situations respectively overflow and underflow. The basic
arithmetic functions possess mechanisms for dealing with situations of overflow
and underflow that reduce these intermediate results modulo
(
N
max
+1)
(see
Chapters 3 and 4). These would be effective here if the result of the complete
modular operation were representable by a
CLINT
type. In order to obtain correct
results in these cases, we shall extract from the functions that we already have for
the basic operations, as announced in Chapter 4, kernel functions
void add (CLINT, CLINT, CLINT);
void sub (CLINT, CLINT, CLINT);
void mult (CLINT, CLINT, CLINT);
void umul (CLINT, USHORT, CLINT);
void sqr (CLINT, CLINT);
The kernel functions comprise the arithmetic operations that have been
removed from the functions
add_l()
,
sub_l()
,
mul_l()
, and
sqr_l()
, which we
have met earlier. What remains in these functions are simply the processes of
removing leading zeros, supporting the accumulator operation, and handling
possible overflow or underflow, while for the actual arithmetic operations the
kernel functions are invoked. The syntax and semantics of these earlier functions
are not altered, and the functions can be used as described.
As an example of multiplication
mul_l()
, this process leads to the following
function (see in this regard the implementation of the function
mul_l()
on
page 36).
Function:
multiplication
int mul_l (CLINT f1_l, CLINT f2_l, CLINT pp_l);
Syntax:
f1_l, f2_l
(factors)
Input:
Output:
pp_l
(product)
E_CLINT_OK
if all is ok
E_CLINT_OFL
if overflow
Return:
