There are many similarities between arithmetic in Z and in R[X], and the

similarities between Z and F [X] run even deeper. Many of the algorithms

we discuss in this chapter are quite similar to the corresponding algorithms

for integers.

As we did in Chapter 15 for matrices, we shall treat R as an “abstract

data type,” and measure the complexity of algorithms for polynomials over

a ring R by counting “operations in R.”

18.1 Basic arithmetic

Throughout this section, R denotes a non-trivial ring.

For computational purposes, we assume that a polynomial a =

k’1 i

i=0 ai X ∈ R[X] is represented as a coe¬cient vector (a0 , a1 , . . . , ak’1 ).

Further, when a is non-zero, the coe¬cient ak’1 should be non-zero.

The basic algorithms for addition, subtraction, multiplication, and divi-

sion of polynomials are quite straightforward adaptations of the correspond-

ing algorithms for integers. In fact, because of the lack of “carries,” these

algorithms are actually much simpler in the polynomial case. We brie¬‚y

discuss these algorithms here”analogous to our treatment of integer arith-

metic, we do not discuss the details of “stripping” leading zero coe¬cients.

For addition and subtraction, all we need to do is to add or subtract

coe¬cient vectors.

’1

k’1

For multiplication, let a = i=0 ai Xi ∈ R[X] and b = i=0 bi Xi ∈ R[X],

398

18.1 Basic arithmetic 399

k+ ’2

ci Xi ,

where k ≥ 1 and ≥ 1. The product c := a·b is of the form c = i=0

and can be computed using O(k ) operations in R as follows:

for i ← 0 to k + ’ 2 do ci ← 0

for i ← 0 to k ’ 1 do

for j ← 0 to ’ 1 do

ci+j ← ci+j + ai · bj

’1

For division, let a = k’1 ai Xi ∈ R[X] and b = i=0 bi Xi ∈ R[X], where

i=0

b ’1 ∈ R— . We want to compute polynomials q, r ∈ R[X] such that a = bq+r,

where deg(r) < ’1. If k < , we can simply set q ← 0 and r ← a; otherwise,

we can compute q and r using O( · (k ’ + 1)) operations in R using the

following algorithm:

t ← b’1 ∈ R

’1

for i ← 0 to k ’ 1 do ri ← ai

for i ← k ’ down to 0 do

qi ← t · ri+ ’1

for j ← 0 to ’ 1 do

ri+j ← ri+j ’ qi · bj

’2

k’

qi Xi , r ← i

q← i=0 ri X

i=0

With these simple algorithms, we obtain the polynomial analog of The-

orem 3.3. Let us de¬ne the length of a ∈ R[X], denoted len(a), to be the

length of its coe¬cient vector; more precisely, we de¬ne

deg(a) + 1 if a = 0,

len(a) :=

1 if a = 0.

It is sometimes more convenient to state the running times of algorithms in

terms of len(a), rather than deg(a) (the latter has the inconvenient habit of

taking on the value 0, or worse, ’∞).

Theorem 18.1. Let a and b be arbitrary polynomials in R[X].

(i) We can compute a ± b with O(len(a) + len(b)) operations in R.

(ii) We can compute a · b with O(len(a) len(b)) operations in R.

(iii) If b = 0 and lc(b) is a unit in R, we can compute q, r ∈ R[X] such

that a = bq + r and deg(r) < deg(b) with O(len(b) len(q)) operations

in R.

Analogous to algorithms for modular integer arithmetic, we can also do

arithmetic in the residue class ring R[X]/(n), where n ∈ R[X] is a polynomial

400 Polynomial arithmetic and applications

of degree > 0 whose leading coe¬cient lc(n) is a unit (in most applications,

we may in fact assume that n is monic). For ± ∈ R[X]/(n), there exists a

unique polynomial a ∈ R[X] with deg(a) < and ± = [a]n ; we call this

polynomial a the canonical representative of ±, and denote it by rep(±).

For computational purposes, we represent elements of R[X]/(n) by their

canonical representatives.

With this representation, addition and subtraction in R[X]/(n) can be

performed using O( ) operations in R, while multiplication takes O( 2 ) op-

erations in R.

The repeated-squaring algorithm for computing powers works equally well

in this setting: given ± ∈ R[X]/(n) and a non-negative exponent e, we can

compute ±e using O(len(e)) multiplications in R[X]/(n), and so a total of

O(len(e) 2 ) operations in R.

The following exercises deal with arithmetic with polynomials R[X] over

a ring R.

Exercise 18.1. State and re-work the polynomial analog of Exercise 3.22.

Exercise 18.2. State and re-work the polynomial analog of Exercise 3.23.

Assume n1 , . . . , nk are monic polynomials.

Exercise 18.3. Given a polynomial g ∈ R[X] and an element ± ∈ E, where

R is a subring of E, we may wish to compute g(±) ∈ E. A particularly

elegant and e¬cient way of doing this is called Horner™s rule. Suppose

g = k’1 gi Xi , where k ≥ 0 and gi ∈ R for i = 0, . . . , k ’ 1. Horner™s rule

i=0

computes g(±) as follows:

β ← 0E

for i ← k ’ 1 down to 0 do

β ← β · ± + ai

output β

Show that this algorithm correctly computes g(±) using k multiplications in

E and k additions in E.

Exercise 18.4. Let f ∈ R[X] be a monic polynomial of degree > 0, and

let E := R[X]/(f ). Suppose that in addition to f , we are given a polynomial

g ∈ R[X] of degree less than k and an element ± ∈ E, and we want to

compute g(±) ∈ E.

(a) Show that a straightforward application of Horner™s rule yields an

algorithm that uses O(k 2 ) operations in R, and requires space for

storing O( ) elements of R.

18.2 Computing minimal polynomials in F [X]/(f ) (I) 401

(b) Show how to compute g(±) using just O(k + k 1/2 2 ) operations in

R, at the expense of requiring space for storing O(k 1/2 ) elements of

R. Hint: ¬rst compute a table of powers 1, ±, . . . , ±m , for m ≈ k 1/2 .

Exercise 18.5. Given polynomials g, h ∈ R[X], show how to compute the

composition g(h) ∈ R[X] using O(len(g)2 len(h)2 ) operations in R.

Exercise 18.6. Suppose you are given three polynomials f, g, h ∈ Zp [X],

where p is a large prime, in particular, p ≥ 2 deg(g) deg(h). Design an

e¬cient probabilistic algorithm that tests if f = g(h) (i.e., if f equals g

composed with h). Your algorithm should have the following properties: if

f = g(h), it should always output “true,” and otherwise, it should output

“false” with probability at least 0.999. The expected running time of your

algorithm should be O((len(f ) + len(g) + len(h)) len(p)2 ).

18.2 Computing minimal polynomials in F [X]/(f ) (I)

In this section, we shall examine a computational problem to which we

shall return on several occasions, as it will serve to illustrate a number of

interesting algebraic and algorithmic concepts.

Let F be a ¬eld, f ∈ F [X] a monic polynomial of degree > 0, and let

E := F [X]/(f ). E is an F -algebra, and in particular, an F -vector space.

As an F -vector space, it has dimension . Suppose we are given an element

± ∈ E, and want to e¬ciently compute the minimal polynomial of ± over F ,

that is, the monic polynomial φ ∈ F [X] of least degree such that φ(±) = 0,

which we know has degree at most (see §17.5).

We can solve this problem using polynomial arithmetic and Gaussian

elimination, as follows. Consider the F -linear map ρ : F [X]¤ ’ E that