Page 337 - Hardware Implementation of Finite-Field Arithmetic

64
p = 2 192 – 2 – 1 317

FFs LUTs Slices Period Cycles Total time
MSB-first 1,185 1,993 1,199 8.176 73,733 602,841
LSB-first 1,779 3,554 1,983 8.871 36,869 327,065

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

All the source files are available at www.arithmetic-circuits.org.

A.6 mod p Division
Four sequential generic circuits have been described in Chap. 4. The
corresponding entities are Euclidean_divider, binary_algorithm, plus_
minus, and Fermat_divider. All four circuits have been implemented
within Spartan3 (speed-5) programmable devices (Table A.4).

FFs LUTs Slices Period AverCycles AverTime
Euclidean 2,703 4,205 2,644 26.1 43,782.7 1,142,728
Binary 771 3,401 2,091 19.9 404.3 8,046
Plus-minus 798 2,016 1,103 26.2 260.7 6,831
Fermat 1,143 2,012 1,460 19.4 113,483 2,201,570

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

Obviously, the best option is the plus-minus algorithm. In this
case p mod 4 = 3 (the least significant bits of p are 11) so that Eq. (4.31)
is used for computing w4 − 1 mod p.
The package storing the parameter values includes the following
constant definitions:

constant K: natural := 192;
constant P: std_logic_vector(K downto 0) :=
‘0’&x”fffffffffffffffffffffffffffffffeffffffffffffffff”;
--LOGK+1 bits for representing integers between -k and k
constant LOGK: natural := 9;
--MINUS_P = -p
constant MINUS_P: std_logic_vector(K+1 downto 0) :=
(‘1’ & not P) + ‘1’;
--TWO_P = 2.p
constant TWO_P: std_logic_vector(K+1 downto 0) := P &
‘0’;
--if p mod 4 = 3:
constant pp1: std_logic_vector (K+1 downto 0) := p(k)&p;
constant pp3: std_logic_vector (K+1 downto 0) := MINUS_P;

All the source files are available at www.arithmetic-circuits.org.