Page 270 - Hardware Implementation of Finite-Field Arithmetic

250 Cha pte r Ei g h t

also known as the square-and-multiply method, which breaks the expo-
nentiation operation into a series of squaring and multiplication opera-
m
tions in GF(2 ). The binary method [Knu81] has been already dealt with
in Chaps. 5 and 7. In this method, repeated squaring of the partial results
is used to reduce the required number of multiplications. Each integer
exponent e can be presented in its binary representation as an m-bit
2
vector as e = e + e 2 + e 2 + . . . + e 2 m − 1 = (e , e , . . . , e ). According to
0 1 2 m − 1 0 1 m − 1
this method, we can obtain:
− 1
m
−
2
b = a = a ∑ m − 1 e i 2 i = a 0 () ( a ) ... a ( 2 m − 1 e m − 1 = ∏ B (8.33)
2
e
e
e
2
e
a
)
2
i=0
1
i
i =0
where
a ⎧ ⎪ 2 i , if e = 1
e i
i
B = ( ) = ⎨ i (8.34)
2
a
i
⎩ ⎪ 1, if e = 0
i
Thus, exponentiation can be accomplished by m successive multi-
i
2
plications. However, in normal basis, a can be obtained by a cyclic-
shift of the normal basis representation of a 2 i − 1 . Hence, from Eq. (8.34),
B is either the ith cyclically shifted version of a or 1. Therefore, the binary
i
or square-and-multiply method given in Eqs. (8.33) and (8.34) can be
implemented in the following algorithm:
Algorithm 8.5—Binary or square-and-multiply exponentiation in normal basis
c := a;
for i in 0 .. m-1 loop
b(i) := 1;
end loop;
for i in 0 .. m-1 loop
if e(i) = 1 then
b := NB_multiplier(b,c,h,w);
end if;
c := NB_sq(c);
end loop;
where NB_multiplier performs the normal basis multiplication pre-
m
sented in Algorithm 8.4 for a given field GF(2 ) with values h and w ,
j j,k
and where NB_sq implements the normal basis squaring. It must be
noted that in normal basis representation, 1 = (1,1, . . . ,1). An execut-
able Ada file NB_exp.adb, including Algorithm 8.5, is available at
www.arithmetic-circuits.org.
An example of datapath corresponding to Algorithm 8.5 is shown
in Fig. 8.3. The squaring operation is a simple signal rewiring, therefore
the minimum clock period is equal to T NB_multiplier . The total computa-
tion time (worst case) is about T ≈ mT .
NB multiplier
_
A VHDL model for the normal basis binary exponentiation algo-
rithm is given in the file NB_binary_exponentiation.vhd, available