Page 259 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Normal Bases 239

Since squaring means a cyclic shift of an element in a normal basis
representation, we have
2
2
2
C = A B = (a , a , . . . , a )(b , b , . . . , b )
m − 1 0 m − 2 m − 1 0 m − 2
= (c , c , . . . , c ) (8.7)
m − 1 0 m − 2
Hence, the last component c of the product C is obtained by
2
m − 2
the same function h given in Eq. (8.6) operating on the components of
A and B , that is, c = h(a , a , . . . , a ; b , b , . . . , b ). By squar-
2
2
m − 2 m − 1 0 m − 2 m − 1 0 m − 2
ing C repeatedly, we can find that:
c = h(a , a , . . . , a ; b , b , . . . , b )
m − 1 0 1 m − 1 0 1 m − 1
c = h(a , a , . . . , a ; b , b , . . . , b )
m − 2 m − 1 0 m − 2 m − 1 0 m − 2 (8.8)
. . .
c = h(a , a , . . . , a ; b , b , . . . , b )
0 1 2 m − 1 1 2 m − 1
The Eq. (8.8) define the Massey-Omura multiplier ([MO86],
[WTSDOR85]). In normal basis representation, this multiplier has the
property that the same logic function h that is used to compute the last
component c of the product, can be used to compute its remaining
m − 1
components c , c , . . . , c , c .
m − 2 m − 3 1 0
3
4
Example 8.2 Normal basis multiplication for f(x) = x + x + 1
Let f(x) = x + x + 1 be the generating irreducible polynomial for
3
4
4
GF(2 ). This polynomial is an N-polynomial because if α is a root of
8
4
f(x), then the elements α, α , α , and α are linearly independent and
2
therefore, the set of roots {α, α , α , α } constitutes a normal basis of
2
8
4
4
GF(2 ). Alternatively, we can conclude that f(x) is an N-polynomial
2
because m = 4 = 2 and f = f ≠ 0 (see Sec. 8.1).
m − 1 3
4
Any two elements A and B in GF(2 ) can be expressed as A = a α +
0
8
2
4
2
4
8
a α + a α + a α and B = b α + b α + b α + b α . Therefore, the product
1 2 3 0 1 2 3
C = AB can be computed as follows:
C = AB = ( α + a α 2 + a α 4 + a α 8 )( b α + b α 2 + b α 4 + b α )
8 8
a
0 1 2 3 0 1 2 3
= c α +c α 2 +c α 4 +c α = α 12 (a b + a b ) + α 10 (aab + a b )
8
0 1 2 3 23 3 2 13 3 1
+α 9 ( ab + ab +) α 8 ( a b +) α 6 ( a b + ab ) + α 5 ( a b + a b ) (8.9)
30 03 22 2 1 1 1 2 20 0 2
+α 4 ( ab ) + α 3 ( a b + a b ) + α 2 ( ab ) + α ( ab )
a
11 01 10 00 33
5
6
12
10
3
9
The elements α , α , α , α , α , and α have been created, and these
elements must be represented in the normal basis. Using the fact that
3
f(α) = α + α + 1 = 0, we have α = α + 1. Therefore, one can find
4
3
4
α 12 = α + α + α 2
4
8
α 10 = α + α 2
8
α = α + α + α
8
9
4
(8.10)
α = α + α + α
2
4
6
α = α 4 + α
=
5
α 3 = α 8 + α 2 + α