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.
 
Search WWH ::




Custom Search