Page 168 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF ( p ) 151

According to Eq. (6.23) and Lemma 6.4, c(n, x)h(x) ≡ a(n, x)g(x)
−1
mod f(x) where a(n, x) is a nonzero element of Z , so that (a(n, x)) c(n, x)
p
h(x) ≡ g(x) mod f(x) and
−1
−1
g(x)h (x) = (a(n, x)) c(n, x) mod f(x) (6.24)
Algorithm 6.5—Binary algorithm, version 2

A := f; B := h; C := zero; d := g; alpha := m; beta := m-1;
while beta >= 0 loop
if b(0) = 0 then
b := Shift_One(b); d := Divide_By_X(d, F); beta :=
beta - 1;
else
coef := (A(0)*Invert(B(0))) mod p;
Old_b := b; Old_d := d; old_beta := beta;
b := Shift_One(Subtract(A, Product(B, coef)));
d := Divide_By_X(Subtract(C, Product(D, coef)),F);
if alpha > beta then
a := Old_b; c := Old_d; beta := alpha - 1; alpha
:= old_beta;
else beta := beta - 1;
end if;
end if;
end loop;
Z := Product(c, Invert(a(0)));
An executable Ada file binary_polynomials2.adb, including Algo-
rithm 6.5, is available at www.arithmetic-circuits.org.
An example of datapath corresponding to Algorithm 6.5 is shown
in Fig. 6.2. The minimum clock period is equal to T +
mod-p-inverter
2T + 2T . In order to calculate an upper bound of
mod-p-multiplier mod-p-subtractor
the number of cycles take into account that α = m, β < m, so that,
0 0
according to Eq. (6.22), the number of cycles is smaller than 2m. Thus,
the total computation time is about
T ≈ 2m(T + 2T + 2T ) (6.25)
mod-p-inverter mod-p-multiplier mod-p-subtractor
A VHDL model has been generated for p = 239. As in the case of
the Euclidean algorithm (Sec. 6.1), the mod 239 inverter is a table
storing x mod 239 for all x in {1, 2, . . . , 238}, and the other components
−1
have been described in Chap. 3 (mod_239_multiplier.vhd, reduced
version of adder_subtractor.vhd). The complete VHDL file binary_
algorithm_polynomials.vhd is available at www.arithmetic-circuits.
org. The entity declaration is

entity binary_algorithm_polynomials is
port(
g, h: in polynomial;
clk, reset, start: in std_logic;