Page 294 - Hardware Implementation of Finite-Field Arithmetic

274 Cha pte r Ni ne

3
2
4
For example, let f(x) = x + x + x + x + 1 be the defining irreduc-
8
8
253
ible polynomial for GF(2 ) and let β = α . Then the optimal dual basis
is {αα αα + αα 6 ,ααα 3 } in accord with Eqs. (9.13) and
, ,1+
5
2
2
7
3
4
,
,
,
,
(9.14) as given in [FBT96a]. In such a case, if p and d represent the
i i
coordinates of an element in the polynomial and dual bases, then the
conversion from dual to polynomial basis can be performed as p = d ,
0 2
p = d , p = d + d , p = d + d , p = d , p = d , p = d , p = d . Conversely,
1 1 2 0 2 3 3 7 4 6 5 5 6 4 7 3
the conversion from polynomial to dual basis can be performed as
d = p + p , d = p , d = p , d = p , d = p , d = p , d = p , d = d + d . In
0 0 2 1 1 2 0 3 7 4 6 5 5 6 4 7 3 7
8
the following algorithm, the dual basis multiplication over GF(2 )
253
4
8
3
2
using f(x) = x + x + x + x + 1 with β = α is given. In Algorithm 9.2,
conversions from dual to polynomial (and polynomial to dual) basis
are performed in such a way that the product C and the input ele-
ments A and B are represented in the polynomial basis.
8
8
Algorithm 9.2—Dual basis multiplication for GF(2 ) with f(x) = x +
2
3
x + x + x + 1
4
Ad(0) := m2xor(A(0),A(2)); Ad(1) := A(1); Ad(2) := A(0);
Ad(3) := A(7); Ad(4) := A(6); Ad(5) := A(5); Ad(6) := A(4);
Ad(7) := m2xor(A(3),A(7));
for i in m .. 2*m-2 loop Ad(i) := 0; end loop;
for i in 0 .. m-1 loop Cd(i) := 0; C(i) := 0; end loop;
for k in 0 .. m-2 loop
for i in 0 .. m-1 loop
Ad(m + k) := m2xor(Ad(m + k),m2and(F(i),Ad(i + k)));
end loop;
end loop;
for j in 0 .. m-1 loop
for i in 0 .. m-1 loop
Cd(j) := m2xor(Cd(j),m2and(Ad(j + i),B(i)));
end loop;
end loop;
C(0) := Cd(2); C(1) := Cd(1); C(2) := m2xor(Cd(0),Cd(2));
C(3) := m2xor(Cd(3),Cd(7)); C(4) := Cd(6); C(5) := Cd(5);
C(6) := Cd(4); C(7) := Cd(3);
In Algorithm 9.2, Ad and Cd represent the elements A and C,
expressed in the dual basis, where Ad has been defined as a bit vector
from 0 to 2m – 2. An executable Ada file dual_mult_conv_8.adb, includ-
ing Algorithm 9.2, is available at www.arithmetic-circuits.org.
Squaring over the dual basis can also be computed using t he
above formulation as follows [FBT96b]. Let X, Y ∈ GF(2 ) so that Y =
m
m
2
,
,
X and let {μμ ... ,μ } be a basis for GF(2 ). Moreover, let α be
0 1 m− 1
a root of the defining irreducible polynomial f(x) for the field, let
m
m
β ∈ GF(2 ); and let h be a linear function from GF(2 ) to GF(2). If X
−
is represented over this basis by X =∑ m−1 x μ , then X =∑ m 1 x μ
2
2
=
i=0 i i i 0 i i
and [FBT96b]