Cryptography Reference
In-Depth Information
Beginning with the highest-valued nonzero bit in the highest-valued word of
the exponent z_l the bits of the exponent are processed, where always we have
first a squaring and then, if applicable, a multiplication. The bits of the expo-
nent are tested in the expression if((w&b)>0) by masking their value with
a bitwise AND.
b=1<<((ld_l (z_l) - 1) & (BITPERDGT - 1UL));
w = z_l[DIGITS_L (z_l)];
for(;b>0;b>>=1)
{
msqr_l (p_l, p_l, m_l);
if((w&b)>0)
{
ummul_l (p_l, bas, p_l, m_l);
}
}
Then follows the processing of the remaining digits of the exponent.
for (k = DIGITS_L (z_l) - 1;k>0;k--)
{
w = z_l[k];
for (b = BASEDIV2;b>0;b>>=1)
{
msqr_l (p_l, p_l, m_l);
if((w&b)>0)
{
ummul_l (p_l, bas, p_l, m_l);
}
}
}
cpy_l (rest_l, p_l);
return E_CLINT_OK;
}
6.2 M -ary Exponentiation
Through a generalization of the binary algorithm on page 82 the number
of modular multiplications for exponentiation can be reduced even further.
The idea is to represent the exponent in a base greater than 2 andtoreplace
multiplication by a in step 3 by multiplication by powers of a . Thus let the
 
Search WWH ::




Custom Search