Page 146 - Hardware Implementation of Finite-Field Arithmetic

Operations over Z [ x ]/ f ( x ) 129
p

In this method, repeated squaring of the partial results is used to
reduce the required number of multiplications. Each integer exponent
k can be presented in its binary representation as a t-bit vector as
k = k + k 2 + k 2 + . . . + k 2 t − 1 = (k , k , . . . , k ). According to this
2
0 1 2 t − 1 0 1 t − 1
method, we can obtain:
t−1
a = a ∑ t − 1 k 2 i = a 0 () ( a ) k ... a ( 2 t − 1 ) k t t − 1 = ∏ B i (5.12)
2
k
2
k
2
k
i
a
i = 0
2
1
i=0
where
2
⎧ ⎪ , i
aif k = 1
i
2
B = ( a ) k i = ⎨ i (5.13)
i ⎩ ⎪ 1 , if k = 0
i
The square and multiply method given in Eqs. (5.12) and (5.13)
can be implemented in the following algorithm:
Algorithm 5.8—Square-and-multiply exponentiation mod f
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 k(i) = 1 then
b := LSEfirst(b,c,f);
end if;
c := LSEfirst(c,c,f);
end loop;
where the result of the exponentiation is the final value of the b(x)
polynomial, and where the multiplication and squaring operations
are both computed with the function LSE first given in Algorithm 5.7.
Furthermore, in Algorithm 5.8, t has been selected to be equal to m.
An executable Ada file exp_mod_f.adb, including Algorithm 5.8, is
available at www.arithmetic-circuits.org.
A VHDL model for the square-and-multiply exponentiation mod f
algorithm is given in the file exp_sq_mult.vhd, available at www.
arithmetic-circuits.org. The datapath corresponding to Algorithm 5.8
is shown in Fig. 5.4.
The entity declaration of the square-and-multiply exponentiator
mod f given in the file exp_sq_mult.vhd is

entity exp_sq_mult is
port (
A: in polynomial;
E: in std_logic_vector (N-1 downto 0);
clk, reset, start: in std_logic;