Page 164 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF ( p ) 147

short_out1(i) <= out1(i);
end generate;
with sel_e select
next_e <= d when “00”, out2 when “01”, short_out1 when
others;
with sel_a select next_a <= n_b when ‘0’, n_r when
others;
with sel_a select next_da <= deg_b when ‘0’, deg_r when
others;
by_x3: for i in 1 to m generate nb_by_x(i) <= n_b(i-1);
end generate;
nb_by_x(0) <= “00000000”;
with sel_b select next_b <= nb_by_x when ‘0’, n_r when
others;
with sel_b select next_db <= db_minus1 when ‘0’, deg_r
when others;
with sel_a select next_c <= d when ‘0’, e when others;
registers_ac: process(clk) ... end process registers_ac;
by_x4: for i in 1 to m generate h_by_x(i) <= h(i-1); end
generate;
h_by_x(0) <= “00000000”;
register_b: process(clk) ... end process register_b;
register_r: process(clk) ... end process register_r;
register_d: process(clk) ... end process register_d;
register_e: process(clk) ... end process register_e;
The complete model includes additionally a counter (variable dif
of Algorithm 6.3), combinational circuits that compute the branching
conditions and a control unit.
For great values of p, the mod p inverter and multiplier compo-
nents are sequential circuits so that additional state and control
signals must be added (start_inversion, inversion_done, start_prod-
uct, product_done). In Eq. (6.17) T and T must be
mod-p-inverter mod-p-multiplier
substituted by the total computation time (number of cycles by the
minimum clock period) of the corresponding operations.

6.2 Binary Algorithm
The binary algorithm ([WWSH02], [DS06], [HMV04]) for computing
the gcd of two polynomials is based on the following observation:
Given two polynomials a(x) and b(x), if both are divisible by x, that is,
if a = b = 0, then gcd(a(x), b(x)) = x · gcd(a(x)/x, b(x)/x); if one of them,
0 0
say b(x), is divisible by x (b = 0) and the other is not (a ≠ 0), then
0 0
gcd(a(x), b(x)) = gcd(a(x), b(x)/x); if none of them is divisible by x then
−1
define a new polynomial ab(x) = a(x) − a b b(x), so that gcd(a(x), b(x)) =
0 0
gcd(ab(x), b(x)) = gcd(ab(x), a(x)), and ab(x) is divisible by x.
Assume that a(x) is not divisible by x and degree(a(x)) > 0, and
define a(0, x) = a(x) and b(0, x)= b(x). Two sequences a(1, x), a(2, x),
a(3, x), . . . and b(1, x), b(2, x), b(3, x), . . . of polynomials are generated:
given a(i, x) and b(i, x) where a(i, x) is not divisible by x, then