Page 161 - Hardware Implementation of Finite-Field Arithmetic

144 Cha pte r S i x

--thread1:
n_r := subtract(n_a, product(n_b,coef)); deg_r := deg_a;
while n_r(m) = 0 loop
n_r := multiply_by_x(n_r); deg_r := deg_r-1;
end loop;
--thread2:
e := d;
for i in 1 .. dif loop e := multiply_by_x(e, f);
end loop;
e := subtract(c, product(e,coef));
--
if deg_b >= deg_r then
n_a := n_b; deg_a := deg_b; n_b := n_r;
deg_b := deg_r;
c := d; d := e;
else n_a := n_r; deg_a := deg_r; c := e;
end if;
end loop;
z := product(d,invert(n_b(m)));

An executable Ada file pseudo_Euclidean_algorithm.adb, including
Algorithm 6.3, is available at www.arithmetic-circuits.org.
An example of datapath corresponding to Algorithm 6.3 is shown
in Fig. 6.1. It is important to note that the sequences of instructions
thread1 and thread2 can be executed in parallel. The control unit exe-
cutes the main loop in at least four clock cycles:
1. Load the initial values:
dif := deg_a - deg_b; coef := (n_a(m)*invert(n_b(m)))
mod p;
--thread1:
n_r := subtract(n_a, product(n_b,coef)); deg_r :=
deg_a;
--thread2:
e := d;
2. Normalize n_r(x) and update e(x) (executed at least once):
--thread1:
n_r := multiply_by_x(n_r); deg_r := deg_r-1; end
loop;
--thread2:
e := multiply_by_x(e, f);
3. Final value of e(x):
e := subtract(c, product(e,coef));

4. Swap if deg _r > deg_b.
As already quoted above, the number of executions of the main
loop is smaller than two times the degree of f, that is, 2m. As regards
the number of cycles, the worst case probably occurs when at each