Page 257 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Normal Bases 237

i
2
m
GF(2 ). Now express each β , 0 ≤ i ≤ m – 1, by m-dimensional vectors
in the polynomial basis in the form
β = ∑ m− 0 1 b ij β j b ∈ GF() (8.2)
i
2
2
j=
ij
If the m × m matrix B = (b ) composed by the above m vec-
ij
tors is nonsingular, then β , β , . . . , β 2 m − 1 are linearly independent, and
0
1
2
2

hence f(x) is an N-polynomial ([Wan86], [MBGMVY93]). For large values
of m, this method requires a great number of computations. However, in
certain cases, there is a simple criterion that can be used to identify
m
n
N-polynomials, as stated in the following. Let m = 2 and f(x) = x +
+
f x m − 1 . . . + f x + f be an irreducible polynomial over GF(2). Then f(x)
m − 1 1 0
is an N-polynomial if and only if the coefficient f ≠ 0 [MBGMVY93].
m-1
n
Equivalently, for m = 2 , a necessary and sufficient condition for the set
0
{β 2 0 ,β 2 1 , ... ,β 2 m − 1 } to be a normal basis of GF(2 ) (and therefore, β ,
2
m
β , . . . , β 2 m − 1 , are linearly independent and β is a normal element), shows
1
2
that the trace of β obeys the following relation [Wan86]:
β β +
2
2
Tr()β =+ 2 β + ... + β 2 m − 1 = 1 (8.3)
Furthermore, if β ∈ GF(2 ) and β = β , i = 0, 1, . . . , m – 1, then
i
2
m
i
β is a normal element and therefore generates a normal basis
{ ,ββ ... ,β } of GF(2 ) over GF(2) if and only if the following
m
,
0 1 m − 1
matrix
⎛ Tr(ββ ) Tr(ββ ) Tr(ββ m − ) ⎞
0 1
0
00
⎜ Tr(ββ ) Tr(ββ ) Tr(ββ 1 ) ⎟

⎜ 10 1 1 1 m − 1 ⎟ (8.4)
⎜ ⎟
⎜ ⎝ Tr(β m − 10 ) Tr(β m − 1 1 ) Tr(β m − 1 m − ⎠ ⎟ )
β
β
β
1
1
is nonsingular [MBGMVY93].
2
3
4
Example 8.1 Let f(x) = x + x + x + x + 1 be an irreducible polynomial
8
for GF(2 ). If β is a root of f(x), it can be found that the matrix B = (b )
8
ij
composed by its conjugates β , β , . . . , β 2 m − 1 represented in the
1
0
2
2

polynomial basis is singular, and hence β and its conjugates are not
linearly independent and they don’t constitute a basis. Therefore,
3
f(x) = x + x + x + x + 1 is not an N-polynomial and β is not a normal
8
4
2
element. In this example m = 2 . Therefore, this conclusion could also
3
be reached using the fact that the trace of β is zero or because the coef-
ficient f = f = 0.
m − 1 7
8
In this case, β is not a normal element in GF(2 ). The elements 1+β,
+
β , 1+β , ββ , or β 253 are not normal elements either. On the other
3
3
3

=
5
hand, the field element ββ satisfies the normality requirements

2
and it generates the normal basis {, ,ββ ... ,β 2 m − 1 }. It can be proven
+
5
5
that the elements 1+β and ββ are also normal elements.