Page 117 - Hardware Implementation of Finite-Field Arithmetic

100 Cha pte r F o u r

z: out std_logic_vector(K-1 downto 0);
done: out std_logic
);
end Euclidean_divider;
The VHDL architecture corresponding to the circuit of Fig. 4.3 is
the following:

divider: nr_divider
port map(a, b, clk, reset, start_division, q, r, division_
done);
multiplier: mult_subt
port map(c, d, q, clk, reset, start_product, next_d,
product_done);
reducer: nr_reducer
port map(d, p, clk, reset, start_reduction, z, reduction_
done);
registers: process(clk)
begin
if clk’event and clk = ‘1’ then
if load = ‘1’ then a <= p; b <= y; c <= long_zero;
d <= zero&x;
elsif update = ‘1’ then
a <= b; b <= r; c <= d; d <= next_d;
end if;
end if;
end process registers;
b_equal_1 <= ‘1’ when b = one else ‘0’;
The complete model additionally includes a control unit.

4.2 Binary Algorithm

T he binary algorithm ([Knu81]) for computing the gcd of two naturals
is based on the following observation: Given two naturals a and b, if
both are even then gcd(a, b) = 2gcd(a/2, b/2); if one of them, say b, is
even and the other odd then gcd(a, b) = gcd(a, b/2); if both are odd and
b greater than or equal to a then gcd(a, b) = gcd(a, b − a) and b − a is
even.
Assume that a is odd and define a = a and b = b. Two sequences
0 0
a , a , a , . . . and b , b , b , . . . of naturals are generated ([BK83]): given
1 2 3 1 2 3
a and b with a odd, then
i i i
If b is even: a = a , b = b /2;
i i + 1 i i + 1 i
If b is odd and b ≥ a : a = a , b = b − a ;
i i i i + 1 i i + 1 i i
If b is odd and b < a : a = b , b = a − b .
i i i i + 1 i i + 1 i i
Obviously a is odd and gcd(a , b ) = gcd(a , b ) so that
i + 1 i + 1 i + 1 i i
gcd(a , b ) = gcd(a , b ) = . . . = gcd(a , b ) = gcd(a, b) (4.22)
i + 1 i + 1 i i 0 0