library ieee; use ieee.std_logic_1164.all;
use ieee.std_logic_arith.all;
use ieee.std_logic_unsigned.all;
package mypackage is
constant n: natural := 8;
constant m: natural := 239;
type r_vector is array(0 to n) of std_logic_vector(n downto 0);
constant zero: std_logic_vector(n downto 0) := ('0', others => '0');
constant int_exp_2n: natural := 50;
constant int_exp_n: natural := 17;
constant one: std_logic_vector(n-1 downto 0) := conv_std_logic_vector(1, n);
end mypackage;

library ieee; use ieee.std_logic_1164.all;
use ieee.std_logic_arith.all;
use ieee.std_logic_unsigned.all;
use work.mypackage.all;
entity Montgomery_step is
port 
(r: in std_logic_vector(n downto 0);
y: in std_logic_vector(n-1 downto 0);
x: in std_logic;
next_r: out std_logic_vector(n downto 0)
);
end Montgomery_step;

architecture circuit of Montgomery_step is
signal long_r, y_by_x, a, m_by_a, two_r: std_logic_vector(n+1 downto 0);
signal module: std_logic_vector(n-1 downto 0);
begin
long_r <= '0'&r;
and_gates1: for i in 0 to n-1 generate y_by_x(i) <= y(i) and x; end generate;
y_by_x(n) <= '0'; 
y_by_x(n+1) <= '0';
a <= long_r + y_by_x;
module <= conv_std_logic_vector(m, n);
and_gates2: for i in 0 to n-1 generate m_by_a(i) <= module(i) and a(0); end generate;
m_by_a(n) <= '0'; 
m_by_a(n+1) <= '0';
two_r <= a + m_by_a;
next_r <= two_r(n+1 downto 1);
end circuit;

library ieee; use ieee.std_logic_1164.all;
use ieee.std_logic_arith.all;
use ieee.std_logic_unsigned.all;
use work.mypackage.all;
entity Montgomery_multiplier is
port (
x, y: in std_logic_vector(n-1 downto 0);
z: out std_logic_vector(n-1 downto 0)
);
end Montgomery_multiplier;

architecture circuit of Montgomery_multiplier is
component Montgomery_step
port 
(r: in std_logic_vector(n downto 0);
y: in std_logic_vector(n-1 downto 0);
x: in std_logic;
next_r: out std_logic_vector(n downto 0)
);
end component;
signal r: r_vector;
signal module: std_logic_vector(n-1 downto 0);
signal long_r_n, long_module, dif: std_logic_vector(n+1 downto 0);
begin
module <= conv_std_logic_vector(m, n);
r(0) <= zero;
iteration: for i in 0 to n-1 generate
step: Montgomery_step port map (r(i), y, x(i), r(i+1));
end generate;
long_r_n <= '0'&r(n);
long_module <= "00"&module;
dif <= long_r_n - long_module;
with dif(n+1) select z <= dif(n-1 downto 0) when '0', r(n)(n-1 downto 0) when others;
end circuit;

library ieee; use ieee.std_logic_1164.all;
use ieee.std_logic_arith.all;
use ieee.std_logic_unsigned.all;
use work.mypackage.all;
entity exp_data_path is
port (
y: in std_logic_vector(n-1 downto 0);
sel: in std_logic_vector(1 downto 0);
clk, enable_e, enable_y: in std_logic;
z: out std_logic_vector(n-1 downto 0)
);
end exp_data_path;

architecture circuit of exp_data_path is
signal mult_in1, mult_in2, mult_out, reg_e_in, e_t, y_t, exp_n, exp_2n: std_logic_vector(n-1 downto 0);
component Montgomery_multiplier
port (
x, y: in std_logic_vector(n-1 downto 0);
z: out std_logic_vector(n-1 downto 0)
);
end component;
begin
exp_2n <= conv_std_logic_vector(int_exp_2n, n);
with sel select mult_in1 <= y when "00", e_t when others;
with sel select mult_in2 <= exp_2n when "00", e_t when "01", y_t when "10", one when others;
multiplier: Montgomery_multiplier port map (mult_in1, mult_in2, mult_out);
exp_n <= conv_std_logic_vector(int_exp_n, n);
with sel select reg_e_in <= exp_n when "00", mult_out when others;
process(clk)
begin
if clk'event and clk = '1' then
if enable_e = '1' then e_t <= reg_e_in; end if;
end if;
end process;
process(clk)
begin
if clk'event and clk = '1' then
if enable_y = '1' then y_t <= mult_out; end if;
end if;
end process;
z <= e_t;
end circuit;

