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