For relatively small p, the value of x−1 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−1 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, n); one<=conv_std_logic_vector(1, n); module<=conv_std_logic_vector(p, n); with first_step select next_r_i<=r_iplus1 when ‘0’, module when others; with first_step select next_r_iplus1<=r_iplus2 when ‘0’, x when others; with first_step select next_c_i<=c_iplus1 when ‘0’, zero when others; with first_step select next_c_iplus1<=c_iplus2 when ‘0’, one when others; divider: functional_divider port map (r_i, r_iplus1, q, r_iplus2); multiplier: functional_multiplier port map (c_i, c_iplus1, q, c_iplus2); process(clk) begin if clk'event and clk=‘1’ then r_i<=next_r_i; r_iplus1<=next_r_iplus1; c_i<=next_c_i; end if; end process; process(clk) begin if clk'event and clk=‘1’ then if enable=‘1’ then c_iplus1<=next_c_iplus1; end if; end if; end process; gt_one<=‘1’ when r_iplus1>one else ‘0’; with c_iplus1(n-1) select z<=c_iplus1 when ‘0’, c_iplus1+ module when others; end circuit; entity inv_control_unit is port ( clk, reset, start, gt_one: in std_logic; first_step, enable, done: out std_logic ); end inv_control_unit; architecture rtl of inv_control_unit is subtype internal_state is natural range 0 to 3; signal state: internal_state; begin process(clk, reset) begin case state is when 0=>first_step<=‘1’; enable<=‘0’; done<=‘1’; when 1=>first_step<=‘1’; enable<=‘0’; done<=‘1’; when 2=>first_step<=‘1’; enable<=‘1’; done<=‘0’; when 3=>first_step<=‘0’; if gt_one=‘1’ then enable<=‘1’; else enable<=‘0’; end if; done<=‘0’; end case; if reset=‘1’ then state<=0; elsif clk'event and clk=‘1’ then case state is when 0=>if start=‘0’ then state<=state+1; end if; when 1=>if start=‘1’ then state<=state+1; end if; when 2=>state<=state+1; when 3=>if gt_one=‘0’ then state<=0; end if; end case; end if; end process; end rtl; entity field_inverter is port ( x: in std_logic_vector(n-1 downto 0); clk, reset, start: in std_logic; z: out std_logic_vector(n-1 downto 0); done: out std_logic ); end field_inverter; architecture circuit of field_inverter is component inv_data_path…end component; component inv_control_unit…end component; signal first_step, enable, gt_one: std_logic; begin first_component: inv_data_path port map (x, clk, first_step, enable, gt_one, z); second_component: inv_control_unit port map (clk, reset, start, gt_one, first_step, enable, done); end circuit;