# Q: Efficient modular arithmetic in VHDL

I'm building some modules in VHDL for handling modular arithmetic and want to make sure it's well-designed for timing and somewhat efficient when scaling up. This will need to work with 128-bit or 256-bit arithmetic when complete, but I'm testing it currently with small 16-bit numbers currently. There are two modules, mod_add for the basic modular arithmetic, and mod_mul for the multiplication built on top of modular addition.

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

generic(
bits : positive := 16;
modulo : positive := 15
);
port(
clk : in std_logic;
rst : in std_logic;
a : in std_logic_vector(bits-1 downto 0);
b : in std_logic_vector(bits-1 downto 0);
q : out std_logic_vector(bits-1 downto 0) := (others => '0')
);
end entity;

constant modulo_c : std_logic_vector(bits-1 downto 0) := std_logic_vector(to_unsigned(modulo, bits));
signal q_int : std_logic_vector(bits downto 0) := (others => '0');
signal q_out : std_logic_vector(bits downto 0) := (others => '0');
begin
process(clk)
begin
if rising_edge(clk) then
if rst = '1' then
q_int <= (others => '0');
q_out <= (others => '0');
else
q_int <= std_logic_vector(unsigned("0" & a) + unsigned("0" & b));
if unsigned(q_int) >= unsigned("0" & modulo_c) then
q_out <= std_logic_vector(unsigned(q_int) - unsigned(modulo_c));
else
q_out <= q_int;
end if;
end if;
end if;
end process;

q <= q_out(bits-1 downto 0);
end architecture behavior;

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity mod_mul is
generic(
bits : positive := 16;
modulo : positive := 15
);
port(
clk : in std_logic;
rst : in std_logic;
ready : out std_logic := '0';
a : in std_logic_vector(bits-1 downto 0);
b : in std_logic_vector(bits-1 downto 0);
q : out std_logic_vector(bits-1 downto 0) := (others => '0')
);
end entity;

architecture behavior of mod_mul is
generic(
bits : positive := 16;
modulo : positive := 15
);
port(
clk : in std_logic;
rst : in std_logic;
a : in std_logic_vector(bits-1 downto 0);
b : in std_logic_vector(bits-1 downto 0);
q : out std_logic_vector(bits-1 downto 0)
);

constant p_c : std_logic_vector(bits-1 downto 0) := std_logic_vector(to_unsigned(modulo, bits));
signal q_int : std_logic_vector(bits downto 0) := (others => '0');
signal q_out : std_logic_vector(bits downto 0) := (others => '0');

constant b_zero : std_logic_vector(bits-1 downto 0) := (others => '0');
signal b_shift : std_logic_vector(bits-1 downto 0) := (others => '0');
signal culm : std_logic_vector(bits-1 downto 0) := (others => '0');
signal val : std_logic_vector(bits-1 downto 0) := (others => '0');
signal culm_add_val : std_logic_vector(bits-1 downto 0) := (others => '0');
signal val_double : std_logic_vector(bits-1 downto 0) := (others => '0');
signal counter : std_logic_vector(1 downto 0) := "00";
begin
bits => bits,
modulo => modulo
) port map(
clk => clk,
rst => rst,
a => culm,
b => val,
);

bits => bits,
modulo => modulo
) port map(
clk => clk,
rst => rst,
a => val,
b => val,
q => val_double
);

process(clk)
begin
if rising_edge(clk) then
if rst = '1' then
counter <= (others => '0');
counter <= (others => '0');
else
counter <= std_logic_vector(unsigned(counter) + 1);
end if;
end if;
end process;

process(clk)
begin
if rising_edge(clk) then
if rst = '1' then
culm <= (others => '0');
val <= (others => '0');
culm <= (others => '0');
val <= a;
b_shift <= b;
elsif counter = "10" then
if b_shift(0) = '1' then
end if;
val <= val_double;
b_shift <= "0" & b_shift(bits-1 downto 1);
end if;
end if;
end process;

q <= culm;
ready <= '1' when b_shift = b_zero else '0';
end architecture behavior;


And the test bench for mod_mul:

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity test_mod_mul is
end entity test_mod_mul;

architecture behavioral of test_mod_mul is
component mod_mul
generic(
bits : positive := 16;
modulo : positive := 15
);
port(
clk : in std_logic;
rst : in std_logic;
a : in std_logic_vector(bits-1 downto 0);
b : in std_logic_vector(bits-1 downto 0);
q : out std_logic_vector(bits-1 downto 0)
);
end component mod_mul;

constant clk_period : time := 20 ns;
signal halt : boolean := false;

signal clk : std_logic := '0';
signal rst : std_logic := '0';
signal load : std_logic := '0';
signal a, b : std_logic_vector(15 downto 0);
signal a_in, b_in : integer := 0;

signal q : std_logic_vector(15 downto 0);
signal q_out : integer;
begin
uut: mod_mul port map(
clk => clk,
rst => rst,
a => a,
b => b,
q => q
);

a <= std_logic_vector(to_unsigned(a_in, a'length));
b <= std_logic_vector(to_unsigned(b_in, b'length));
q_out <= to_integer(unsigned(q));

process
begin
clk <= '1';
wait for clk_period/2;
clk <= '0';
wait for clk_period/2;
if halt then
wait;
end if;
end process;

process
procedure check_multiply(
constant a, b : in integer;
constant q : in integer) is
begin
wait until falling_edge(clk);
a_in <= a;
b_in <= b;
wait for clk_period;
wait until rising_edge(clk) and ready = '1';
assert q_out = q report "Failed mod multiplication" severity error;
end procedure check_multiply;
begin
rst <= '1';
wait for 10*clk_period;
rst <= '0';
wait for clk_period;
assert q_out = 0 report "Failed mod multiplication" severity failure;

check_multiply(2, 2, 4);
check_multiply(2, 3, 6);
check_multiply(3, 3, 9);
check_multiply(4, 4, 1);
check_multiply(6, 5, 0);
check_multiply(6, 7, 12);

wait for 1000 ns;
halt <= true;
wait;
end process;
end architecture behavioral;

• Can I ask what you are designing? ASIC? FPGA? What synthesis tools are you using? What arithmetic functions do you want to realize (in equations)? – JHBonarius Jun 26 '18 at 19:46