Page 298 - Hardware Implementation of Finite-Field Arithmetic

278 Cha pte r Ni ne

Triangular bases have been used by several authors for the
m
implementation of GF(2 ) arithmetic operations ([Has95], [Has98],
[FBF97], [HB95], [IHT06], [IST06]). For example, an efficient algorithm
m
for the computation of the GF(2 ) inversion over the polynomial basis
was given in [HW00]. This algorithm uses the above given expressions
and it is based on solving simultaneous linear equations over GF(2)
([HB92], [Has95]). The inversion algorithm is given as follows.
m
In order to compute the inverse B of an element A ∈ GF(2 ), with
A and B represented in the polynomial basis, assume that h terms in
i
GF(2) are defined as follows [HW00]:
⎧
⎪ a m−1 , i = 0
⎪
+
−
h = ⎨ a m−− ∑ i−1 h f , 1 ≤ i ≤ m − 1
i 1 i j=0 i−−1 j m−−1 j (9.23)
⎪ m −1
⎪ ∑ h f , m i − 1
≤≤ 2m
1
1
⎩ j =0 i −− j m −− j
m
Also assume that α ∈ GF(2 ) is a root of the irreducible polynomial
fx() =∑ m f x , B is the inverse of A, and g is the ith coordinate of the
i
i=0 i i
m
element G = B + α with respect to the polynomial basis. Then the
following equation holds ([Has95], [HB92], [HW00]):
⎛ s 0 s 1 s m 1 ⎞ ⎛ g ⎞ ⎛ s m ⎞
−
⎜ ⎟ ⎜ g 0 ⎟ ⎜ s ⎟
⎜ s 1 s 2 s m ⎟ ⎜ 1 ⎟ ⎜ m +1 ⎟
⎜ ⎟ ⎜ ⎟ = ⎜ ⎟ (9.24)
s ⎜ s s ⎟ g ⎜ m−2 ⎟ ⎟ ⎜s ⎟
−
−
−
⎜ m 2 m 1 2 m 3 ⎟ ⎜ ⎟ ⎜ 2 m −2 ⎟
s
⎝ s m 1 s m s 2m− ⎠ ⎝ g m− ⎠ ⎝ 2 m −1 ⎠
−
1
m 2

where s terms in GF(2) are defined as
i
⎧ h , 0 ≤≤ 2 m − 2
i
s = ⎨ i (9.25)
i ⎩ h + ,1 i = 2 m − 1
i
Using the above equations, the following algorithm for the
computation of A = B = G + α was given in [HW00]:
− 1
m
m
Algorithm 9.4—Algorithm for inversion over GF(2 )
m
Input: A ∈ GF(2 ) in polynomial basis.
Output: B = A -1 in polynomial basis.
1. Px() =∑ i = 0 p x = 1
m
i
i
2. Q(x) =∑ m q x = 1, L = 0, s = a
i
i = 0 i 0 m −1