Page 290 - Hardware Implementation of Finite-Field Arithmetic

270 Cha pte r Ni ne

Using Eq. (9.2), the multiplication of two field elements can be
given as follows [HTDR88]. Let {λλ 1 ,... ,λ m − 1 } be a basis of GF(2 )
,
m
0
,
,
and let {μμ ... ,μ } be its dual basis. Then the product C = AB of
0 1 m − 1
m
two field elements A, B ∈ GF(2 ) can be represented in the dual basis
as follows:
m − 1 m − 1 m − 1
=
=
C = ∑ μ i ∑ Tr Cλ μ( ) i ∑ Tr ABλ μ( ) (9.3)
c
i i i i
i=0 i=0 i=0 0
where c = Tr(Cλ ) is the ith coefficient of the product in the dual basis,
i
i
A =∑ m − 1 a μ , and B =∑ m − 1 b λ . Therefore, the element B is represent-
i=0 i i i=0 ii
,
ed in the basis {λλ ... ,λ m− 1 }, as long as the element A and the
,
1
0
product C are represented in the dual basis {μμ ,... ,μ }.
,
0 1 m − 1
Some bases other than the dual basis can still achieve the dual
basis style. These bases, normally referred to as weakly dual bases,
are obtained by inserting a fixed nonzero field element into the
trace function that defines the dual basis. Weakly dual bases can
be defined in the following ([WH98], [WH01]). Let {λλ 1 ,... ,λ m − 1 }
,
0
and {μμ 1 ,... ,μ m − 1 } be two bases for GF(2 ) and β ∈ GF(2 ), β ≠ 0.
,
m
m
0
Then, the bases are said to be weakly dual to each other.
{μμ 1 ,... ,μ m− 1 } is a weakly dual basis of {λλ 1 ,... ,λ m − 1 } if
,
,
0
0
=
Tr(βλ μ ) δ , i j , = 01 , m − 1 where δ is the Kronecker delta
,
, ,...
i j ij ij
function, which is equal to 1 if i = j and 0 otherwise ([WH98],
[WHB98], [WH01]). It must be noted that this condition for the
trace function is equal to the condition given in Eq. (9.1) simply by
inserting the element β into the trace function. Therefore, when
β = 1, {λλ 1 ,... ,λ m − 1 } and {μμ 1 ,... ,μ m − 1 } they are said to be a
,
,
0
0
pair of dual basis.
The above idea of the trace function can be extended to include
any general linear function [FBT96a] in such a way that any linear
m
function h from GF(2 ) to GF(2) can be considered to be of the form
hz () = Tr z), ∀β z GF(∈ 2 m ), for some β in GF(2 ). As a result, there are
m
(
m
m
2 linear functions h from GF(2 ) to GF(2). Furthermore, these
functions are of the form
m − 1
hz () = ∑ x z ∀ z GF(∈ 2 m ) (9.4)
ii
i=0
where x ∈ GF(2) and the addition is performed modulo 2 [FBT96a].
i
Let {λλ ,... ,λ } be a basis for GF(2 ) and let h be a nonzero
m
,
0 1 m − 1
m
linear function from GF(2 ) to GF(2). Then the dual basis
of {λλ ,... ,λ m − } with respect to the function h is the basis
,
1
1
{μμ 0 ,... ,μ } so that h(λ μ ) = 1 if i = j, 0 otherwise [KL99].
,
0 1 m − 1 i j