library ieee; use ieee.std_logic_1164.all;
use work.mypackage.all;
entity exp_control_unit is
port (clk, reset, start: in std_logic;
x: in std_logic_vector(n-1 downto 0);
done, enable_e, enable_y: out std_logic;
sel: out std_logic_vector(1 downto 0)
);
end exp_control_unit;

architecture rtl of exp_control_unit is
subtype internal_state is natural range 0 to 7;
signal state: internal_state;
subtype count is integer range 0 to n-1;
signal counter: count;
begin
process(clk, reset)
begin
case state is
when 0 => sel <= "00"; enable_e <= '0'; enable_y <= '0'; done <= '1';
when 1 => sel <= "00"; enable_e <= '0'; enable_y <= '0'; done <= '1';
when 2 => sel <= "00"; enable_e <= '1'; enable_y <= '0'; done <= '0';
when 3 => sel <= "00"; enable_e <= '0'; enable_y <= '1'; done <= '0';
when 4 => sel <= "01"; enable_e <= '1'; enable_y <= '0'; done <= '0'; 
when 5 => sel <= "10"; enable_e <= '1'; enable_y <= '0'; done <= '0'; 
when 6 => sel <= "10"; enable_e <= '0'; enable_y <= '0'; done <= '0'; 
when 7 => sel <= "11"; enable_e <= '1'; enable_y <= '0'; done <= '0'; 
end case;
if reset = '1' then state <= 0 ; counter <= n-1;
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; --0
when 3 => state <= state + 1; counter <= n-1; --1
when 4 => if x(counter) = '1' then state <= state + 1; else state <= 6; end if; counter <= counter - 1; --2
when 5 => state <= state + 1; --3
when 6 => if counter < 0 then state <= state + 1; else state <= 4; end if;
when 7 => state <= 0; --4  
end case;
end if;
end process;
end rtl;


library ieee; use ieee.std_logic_1164.all;
use ieee.std_logic_arith.all;
use ieee.std_logic_unsigned.all;
use work.mypackage.all;
entity exponentiate is 
port
(x, y: 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 exponentiate;

architecture circuit of exponentiate is
component exp_data_path
port (
y: in std_logic_vector(n-1 downto 0);
sel: in std_logic_vector(1 downto 0);
clk, enable_e, enable_y: in std_logic;
z: out std_logic_vector(n-1 downto 0)
);
end component;
component exp_control_unit
port (clk, reset, start: in std_logic;
x: in std_logic_vector(n-1 downto 0);
done, enable_e, enable_y: out std_logic;
sel: out std_logic_vector(1 downto 0)
);
end component;
signal sel: std_logic_vector(1 downto 0);
signal enable_e, enable_y: std_logic;
begin
first_component: exp_data_path port map (y, sel, clk, enable_e, enable_y, z);
second_component: exp_control_unit port map (clk, reset, start, x, done, enable_e, enable_y, sel);
end circuit;


--check that 211**150 = 166, 211**112 = 6, 7>**9 = 130:

library ieee; use ieee.std_logic_1164.all;
use ieee.std_logic_arith.all;
use ieee.std_logic_unsigned.all;
use work.mypackage.all;
entity test_exponentiate is end test_exponentiate;

architecture test of test_exponentiate is
component exponentiate
port
(x, y: 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 component;
signal x, y, z: std_logic_vector(n-1 downto 0);
signal clk, reset, start, done: std_logic := '0';
begin
clk <= not(clk) after 5 ns;
device_under_test: exponentiate port map(x, y, clk, reset, start, z, done);
x <= conv_std_logic_vector(150, n),
conv_std_logic_vector(112, n) after 1000 ns, 
conv_std_logic_vector(9, n) after 2000 ns;
y <= conv_std_logic_vector(211, n),
conv_std_logic_vector(7, n) after 2000 ns;
reset <= '1', '0' after 10 ns;
start <= '0', '1' after 50 ns, '0' after 100 ns,
'1' after 1050 ns, '0' after 1100 ns,
'1' after 2050 ns, '0' after 2100 ns;
end test;