Page 274 - Hardware Implementation of Finite-Field Arithmetic

254 Cha pte r Ei g h t

• d = 1 ⇒
3
0
1
52
32
32
) (
)
r = 2 = 1⋅2 ⇒ B =(( A ) ( A ) 10 A )( 1 2 3 ⋅+1 = A (( 52 3 A ) 10 )(()A 2
0
r = 4 = 1⋅2 ⇒
2
2
10
2
110
3
3
52
32
32
52
2
1 2
B =(( A ) ( A ) ( ) 2 A ) 3 ⋅+2 = ( ( A ) ( A ) () ()A ) A 2 8 = A 3370
A )(

Assume that r_array has been defined as an array (0 . . . m/2 − 1)
of integers holding the values of the coefficients r of the exponent as
i
in Eq. (8.36). Assume also that the functions
function vectoint_k(x: poly_vector; k,p: integer)
return integer
function pow2j(q: integer) return integer
function inttovect(x: integer) return poly_vector
Convert k bits (starting in the pth bit) belonging to a bit vector with m bits
to its integer value; compute if the integer q is a power of 2 (i.e., if q = 2);
j
and convert an integer to its bit vector representation (with m bits) that
are available. Then the following algorithm implements the 2 -ary
k
method for exponentiation given in Algorithm 8.7 which computes A . e
k
Algorithm 8.8—2 -ary method for exponentiation in normal basis
for i in 0 .. m/2-1 loop r( i) := 0; end loop;
e := inttovect(g);
for i in 0 .. m/k-1 loop
r(i) := vectoint_k(e,k,i*k);
end loop;
for i in 0 .. m-1 loop b(i) := 1; end loop;
d := 2**k-1;
while d >= 1 loop
aux := NB_exp(a,d,h,w);
for i in 0 .. m/k-1 loop
q := r(i)/d;
if r(i) = d*(2**pow2j(q)) then
if k*i+pow2j(q) = 0 then
aux1 := aux;
elsif k*i+pow2j(q) = 1 then
aux1 := NB_sq(aux);
elsif k*i+pow2j(q) > 1 then
aux1 := NB_sq(aux);
for l in 1 .. (k*i+pow2j(q))-1 loop
aux1 := NB_multiplier(aux1,aux1,h,w);
end loop;
end if;
b := NB_multiplier(b,aux1,h,w);
end if;
end loop;
d := d - 2;
end loop;