Page 295 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Other Bases 275

(β
(βα =
2
hY j ) hX α j )
⎛ ⎛ m − 1 ⎞ ⎞ ⎞ m − 1
= h β ⎜ ∑ x μ i ⎟ α ⎟ = ∑ xh(βμ α j ) j = , ,01 ... , m − 1 (9.15)
j
i
2
i
2
⎜
⎜ ⎝ ⎠ ⎟ ⎠ i
i ⎝ =0 = i 0
,
If now the basis {μμ ... ,μ } is taken to be the dual basis to
,
0 1 m − 1
i
h Y
)
the polynomial basis with respect to h and β, then y = (βα , where
i
Y =∑ m − 1 y μ . Therefore the dual basis representation of Y is given as
i=0 i i
follows [FBT96b]:
⎛ h(βμ 2 h βμ ( ) h(βμ 2 ) ⎞
2 2
⎛ hY)β ⎞ 0 ) 1 m − 1 ⎛ x 0 ⎞
(
⎜ hY )βα ⎟ ⎜ ⎜ h(βμ α ) ( h βμ 1 ) α h(βμ 2 ) α ⎟ ⎟ ⎜ x ⎟
2
2
(
⎜ ⎟ = ⎜ ⎜ 0 m − 1 ⎟ ⎜ 1 ⎟

⎜ ⎟ ⎜ ⎟ ⎜ ⎟
h βμ α )
(βα
⎝ hY m−1 )⎠ ⎜ ⎝ h(βμ α m 1− ) ( 2 m 1− h(βμ 2 α m 1− ) ⎟ ⎝ m 1 ⎟ ⎠
⎜x
2
−
⎠
m 1−
0
1

(9.16)
For example, let f(x) = x + x + 1 be the defining irreducible
4
4
polynomial for GF(2 ) and let α be a root of f(x). If h is the least
significant polynomial coefficient and β = 1, then the optimal dual
basis to the polynomial basis {, ,1 αα 2 ,α 3 } is {,1 αα α
2
3
, } accordingly
,
with Eqs. (9.11) and (9.12) [FBT96a]. Therefore, using Eq. (9.16),
the coordinates y of the square of X, Y = X can be given as follows
2
i
[FBT96b]
y ⎛ ⎞ ⎛ 10 10⎞ ⎛ ⎞
x
0
0
⎜ ⎟ ⎜ 01 0 0 ⎟ ⎜ ⎟
y
x
1
1
⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ (9.17)
⎟ ⎜ ⎟
⎜ y 2⎟ ⎜ 01 01 x 2
⎜ ⎟
⎜ ⎟ ⎝ 00 1 0⎠ ⎝ ⎠
y ⎝ ⎠
⎠ x
3 3
where X and Y are represented in the dual basis.
Using Fermat’s theorem, the inverse of an element over the dual
m
basis in GF(2 ) ca n be found by successive squaring and multiplica-
m
tion. From Fermat’s theorem, that is, X 2 − 1 = 1, X 2 m = X holds. There-
fore, the inversion can be carried out by computing X −1 = X 2 m −2 , for
m
2
3
m
X ≠ 0 ∈ GF(2 ). Since 2 – 2 = 2 + 2 + 2 + . . . + 2 m − 1 , X −1 can be
expressed as [FBT96b]
3
2
1
2
2
2
X −1 = X 2 m − 2 = ( X )( X )( X ) ⋅ ⋅( X 2 m−1 ) (9.18)

Assume that the function
function dual_sq_GF4(Ad: poly_vector) return poly_
vector;