Page 262 - Hardware Implementation of Finite-Field Arithmetic

242 Cha pte r Ei g h t

where A = (, i+1 ,... a , i−1 ) is the i-fold left cyclic shift of A, and the
i ()
a a
i
T
i ()
same is for B ([HWB93], [RH00]). It is easy to prove that the num-
bers of nonzero entries in all M ’s are equal [MBGMVY93]. Following
i
Mullin et al. [MOVW88], the number of nonzero entries in M is
i
known as the complexity of the normal basis N, which is defined by
C = H(M ) 0 ≤ i ≤ m − 1 (8.17)
N i
where H(M ) refers to the Hamming weight, that is, the number of
i
1s in M .
i
It can be proven ([RH00], [RH02]) that the multiplication
matrix M given in Eq. (8.14) is symmetric and its diagonal entries
are the elements of the normal basis {β 2 0 ,β 2 1 ,... ,β 2 m− 1 } . Denoting
M as M = (μ , ij ij , −1 , where μ ij , = μ j i , = β 2 i +2 j , it is easy to see that
m
)
=0
μ = μ 2 , < ij ≤ m− 1. In this way, given the m entries of the 0th
,
0
ij , i−1 j , −1
row of the M matrix, the remaining entries (except the leftmost
ones) can be generated by using some squaring operations (free of
cost in normal basis representations). In Eq. (8.14), the exponents of
β can be represented in the binary form using m bits where each
exponent has only two 1s and zeros elsewhere. Formally, if the set of
j
i
exponents of β in the M matrix are represented by R = {2 + 2 | 0 ≤ i,
j ≤ m – 1, i ≠ j}, then it can be observed that the elements of R belong
to the set of the ring of integers modulo 2 – 1. For these elements in
m
R, it can also be proven [RH00] that the cyclic distance between the
two 1s is in the range [1, v], where v = ⎣m/2⎦. If we let
δ = β 12 j j = 01,, ... v , (8.18)
+
j
then the entries of M can be obtained from δ ’s as follows [RH03a]:
j
⎧ δ 2 i , 0 <− v
ji ≤
⎪
⎨
μ ij , = μ j i , = ⎨ 2 j j − i (8.19)
j i
⎪ δ mi j , v <− ≤ m− 1
⎩
+−
Noting that
⎧ ⎪ δ , for m odd
δ = ⎨ v (8.20)
m − 1 − v δ , for m even
⎩ ⎪ v − 1
and

δ = δ 2 v for m even (8.21)
v v