Cryptography Reference
In-Depth Information
This method can be generalized and the resulting square-and-multiply algo-
rithm as captured in Algorithm 3.3 works for modular exponentiation in any (mul-
tiplicative) group. Let
G,
·
be such a group, a an element in the group, and b a
). If we want to compute a b in G , then we must have
a binary representation of the exponent b (i.e., b = b k− 1 ...b 1 b 0 ) and process this
string bitwise from one end to the other. More specifically, we process the exponent
from the most significant bit (i.e., b k− 1 ) to the least significant bit (i.e., b 0 ). The
other direction is also possible and works similarly. In Algorithm 3.3, the variable
s is used to accumulate the result. The variable is initially set to 1. The exponent is
then processed from b k− 1 to b 0 . For each exponent bit, the value of s is squared and
multiplied with a if the bit is equal to one. Finally, the algorithm returns s , and this
value represents a b in G .
positive integer (i.e., b
N
Algorithm 3.3
The square-and-multiply algorithm.
( a
G, b = b k− 1 ...b 1 b 0 N )
s ← 1
for i = k − 1 down to 0 do
s ← s · s
if b i =1then s ← s · a
return s
( a b )
Z 11 and want to
compute 7 22 (mod 11), then we must first write the exponent in binary notation
(i.e., b = (22) 10 = (10110) 2 )andset s to 1. The computation according to
Algorithm 3.3 is as follows:
Let's have a look at an example. If we consider the group
7 (1) 2
=1 2
·
7
7 (mod 11)
7 (10) 2
=7 2
5 (mod 11)
7 (101) 2
=5 2
·
7
3
·
7
10 (mod 11)
7 (1011) 2
(10) 2
=
·
7
7 (mod 11)
7 (10110) 2
=7 2
5 (mod 11)
In the first iteration, s is squared and multiplied with 7 modulo 11. The result
is 7. In the second iteration, this value is squared modulo 11. The result is 5. In the
third iteration, this value is squared and multiplied with 7 modulo 11. The result is
10 (or
1). In the fourth iteration, this value is squared and multiplied with 7 modulo
Search WWH ::




Custom Search