15.2 INVERSION IN GF(p)

For relatively small p, the value of x−1 for all x image {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

image

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 pr(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 xp. 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;

image

Figure 15.11 Modulo p inverter.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset