Page 297 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Other Bases 277

9.2 Triangular Bases
Let fx() =∑ m f x be an irreducible binary polynomial of degree m,
i
i=0 i
m
with f = f = 1 and f ∈ {0,1} for 0 < i < m, and let α ∈ GF(2 ) be a root
m 0 i
,
,
of f(x). The set Λ= {λλ ... ,λ } of m elements is called the
0 1 m −1
triangular basis of the polynomial basis Ω= {, ,1 αα ... ,α m −1 } if
2
,
m−1
i ∑
λ = f j+1 α ji 0 ≤ i ≤ m − 1 (9.19)
−
=
ji

where f ’s is the coefficient of the irreducible polynomial f(x) ([HB95],
i
m
[Has98], [FBF97], [HW00]). For any element A ∈ GF(2 ), its coordi-
nates with respect to the polynomial basis Ω and the triangular basis

Λ can be denoted as A = (, ,... a , m − 1 ) and A = (, , ... a , m − 1 ).
a a
a a
Λ
Ω
0
1
1
0

Since A =∑ m − 1 aα i =∑ m − 1 a λ , the conversion of the Λ coordinates to
i=0 i i=0 ii
the corresponding Ω coordinates can be performed as follows
[HW00]
⎧ a , i = 0
⎪
0
i
a m−− i = ⎨ ∑ a ≤≤ (9.20)
f
1
⎪ ij m j , 1 i m − 1
−
−
⎩ j=0
while the conversion of the Ω to Λ coordinates can be performed as
[HW00]
⎧ a , i = 0
⎪ m−1
a = ⎨ i−1 (9.21)
+
i a m−− ∑ a ≤ i ≤
f
⎪ 1 i i− −1 j m−−1 j , 1 i m − 1
⎩ j=0
T
T
Equation (9.21) can also be expressed as A = T A , where T
Λ
Ω
denotes vector transposition and where the transformation matrix T
is given as [Has98]
0 ⎛ 0 0 0 0 1 ⎞
0 ⎜ 0 0 0 1 t ⎟
⎜ 0 1 ⎟
2 ⎟
T = ⎜ 0 ⎜ 0 1 t 1 t ⎟ (9.22)
0 ⎜ 1 t t t t ⎟
⎜ 1 m − 4 m m−3 m−2 ⎟
⎝ 1 t 1 t 2 t m−3 t m−2 t m− ⎠
1

with t =∑ j−1 f t 0, ≤ i ≤ m − 1, and t = 1 [Has98].
−+
j i=0 mj i i 0