TABLE OF CONTENTS In this chapter we are concerned with the mathematical and computational properties of polynomials with one variable with coefficients from a field F. All the algorithms considered here are ultimately based on polynomial division.
In Section 4.1 we introduce the basic definitions, describe an algorithm for polynomial division, and then give an algorithm for polynomial expansion. In Section 4.2 we examine the gcd problem for polynomials and give versions of Euclid s algorithm and the extended Euclidean algorithm in this setting. In Section 4.3 we use the procedures in the first two sections to perform arithmetic operations for expressions in simple algebraic number fields and to extend the polynomial operations to this setting. In Section 4.4 we describe an algorithm for partial fraction expansion that is based on polynomial division, polynomial expansion, and the extended Euclidean algorithm.
Since the mathematical definitions and theorems apply for any coefficient field F, we present the ideas in this general setting. In a computational setting, however, the algorithms make most sense for coefficient fields where computation is effective and efficient.
Let u be a polynomial of the form
where the coefficients u j are from a field F. The notation F[ x] represents the set of all such polynomials.
Recall that lc (u, x) represents the leading coefficient of a polynomial and deg (u, x) its degree. [1] A polynomial with lc (u, x)=1 is called a monic
