Page 28 - Hardware Implementation of Finite-Field Arithmetic

Mathematical Backgr ound 11

1.2.4 Polynomials

Definitions 1.17
1. If R is a commutative ring, then a polynomial in the
indeterminate x over R is an expression of the form
n
f (x) = a x + a x n − 1 + . . . + a x + a
n n − 1 1 0
where a ∈ R, ∀ i ∈ {0, 1, . . . , n}. The element a is called the
i i
i
coefficient of x in f (x).
2. The largest integer m (if any) such that a ≠ 0 is the degree of
m
f (x) . It is denoted deg (f) and a is called the leading
m
coefficient . If all the coefficients of f (x) are equal to 0 then
f (x) is called the zero polynomial and its degree defined to
be equal to −∞. The zero-degree polynomials are also called
constant polynomials .
3. A monic polynomial is a polynomial whose leading coefficient
is equal to 1.
4. The polynomial ring R[x] is the ring formed by the set of all poly-
nomials in the indeterminate x with coefficients in R. The two
operations are the standard polynomial addition and multi-
plication, with coefficient arithmetic performed in R. The
additive identity element 0 is the zero polynomial. The multipli-
cative identity element 1 is the monic constant polynomial.

3
3
4
Example 1.9 Let f (x) = x + 3x + 2x + 4 and g (x) = 4x + 3x + 4 be
elements of the polynomial ring Z [x]. The addition and multiplication
5
of the two polynomials is as follows:
3
f (x) + g (x) = x + 2x + 3
4
6
4
3
5
2
f (x)g (x) = 4x + 2x + 3x + x + 3x + x + 1
7
In the following text, we will deal almost exclusively with poly-
nomials over an arbitrary field F.
Definition 1.18 Thanks to the fact that F is a field, all the nonzero
coefficients have an inverse and the standard polynomial division
can also be performed. Thus, if g (x) and h(x) ≠ 0 are polynomials in
F[x], then there exist two polynomials q (x) (the quotient) and r (x) (the
remainder) in F[x] such that
g (x) = q (x)h(x) + r (x) where deg (r) < deg (h) (1.3)
Notation:

r (x) = g (x) mod h(x) q (x) = g (x) div h(x)