Page 335 - Hardware Implementation of Finite-Field Arithmetic

64
p = 2 192 – 2 – 1 315

A.4 mod p Multiplication

A.4.1 Generic Circuit
Three sequential generic circuits have been described in Chap. 3. The
corresponding entities are csa_mod_multiplier, dar_mod_multiplier, and
dar_csa_multiplier. The package storing the parameter values includes
the following constant definitions:
constant k: integer := 192;
--logk is the number of bits of k-1
constant logk: integer := 8;
constant m: std_logic_vector(k+1 downto 0) :=
“00” & X”fffffffffffffffffffffffffffffffeffffffffffff
ffff”;
--minus_m = 2**(k+2) - m
constant minus_m: std_logic_vector(k+1 downto 0) :=
“11” & X”00000000000000000000000000000001000000000000
0001”;
The implementation results are the following (Spartan3, speed-5)
(Table A.2):

FFs LUTs Slices Period Cycles Total time
csa_mod 1,271 3,678 2,053 6.233 384 2393.5
dar_mod 400 593 400 23.615 384 9068.2
dar_csa 597 1,835 1,113 9.796 384 3761.7

TABLE A.2 Cost and Delay of mod 2 192 − 2 64 − 1 Multipliers

All the source files are available at www.arithmetic-circuits.org.
A.4.2 Specific Circuit
Another method consists of multiplying x by y, and then reducing
mod p with a specific combinational circuit. For that, the carry-save
shift-and-add multiplier of Fig. 3.5 and the mod p reducer of Sec. 2.6.2
can be used. An additional ripple-carry adder is necessary for
summing up the outputs p and p of the carry-save adder. A complete
c s
VHDL file csa_modp192_multiplier is available at www.arithmetic-
circuits.org. The entity declaration is
entity csa_modp192_multiplier is
port (
x, y: in std_logic_vector(191 downto 0);
clk, reset, start: in std_logic;
z: out std_logic_vector(191 downto 0);
done: inout std_logic
);
end csa_modp192_multiplier;