Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems

15.2 INVERSION IN GF(p)

For relatively small p, the value of x⁻¹ for all x {1, …,p − 1} can be computed in advance and stored within a look-up table. For larger values of p, Algorithm 8.16 can be used. As was already mentioned in Section 8.2, the value of c(i) belongs to the interval −p/2 < c(i) < p/2, so that

and all c(i) can be represented with n digits in reduced B's complement form. The value of r(i) belongs to the interval p ≥ r(i)≥1 so that all r(i) are n-digit base B numbers. The data path of the corresponding circuit is shown in Figure 15.11.

Example 15.7 (Complete VHDL source code available.) Generate the VHDL model of a circuit that computes z = x⁻¹ modulo p, where x and p are two n-bit numbers, with x ≤ p. The structure of the data path is shown in Figure 15.11.

entity inv_data_path is
port (
  x: in std_logic_vector(n-1 downto 0);
  clk, first_step, enable: in std_logic;
  gt_one: out std_logic;
  z: out std_logic_vector(n-1 downto 0)
);
end inv_data_path;

architecture circuit of inv_data_path is signal r_i, r_iplus1, r_iplus2, c_i, c_iplus1, c_iplus2, next_r_i, next_r_iplus1, next_c_i, next_c_iplus1, zero, one, module, q: std_logic_vector(n-1 downto 0); component functional_divider…end component; component functional_multiplier…end component; begin zero<=conv_std_logic_vector(0, ...