Page 136 - Hardware Implementation of Finite-Field Arithmetic

Operations over Z [ x ]/ f ( x ) 119
p

where a(x) and b(x) are defined as polynomials with maximum degree
m − 1.
Assume that the function
function mod_m_subtraction(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 subtraction given
in Algorithm 3.4. Then the subtraction of two polynomials a(x) − b(x)
in Z [x]/f(x) is accomplished using Eq. (5.1) as follows:
p
Algorithm 5.4—Subtraction of polynomials mod p, version 2

for i in 0 .. m-1 loop
c(i) := mod_m_subtraction(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
subtraction_mod_f_poly.adb, including Algorithm 5.4, is available at
www.arithmetic-circuits.org.
A VHDL model for the second version of the subtraction of
polynomials mod p (Algorithm 5.4) is given in the file subtractor_
polynom.vhd which is available at www.arithmetic-circuits.org. The
entity declaration is
entity subtractor_polynom is
port(
a, b: in polynomial;
z: out polynomial
);
end subtractor_polynom;

The VHDL architecture is the following:
gen: for i in 0 to M-1 generate
subt: process(a,b)
variable z1, z2: std_logic_vector(K downto 0);
begin
z1 := (‘0’ & a(i)) - 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;

A parallel adder in Z [x]/f(x) requires m Z adders, and its critical
p p
path delay is one Z adder. For the addition given in Algorithm 5.2,
p
where the function mod_m_addition that implements the optimized
binary mod p addition presented in Algorithm 3.2 is used, the delay
is given in Eq. (3.2).