Cryptography Reference
In-Depth Information
m i = 0 e i 2 i mod n
= i = 0 (
= 0 i k , e i = 1 m 2 i mod n .
m 2 i
m e mod n
e i mod n
=
)
This suggests the following algorithm:
Algorithm 2.4. Modular exponentiation algorithm .
Input : n
2, m ∈ Z n ,and e
0.
Output : m e mod n .
= i = 0 e i 2 i .
1. Compute the binary expansion of e , e
= (
e k e k 1
...
e 1 e 0
)
2
2. Compute the powers m 2 i mod n for 0
i
k by successive squarings (note that
m 2 i + 1
m 2 i
2 ).
3. Compute m e mod n as the product of those m 2 i mod n for which the corresponding
bit is e i = 1.
4. return m e mod n .
= (
)
As we are going to see, this algorithm is implemented in Maple and allows the
computation of extremely large exponentiations with great efficiency. But, before
discussing Maple's built-in function for this purpose, we are going to exhibit a
straightforward implementation that makes it easy to understand the simplicity and
elegance of the algorithm. The algorithm can be rendered in Maple as follows:
> ModExp := proc(m::nonnegint, e::nonnegint, n::posint)
local z, y, t;
ifm=0ande=0then
error "0ˆ0 is undefined"
end if;
z:=m;
y:=1;
t:=e;
while 0<tdo
if irem(t, 2, 't') = 1 then
y := irem(y*z, n)
end if;
z := irem(z*z, n)
end do;
y
end proc:
In this function the operations described in Algorithm 2.4 are carried out in a
slightly different order. In the while loop, the binary expansion of e is being computed
by means of successive divisions by 2 and, after computing each bit, a multiplication
by m followed by a squaring is done if the corresponding bit is 1, while if the bit
is 0 only the squaring is performed; note that in this process the bits of e are being
scanned in the same order as they are generated, i.e., from the least significant to
the most significant one or, in other words, from 'right to left'. It is then clear that,
discounting the initial iteration of the loop which is trivial as at most it only requires
multiplying by 1 and squaring 1, if e has k
1 of these bits
are equal to 1, then the total number of modular operations (either multiplications or
squarings) performed is k
+
1 bits and exactly r
+
r integer multiplications
of numbers less than n and the same number of divisions to reduce modulo n .To
estimate the complexity of this algorithm note that the number of iterations of the
+
r . This amounts to a total of k
+
 
 
Search WWH ::




Custom Search