Page 273 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Normal Bases 253

Algorithm 8.6—m-ary method for exponentiation
Input: A, e
Output: B = A e
2
3
1. Compute A , A ,..., A m-1 .
2. B := 1
3. for d = l downto 0 by –1 do
4. B := B m
r
5. B := BA d
6. end for
7. return B
This method is particularly attractive if m = 2 , so that raising a to the mth
k
power only involves k squarings ([Sti90], [Gat91]). Therefore, if the field
GF(2 ) is used with a normal basis, then the squarings can be done with
m
k
just a cyclic shift. In this case, the 2 -ary method takes only ⎡m/k⎤ + 2 k − 1 – 2
multiplications, since only odd powers up to 2 – 1 need to be computed.
k
k
The 2 -ary method is given in the following algorithm [Gor98]:
k
Algorithm 8.7—2 -ary method for exponentiation
Input: A, e
Output: B = A e
k
5
3
1. Compute A ,A ,...,A 2 -1 .
2. B := 1
3. for d = 2 – 1 downto 1 by –2 do
k
j
4. for each i such that r= d2 i do
i
⋅
d2 ki+j i
5. B := B(A )
6. end for
7. end for
8. return B
We can illustrate the 2 -ary method with the following example:
k
r
Example 8.4 Assume that we want to compute the value of A = A 3370 .
The binary representation of the power r = 3370 is r = 110100101010.
Let k = 3, therefore the binary representation of r must be considered
in groups of 3 bits each, in such a way that
32
r
30
r = 110 100 101 010 = r 2 () + r 2() + r 2() + r 2()
33
31

3
1
0
2
r 3 r 2 r 1 r 0
= 62() + 42() + 52 ) + 2 2 3 0 3370 (8.36)
( ) =
33
3 1
32
(
)
10
The values of the r s are in the range r ∈ [0,1,2, . . . ,7]. From Algo-
i
7
3
5
rithm 8.7, only the terms A , A , and A should be computed. The execu-
tion of Algorithm 8.7 will give the following intermediate results:
• d = 7 ⇒ There is not any r in the form r = d2 .
j
i
i i
52
52
0
• d = 5 ⇒ r = 5 = 5⋅2 ⇒ B = 1( A ) 31 ⋅+0 = ( A ) 3
1
3
3
3
52
32
52
32
• d = 3 ⇒ r = 6 = 3⋅2 ⇒ B = (( A ) )( A ) 3 ⋅+1 = (( A ) )( A ) 10
1
3