## 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 ...