Page 243 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Polynomial Bases 223

Coordinates in Eq. (7.72) can also be obtained using Eqs. (7.66)
to (7.70).
It must be noted that at least one class 1 irreducible pentanomial
exists for every m in the range of 160 to 600 [RH04]. Therefore, class 1
irreducible pentanomials are good candidates for implementation of
elliptic curve cryptosystems. The following algorithm can be given
for the computation of the product using class 1 irreducible
pentanomials fx () = x + x + x + x + 1, with k ≤ m/2 and k = k – k ,
k
k
m
k
2
3
1
3 1 3 2
that implements the expressions given in Eqs. (7.66) to (7.70).
Algorithm 7.26—Mastrovito multiplication for class 1 pentanomials
d := vector_D(a,b);
e := vector_E(a,b);
for j in 0 .. k2-2 loop h(j) := m2xor(e(j+m-k3),
e(j+m-k2)); end loop;
for j in 0 .. k1-2 loop
e0(j) := m2xor(e(j),m2xor(h(j),e(j+m-k1)));
end loop;
for j in k1-1 .. k2-2 loop e0(j) := m2xor(e(j),h(j));
end loop;
for j in k2-1 .. k3-2 loop e0(j) := m2xor(e(j),e(j+m-k3));
end loop;
for j in k3-1 .. m-2 loop e0(j) := e(j); end loop;
e0(m-1) := 0;
for j in 0 .. k1-1 loop e1(j) := 0; end loop;
for j in k1 .. m-1 loop e1(j) := e0(j-k1); end loop;
for j in 0 .. k1-1 loop e01(j) := e0(j); end loop;
for j in k1 .. m-k2-1 loop e01(j) := m2xor(e0(j),e1(j));
end loop;
for j in m-k2 .. m-2 loop e01(j) := h(j+k2-m); end loop;
e01(m-1) := e1(m-1);
for j in 0 .. m-1 loop
if j < k2 then c(j) := m2xor(d(j),e01(j));
else c(j) := m2xor(d(j),m2xor(e01(j),e01(j-k2)));
end if;
end loop;

An executable Ada file mastrovito_multiplication_v2_pentanomials
.adb, including Algorithm 7.26 and the corresponding VHDL descrip-
tion of the circuit mastrovito_pentanom_multiplication.vhd, is available
at www.arithmetic-circuits.org.

7.7 FPGA Implementations
Several circuits described in this chapter have been implemented
within a Xilinx Spartan3 (speed grade-5) programmable device. The
times (period, total time) are expressed in ns. Timing constraints
were utilized when necessary. The parameters FFs and LUTs represent
the number of flip-flops and look-up tables, respectively. Every slice
includes two flip-flops and two look-up tables. All the source files are