Cryptography Reference
In-Depth Information
If k > 0 ,then a_l is squared k times modulo m_l .
if (k > 0)
{
cpy_l (tmp_l, a_l);
while (k-- > 0)
{
msqr_l (tmp_l, tmp_l, m_l);
}
cpy_l (p_l, tmp_l);
}
else
Otherwise, if k =0 , we need only to reduce modulo m_l .
{
mod_l (a_l, m_l, p_l);
}
return E_CLINT_OK;
}
6.3 Addition Chains and Windows
A number of algorithms for exponentiation have been published, some of which
are conceived for arbitrary operands and others for special cases. The goal is
always to find procedures that employ as few multiplications and divisions as
possible. The passage from binary to M -ary exponentiation is an example of how
the number of these operations can be reduced.
Binary and M -ary exponentiation are themselves special cases of the
construction of addition chains (cf. [Knut], Section 4.6.3). We have already
taken advantage of the fact that the laws of exponentiation allow the additive
decomposition of the exponent of a power: e = k + l
a e
= a k + l
= a k a l .
Binary exponentiation decomposes the exponent into a sum
e = e k 1 · 2 k 1 + e k 2 · 2 k 2 + ··· + e 0 ,
from which follows the exponentiation in the form of alternating squarings and
multiplications (cf. page 82):
a e mod n =
( a e k 1 ) 2 a e k 2 2
2
a e 0 mod n.
···
···
 
Search WWH ::




Custom Search