Polynomial Arithmetic with Coefficients in Zp
Let us now consider polynomials in which the coefficients are
elements of some field F. We refer to this as a polynomial over the field F. In
that case, it is easy to show that the set of such polynomials is a ring,
referred to as a polynomial ring. That is, if we
consider each distinct polynomial to be an element of the set, then that set is
a ring.[5]
[5] In fact, the set of polynomials whose coefficients are elements of a commutative ring forms a polynomial ring, but that is of no interest in the present context.
When polynomial arithmetic is performed on polynomials over a
field, then division is possible. Note that this does not mean that exact division is possible. Let us clarify this
distinction. Within a field, given two elements a
and b, the quotient a/b is also an element
of the field. However, given a ring R that is not
a field, in general division will result in both a quotient and a remainder;
this is not exact division.
|
Consider the division 5/3 within a set S. If S is the set of
rational numbers, which is a field, then the result is simply expressed as 5/3
and is an element of S. Now suppose that S is the field Z7. In this case, we
calculate (using Table
4.3c):
5/3 = (5 x 31) mod 7 = (5 x 5) mod 7 = 4
which is an exact solution. Finally, suppose that S is the set of integers, which is a ring but not a
field. Then 5/3 produces a quotient of 1 and a remainder of 2:
5/3 = 1 + 2/3
5 = 1 x 3 + 2
Thus, division is not exact over the set of
integers.
|
Now, if we attempt to perform polynomial division over a
coefficient set that is not a field, we find that division is not always
defined.
|
If the coefficient set is the integers, then (5x2)/(3x) does
not have a solution, because it would require a coefficient with a value of 5/3,
which is not in the coefficient set. Suppose that we perform the same polynomial
division over Z7. Then we have (5x2)/(3x) =
4x which is a valid polynomial over
Z7.
|
However, as we demonstrate presently, even if the coefficient
set is a field, polynomial division is not necessarily exact. In general,
division will produce a quotient and a remainder:
No comments:
Post a Comment