Page 135 - Hardware Implementation of Finite-Field Arithmetic

118 Cha pte r F i v e

where a(x) and b(x) are defined as polynomials with maximum
degree m − 1.
Assume that the function
function mod_m_addition(x, y, p, k: natural) return
natural

computing (x + y) mod p, with p a k-bit natural, is available. This
function implements the optimized binary mod p addition given in
Algorithm 3.2. Then the addition of two polynomials a(x) + b(x) in
Z [x]/f(x) is accomplished using Eq. (5.1) as follows:
p
Algorithm 5.2—Addition of polynomials mod p, version 2

for i in 0 .. m-1 loop
c(i) := mod_m_addition(a(i),b(i),p,m);
end loop;
where k has been particularized to be equal to m, and where the
polynomials a, b, and c range from 0 to m − 1. An executable Ada file
addition_mod_f_poly.adb, including Algorithm 5.2, is available at
www.arithmetic-circuits.org.
A VHDL model for the second version of the addition of polynom-
ials mod p (Algorithm 5.2) is given in the file adder_polynom.vhd which
is available at www.arithmetic-circuits.org. The entity declaration is
entity adder_polynom is
port(
a, b: in polynomial;
z: out polynomial
);
end adder_polynom;
The VHDL architecture is the following:
gen: for i in 0 to M-1 generate
addition: process(a,b)
variable z1, z2: std_logic_vector(K downto 0);
begin
z1 := a(i) + (‘0’ & b(i));
z2 := z1 - P;
if z1(K) = ‘0’ then z(i) <= z1(K-1 downto 0);
else z(i) <= z1(K-1 downto 0); end if;
end process;
end generate;
The subtraction of two elements a(x) − b(x) in Z [x]/f(x) is
p
accomplished using Eq. (5.1) as follows:
Algorithm 5.3—Subtraction of polynomials mod p
for i in 0 .. m-1 loop
c(i) := (a(i)-b(i)) mod p;
end loop;