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

Given a polynomial

image

of degree n (fn ≠ 0) whose coefficients belong to Zp (p prime), the set Zp[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

image

the addition and the subtraction are defined as follows:

image

image

where ai + bi and ai − bi 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 (ab) 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 ...

Get Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.