Page 216 - Hardware Implementation of Finite-Field Arithmetic

196 Cha pte r Se v e n

computed using the binary method [Knu81], also known as the square
and multiply method, which breaks the exponentiation operation into
m
a series of squaring and multiplication operations in GF(2 ).
The binary method [Knu81] is a popular algorithm for computing
e
b = a because it is suitable for hardware implementation ([SSTP88],
[Wan94], [Ara93]). 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 vector as e = e + e 2 + e 2 + . . . + e 2 m − 1 = (e , e , . . . , e ).
2
0 1 2 m − 1 0 1 m − 1
According to this method, we can obtain:
−
a ( ) ...( )
b = a = a ∑ m−1 e 2 i = a 0 () e 1 a 2 2 e 2 a 2 m−1 1 e m − 1 = m ∏ 1 B
2
e
e
i
i=0
i (7.44)
= i 0
where
2
a ⎧ ⎪ , i if e = 1
i
e
2
B = ( a ) i = ⎨ i (7.45)
i
⎩ ⎪ 1 , if e = 0
i
e
If the exponentiation a is performed from least significant bit (e )
0
to most significant bit (e ) of the exponent, it can be proved [Knu81]
m − 1
that this method requires ⎣log e⎦ + v(e) – 1 multiplications, where v(e)
2
is the number of binary ones in the exponent. The binary or square-
and-multiply method given in Eqs. (7.44) and (7.45) can be implemented
in the following algorithm:
Algorithm 7.16—Binary or square-and-multiply exponentiation
for i in 0 .. m-1 loop b(i) := 0; end loop;
c := a; b(0) := 1;
for i in 0 .. m-1 loop
if e(i) = 1 then b := LSBfirst(b,c,f); end if;
c := LSBfirst_squarer(c,f);
end loop;
where the result of the exponentiation is finally loaded at the bit
vector b, and where the multiplication and squaring operations are
computed with the functions LSBfirst and LSBfirst_squarer given in
Algorithms 7.3 and 7.10, respectively. An executable Ada file
SQandMult_exp.adb, including Algorithm 7.16, is available at www.
arithmetic-circuits.org.
A VHDL file exponentiation_sq_mult.vhd, modeling a sequential
implementation of Algorithm 7.16, is available at www.arithmetic-
circuits.org. The corresponding circuit is shown in Fig. 7.6.
The entity declaration of the binary or square-and-multiply
exponentiation circuit given in the VHDL file exponentiation_sq_
mult.vhd follows below.