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 corresponding formal algorithm is the following.

Algorithm 8.19

z:=zero;
for i in 1..n loop z:=z*x+a(n-i)*b; end loop;

The computation primitives necessary for executing Algorithm 8.19 are:

• the multiplication of a polynomial by x,
• the multiplication of a polynomial by a coefficient,
• the addition of polynomials.

The addition is performed componentwise (Algorithm 8.17). The multiplication of a polynomial by a coefficient is also computed componentwise. Assume that a procedure

procedure modular product (a, b: in coefficient; m: in module;
c: out coefficient);

has been defined. It computes c = a.b mod m (see Section 8.1.3). Then the following procedure computes the product of a(x) by a coefficient b:

procedure by_coefficient (a: in polynomial; b: in coefficient;
p: in module; c: out polynomial)
is begin
  for i in 0..n−1 loop modular_product(a(i), b, p, c(i));
end loop;
end procedure;

It remains to generate a procedure for computing the multiplication of a polynomial a(x) by x. First observe that

so that

where

Compute now a(x).x:

The corresponding procedure is

procedure by_x (a: in polynomial; p: in module; b:
out polynomial) is
begin
  modular_product (a(n−1), r(0), p, b(0));
  for i in 1..n−1 loop
      modular_product (a(n−1), r(i), p, c);
      modular_addition (a(i-1), c, p, b(i));
end loop;
end procedure;

Thus Algorithm 8.19 is equivalent to the following one.

Algorithm 8.20 Multiplication of Polynomials, First Version

for i in 0..n−1 loop z(i):=0; end loop;
for i in 1.. n loop
  by_x(z, p, z1);
  by_coefficient(b, a(n-i), p, z2);
  for j in 0..n−1 loop modular_addition(z1(j), z2(j),
  p, z(j));  end loop;
  end loop;

The preceding algorithm can be decomposed at the coefficient level. The operations corresponding to the main loop are the following:

next_z(0)=(z(n−1).r(0)+b(0).a(n-i)) mod p,
next_z(1)=(z(0)+z(n−1).r(1)+b(1).a(n-i)) mod p,
next_z(2)=(z(1)+z(n−1).r(2)+b(2).a(n-i)) mod p,
…
next_z(n−1)=(z(n-2)+z(n−1).r(n−1)+b(n−1).a(n-i)) mod p,
z=next_z.

The complete algorithm is the following (the values of r_i = −f_i/f_n mod p should have been previously computed).

Algorithm 8.21 Multiplication of Polynomials, Second Version

Instead of addressing a new coefficient of a at each step (a(n − 1), a(n − 2), … , a(0)), an alternative solution is to use a procedure

right_rotate procedure(a: inout polynomial)

that substitutes

Algorithm 8.22 Multiplication of Polynomials, Third Version

for i in 0..n−1 loop z(i):=0; end loop;
for i in 1..n loop
  modular_product (z(n−1), r(0), p, c(0));
  modular_product (a(n−1), b(0), p, d(0));
  modular_addition (c(0), d(0), p, next_z(0));
  for i in 1..n−1 loop
     modular_product (z(n−1), r(i), p, c(i));
     modular_product (a(n−1), b(i), p, d(i));
     modular_addition (c(i), d(i), p, e(i));
     modular_addition (z(i-1), e(i), p, next_z(i));
  end loop;
  z:=next_z;
  righ_rotate(a);
end loop;