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).
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 (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;
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 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 ri = −fi/fn 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;