Page 212 - Hardware Implementation of Finite-Field Arithmetic

192 Cha pte r Se v e n

0
2
m 1
with the initial values W () = a ⎣ ( ⎢ m 12⎥ x 2⎢ ⎣ ( − )/2⎥ ⎦ + ... + a x + ,
a
−
1
0 0
)/ ⎦
m 1
2
a () 0 = x 2⎢ ⎣ ( − )/2⎥ ⎦ x = x 2⎡ ⎢ m/2⎤ ⎥ , and k = 1, 2, . . . , ⎣m/2⎦. For the com-
2
2
(2)
putation, multiply-by-x , we can assume that a = ax mod f(x). A
straightforward multiply-by-x operation is equivalent to shift-left by
2
2 bits operation. Therefore, the following intermediate result is obtained:
+
2
m
3
a () = a m 1 x m 1 + a m 2 x + ... + a x + a x 2 (7.36)
−
−
0
1
where polynomial modulo operations have to be performed in order
to reduce the degree of a from m + 1 to less than or equal to m – 1.
(2)
The following polynomial f’(x) can be defined in order to do that:
f’(x) = f(x)x (7.37)
with f(x) = f x m − 1 + f x m − 2 + . . . + f x + f , and where the coefficients
m − 1 m − 2 1 0
of f’(x), f’ , can be computed from the coefficients of f(x), f , as
i i
follows:
⎪ f ⎧ i−1 + f m−1 f ; 1 ≤ i ≤ m − 1
i
f ' = ⎨ (7.38)
i
f ;
⎩ ⎪ f m−10 i = 0
+
For the irreducible polynomial f(x) = x + f x m − 1 . . . + f , we have x =
m
m
m − 1 0
f + f x + . . . + f x m − 1 . Therefore,
0 1 m − 1
m
x = f(x)
x m + 1 = f’(x) (7.39)
Substituting Eq. (7.39) into Eq. (7.36), we have
⎧ a + a f +′ a f ; 2 ≤ ≤ m 1−
i
−
−
−
⎪ i 2 m 1 i m 2 i
() 2
f ;
a i = a ⎨ m 1 f ′ 1 + a m−21 i = 1 (7.40)
−
−
⎪ a f ′ + a f ; i = 0
⎩ m −1 0 m −2 0
(2)
where a and a are coordinates of a and a , respectively. Therefore,
(2)
i i
m
LSB-first squaring operati on in GF(2 ) can be computed with the
following steps [JSP98]:
1. Initially,
m 1
2
W () 0 = a ⎢ ⎣ ( − )/ ⎦ x 2⎢ ⎣ ( − )/2⎥ ⎦ + ... + a x + a 0 0
m 12⎥
1
⎧ (7.41)
a 0 () = x 2 m/⎡ ⎢ 2⎤ ⎥ = ⎨ fx (), even m
'(
⎩ fx), odd m