With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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

Given a polynomial 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 the addition and the subtraction are defined as follows:  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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required