Page 291 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Other Bases 271

When {λλ 1 ,... ,λ m − 1 } is the polynomial basis {, , αα 2 ,... ,α m − 1 },
,
1
0
∈
linear functions of the form hz() = z i { , ,... , m − 1 } are very useful
01
,
i
m
because the values of h(z), because every z in GF(2 ) can be directly
obtained from the polynomial basis representation of z without any fur-
ther computation. From this fact, the following new definition of duality
was given in [FBT96a]. Let {λλ ,... ,λ } and {μμ ,... ,μ } be
,
,
0 1 m− 1 0 1 m− 1
two bases for GF(2 ), h is a nonzero linear function from GF(2 ) to
m
m
m
GF(2), and β ∈ GF(2 ), β ≠ 0. Then the two bases are said to be dual
with respect to h and β if
h(βλ μ ) δ i j , = 01 , m − 1 (9.5)
=
, ,...
i j ij
where δ is the Kronecker delta function, and {λλ 1 ,... ,λ m− 1 } and
,
ij
0
{μμ ,... ,μ } are the polynomial and dual bases, respectively. In
,
0 1 m− 1
m
this case, any element A ∈ GF(2 ) can be represented in the dual basis
as follows [FBT96a]:
m − 1
A = ∑ h Aβλ i )μ i (9.6)
(
i=0
By using different values of h and β in Eq. (9.5), for any given
m
basis there are now 2 − 1 dual basis instead of only one dual basis.
Therefore, the most convenient dual basis can be selected in such a
way that the complexity of the dual to polynomial basis conversion
could be reduced. For certain GF(2 ), β can be chosen so that the dual
m
basis is just a reordering of the polynomial basis [MKW89]. Morii et al.
[MKW89] considered the case where h is the trace function. However,
these results were extended for any general function h in [Fen93],
[FBT96a].
Using the above definition of duality, the following multiplication
algorithm over GF(p ) was given in [Fen93], [FBT96a]. Let A, B, C ∈ GF(p )
m
m
so that C = AB. Let α be a root of the defining irreducible polynomial f(x)
for the field, and let h be a linear function from GF(p ) to GF(p). If
m
β ∈ GF(p ), represents B over the polynomial basis as B =∑ m − 1 b α , then
m
i
i=0 i
the multiplication can be obtained as [FBT96a]
⎛ hA )β hAβα ) hAβα m − 1 )⎞ ⎛ b b ⎞ ⎛ hC ( β ) ⎞
(
(
(
0
⎜ hAβα ) hAβα 2 ) hAβα m ⎟ ⎜ b ⎟ ⎜ hC ( βα ) ⎟
(
(
(
)
⎜ ⎟ ⎜ 1 ⎟ = ⎜ ⎟ (9.7)

⎟ ⎜
⎜ ⎜ hAβα m − 1 hAβα m 2 m − ⎟ ⎜ ⎟ ⎟ ⎜ ⎝ hC ( βα m 1 ) )⎠ ⎟
−
hAβα
⎝
2
−
⎝ ( ) ( ) ( )⎠ b m 1⎠
A multiplier using dual basis was first proposed by Berlekamp
[Ber82]. Using the above multiplication algorithm, the Berlekamp
multiplier can be obtained [Ber82].