O'Reilly logo

Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems by Gustavo D. Sutter, Gery J.A. Bioul, Jean-Pierre Deschamps

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

No credit card required

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

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

Start Free Trial

No credit card required