Page 293 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Other Bases 273

It must be noted that, from the above equations, the irreducible
m
polynomial f(x) selected for the field GF(2 ) influences the multiplication
complexity. Furthermore, field elements are represented only in a given
basis (normally the polynomial basis). Therefore, convenient dual basis
must be selected in such a way that the com plexity of the dual to
polynomial (and polynomial to dual) basis conversion could be
reduced. Morii et al. [MKW89] demonstrated that when the irreducible
m
m
k
polynomial for GF(2 ) is a trinomial of the form f(x) = x + x + 1 (m > k)
k
m
or a pentanomial of the form f(x) = x + x k + 2 + x k + 1 + x + 1 (m > k + 2),
then optimal dual bases can be found [FBT96a].
When the defining irreducible polynomial is a trinomial of the
form f(x) = x + x + 1 (m > k) and if β is selected in Eq. (9.5) so that
m
k
[FBT96a]
⎧1 , i =− 1
k
h(βα = ⎨ (9.11)
⎨
i
)
k
1
⎩ , 0 i = 0 , ,... , m − 1 (with i ≠ − 1 )
then the optimal dual basis to the polynomial basis is ([MKW89],
[Fen93])
{α k − 1 ,α k − 2 ,. . . , , ,α m − 1 ,α m − 2 ,. . . ,α k } (9.12)
α 1

Therefore, the dual basis is merely a permutation of the polynomial
basis and the basis conversion can be implemented simply by
wiring.
On the other hand, if the defining irreducible polynomial for
GF(2 ) is a pentanomial of the form f(x) = x + x k + 2 + x k + 1 + x + 1
k
m
m
(m > k + 2) and if β is selected in Eq. (9.5) in such a way that
[FBT96a]
⎧1 , i = 0 k ,
i
h(βα = ⎨ i ≠ (9.13)
)
⎩ , 0 i = 1 ,... , m − 1 (with k)
then the optimal dual basis to the polynomial basis is ([MKW89],
[Fen93])

α
{αα k −1 ,α k −2 ,... , , +1 αα k +1 + α m−1 ,α m−2 ,α m m−3 ,... ,α k +2 ,α k +1 }
k
k
,
,

(9.14)
Therefore, the dual basis can be obtained from the polynomial
basis with two mod 2 additions and a reordering of basis coefficients.
Optimal dual basis for m = 2, 3, . . . , 10, using irreducible trinomials
and pentanomials, were given in [FBT96a].