Page 92 - Hardware Implementation of Finite-Field Arithmetic

mod m Operations 75

ss(i) <= ps(i) xor pc(i) xor long_y(i);
sc(i+1) <= (ps(i) and pc(i)) or (ps(i) and long_y(i))
or (pc(i) and long_y(i));
end generate;
ss(K+1) <= ps(K+1) xor pc(K+1) xor long_y(K+1);
two_ps <= ps(K downto 0) & ‘0’;
two_pc <= pc(K downto 0) & ‘0’;
with step_type select ws <= two_ps when ‘0’, ss when
others;
with step_type select wc <= two_pc when ‘0’, sc when
others;
t <= ws(k+1 downto k-1) + wc(k+1 downto k-1);
quotient(1) <= t(2) xor (t(1) and t(0));
quotient(0) <= not(t(2) and t(1) and t(0));
with quotient select u <=
minus_M when «01», long_ZERO when «00», M when others;
second_csa: for i in 0 to k generate
next_ps(i) <= ws(i) xor wc(i) xor u(i);
next_pc(i+1) <= (ws(i) and wc(i)) or
(ws(i) and u(i)) or (wc(i) and u(i));
end generate;
next_ps(k+1) <= ws(k+1) xor wc(k+1) xor u(k+1);
parallel_register: process(clk)
begin
if clk’event and clk = ‘1’ then
if load = ‘1’ then
ps <= (others => ‘0’); pc <= (others => ‘0’);
elsif condition = ‘1’ then
ps <= next_ps; pc(k+1 downto 1) <= next_pc;
end if;
end if;
end process parallel_register;
The complete model additionally includes a k-bit shift register, a
3-input combinational circuit generating condition, the adders
corresponding to the final steps, a k-state counter, and a control unit.
As regards the done flag, a comment similar to Comment 2.1 must be
done.

3.4.3 Montgomery Multiplication

3.4.3.1 Montgomery Arithmetic
Consider two natural numbers m and R > m, and assume that they are
relatively prime, that is, gcd(m, R) = 1. Then there exists an element
R of Z such that
−1
m
− 1
RR mod m = 1 (3.11)
Define an application T from Z to Z :
m m
T(x) = xR mod m (3.12)