Page 346 - Hardware Implementation of Finite-Field Arithmetic

326 App endix B

6
B.2.7 mod (x − 2) Division
In this case,

2
r = 1 + p + p + p + p + p 5
4
3
so that h(x) r − 1 can be computed as follows:
dx () = h x ()
0
dx () = d x () = h x () p
p
1 0
dx () = d x d x ( ) = hx 1 + p
()
)
( )
2 0 1
() = d x
dx () p ( 2 ) = h () x p 2 + p 3
3 2
() = d (() ()xd x =
pp +
x
dx h () 1++ 2 p 3
4 2 3
+
2 2
p
dx = () = h () p p + p 3 + p 4
() dx
x
5 4
pp
()
d x() = hxd x() = hx() 1++ 2 + p 3 + p 4
6 5
3
4
+
2
d (x) = d x ( ) = h x ( ) p p + p + p + p 5 = h x ( ) r−1
p
x
7 6
The corresponding division algorithm, similar to Algorithm 6.8,
is the following.
Algorithm B.1—mod f(x) division
a := h;
for j in 0 .. 5 loop e(j) := (a(j)*frobenius(j,1)) mod p;
end loop;
a := product_mod_f(e, a, f);
for j in 0 .. 5 loop e(j) := (a(j)*frobenius(j,2)) mod p;
end loop;
a := product_mod_f(e, a, f);
for j in 0 .. 5 loop e(j) := (a(j)*frobenius(j,1)) mod p;
end loop;
a := product_mod_f(e, h, f);
for j in 0 .. 5 loop e(j) := (a(j)*frobenius(j,1)) mod p;
end loop;
-- e = h r-1
a := product_mod_f(e, h, f); -- a = h r
-r
inv := invert(a(0)); a := e; -- inv = h , a = h r-1
for j in 0 .. 5 loop e(j) := (a(j)*inv) mod p; end loop;
-r
-- e = h r-1 .h = h -1
-1
z := product_mod_f(e, g, f); -- z = h .g
An example of datapath corresponding to Algorithm B.1 is shown
in Fig. B.1. The total computation time approximately amounts to