Cryptography Reference
In-Depth Information
SETDIGITS_L (quot_l, DIGITS_L (r_l) - DIGITS_L (b_l) + 1);
RMLDZRS_L (quot_l);
SETDIGITS_L (r_l, DIGITS_L (b_l));
cpy_l (rem_l, r_l);
return E_CLINT_OK;
In the case of “short division” the divisor possesses only the digit
b
0
, by which
the two digits
(
ra
i
)
B
are to be divided, where
a
i
runs through all digits of the
dividend;
r
is initialized with
r ←
0
and assumes the difference
r ←
(
ra
i
)
B
−qb
0
.
The value
r
is represented by the
USHORT
variable
rv
. The value of
(
ra
i
)
B
is stored
in the
ULONG
variable
rhat
.
shortdiv:
rv = 0;
bv = *LSDPTR_L (b_l);
for (rptr_l = MSDPTR_L (r_l), qptr_l = quot_l + DIGITS_L (r_l);
rptr_l >= LSDPTR_L (r_l); rptr_l--, qptr_l--)
{
*qptr_l = (USHORT)((rhat = ((((ULONG)rv) << BITPERDGT) + (ULONG)*rptr_l)) / bv);
rv = (USHORT)(rhat - (ULONG)bv * (ULONG)*qptr_l);
}
SETDIGITS_L (quot_l, DIGITS_L (r_l));
RMLDZRS_L (quot_l);
u2clint_l (rem_l, rv);
return E_CLINT_OK;
}
With
t
=
O
(
mn
)
, the run time
t
of the division is analogous to that for
multiplication, where
m
and
n
are the numbers of digits of the dividend and
divisor, respectively, to the base
B
.
In the sequel we shall describe a number of variants of division with
remainder, all of which are based on the general division function. First we have
the mixed version of the division of a
CLINT
type by a
USHORT
type. For this we
return once again to the routine for small divisors of the function
div_l()
, where
it is placed almost without alteration into its own function. We thus present only
the interface of the function.