Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems

8.3 OPERATIONS IN Z_p[x]/f(x)

Given a polynomial

of degree n (f_n ≠ 0) whose coefficients belong to Z_p (p prime), the set Z_p[x] /f(x) of polynomials of degree less than n, modulo f(x), is a finite ring (Chapter 2, Section 2.2.2).

8.3.1 Addition and Subtraction

Given two polynomials

the addition and the subtraction are defined as follows:

where a_i + b_i and a_i − b_i are computed modulo p. Assume that two procedures

procedure modular_addition (a, b: in coefficient; m: in
module; c: out coefficient);
procedure modular_subtraction (a, b: in coefficient; m: in
module; c: out coefficient);

have been defined. They compute (a + b) mod m and (a − b) mod m (see Sections 8.1.1 and 8.1.2). Then the addition and subtraction of polynomials are performed componentwise.

Algorithm 8.17 Addition of Polynomials

for i in 0..n−1 loop
   modular_addition (a(i), b(i), p, c(i));
end loop;

Algorithm 8.18 Subtraction of Polynomials

for i in 0..n−1 loop
   modular_subtraction (a(i), b(i), p, c(i));
end loop;

8.3.2 Multiplication

Given two polynomials

their product z(x)=a(x).b(x) can be computed as follows:

The ...