Page 213 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Polynomial Bases 193

2. At step-k, with 1 ≤ k ≤ ⎣m/2⎦ − 1, the following values are
computed:

a ⎧ k ( −1 ) + a k ( −1 ) f +′ a k ( −1 ) f ; 2 ≤ i ≤ m − 1
i
⎪ ⎪ i−2 m−1 i m−2 i
k −1)
k −1)
(
a i k () = a ⎨ ( m−1 f ′ 1 + a m−2 f ; i = 1
1
⎪ ( k −1) f f ′ + ( k 1) i = (7.42)
−
⎩ ⎪ a m−1 0 a m 2 f ; 0
−
0
−
w k () = w ( k 1) + a ( (k−1 ) a
i i i ⎡ ⎢ m / ⎤ ⎥ +−1
2
k
3. For k = ⎣m/2⎦,
w k () = w k ( −1 ) + a k ( −1 ) a (7.43)
i i i m−1
4. Finally, the result is W = W (⎣m/2⎦) . For even values of the field
order m, m/2 steps are required. For odd values of m, (m – 1)/2
steps will be required.
Assume that the function
function Product_alpha(f: poly_vector) return poly_
vector

performing the product f’(x) = f(x)x given in Eq. (7.38) is available.
Then the above LSB-first squaring operation in GF(2 ) can be given in
m
the following algorithm:
Algorithm 7.15—LSB-first squaring, version 2

for i in 0 .. m-1 loop W(i) := 0; baux(i) := 0;
end loop;
for i in 0 .. (m-1)/2 loop W(2*i) := a(i); end loop;
if (m rem 2) = 0 then b := f; else b := Product_alpha(f);
end if;
faux := Product_alpha(f);
for k in 1 .. (m/2)-1 loop
for i in 2 .. m-1 loop
baux(i) :=
m2xor(b(i-2),m2xor(m2and(b(m-1),faux(i)),m2and
(b (m-2),f(i))));
end loop;
baux(1) := m2xor(m2and(b(m-1),faux(1)),m2and
(b (m-2),f(1)));
baux(0) := m2xor(m2and(b(m-1),faux(0)),m2and
(b (m-2),f(0)));
W := m2xvv(W,m2abv(a(((m+1)/2)+k-1),b));
b := baux;
end loop;
W := m2xvv(W,m2abv(a(m-1),b));