Page 299 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Other Bases 279

3. for i = 1 to 2m do

4. d =∑ L p s
j = 0 ji − 1 − j
{ d, if i − 1 − 2 L ≥ 0
5. e = , 0 otherwise

⎛ P(x) ⎞ ⎛1 d ⎞ ⎛ P(x)⎞
⎟ ⎜
6. ⎜ ⎝ Q(x) ⎠ ⎟ = ⎜ e ⎝ 1 − e⎠ ⎝ xQ(x) ⎠ ⎟

7. L = e(i − L) + (1 − e)L
a ⎧ +∑ i − 1 s f , 1 ≤ i ≤ m − 1
−
⎪ m − 1 ∑ i m − 1 1 s j = 0 i −−1 j m −−1 j m ≤ i ≤ 2m − 2
⎪
,
f
8. s = ⎨ j = 0 m − i − 1 − j m − 1 j−
i 1 +∑ 1
⎪ j = 0 s i −− f 1−j j , i = 2 m − 1
1 j m −
⎪ don't care i = 2 m
⎩
9. end for
10. G = (p , p ... p m − 1 , p )
,
,
2
1
m
11. B = (p + f m − 1 , p + f m − 2 , ... p, m −1 + f p m + f)
,
1
2
1
0
Assume that the function bit2int converting a bit into its
corresponding integer is available. Assume also that the functions
m2xvvm and m2abvm performing the bit-wise XOR of two bit vectors
x and y with m + 1 bits (x XOR y , x XOR y , . . . , x XOR y ), and
0 0 1 1 m m
returning the multiplication of a bit x by a bit vector y with m + 1 bits
(x AND y , x AND y , . . . , x AND y ), respectively, are also available.
0 1 m
Furthermore, assume that the product xQ(x) given in step 6 in
Algorithm 9.4 is simply implemented using the function rshiftm
performing 1-bit right shift of a bit vector with m + 1 bits. Then,
Algorithm 9.4 can be implemented as follows:
Algorithm 9.5—Inversion over GF(2 )
m
-- Computation of h and s
h(0) := a(m-1);
for i in 1 .. m-1 loop
for j in 0 .. i-1 loop
h(i) := m2xor(h(i),m2and(h(i-1-j),f(m-1-j)));
end loop;
h(i) := m2xor(a(m-1-i),h(i));
end loop;
for i in m .. 2*m-1 loop
for j in 0 .. m-1 loop
h(i) := m2xor(h(i),m2and(h(i-1-j),f(m-1-j)));
end loop;