bases for F [X]¤ and E: for F [X]¤ , let us take X , X ’1 , . . . , 1, and for E, let

us take 1, ·, . . . , · ’1 , where · := [X]f ∈ E. The matrix A representing the

map ρ (via multiplication on the right by A), is the ( + 1) — matrix A

whose ith row, for i = 1, . . . , + 1, is the coordinate vector of ± +1’i .

We apply Gaussian elimination to A to ¬nd a set of row vectors v1 , . . . , vs

that are coordinate vectors for a basis for the kernel of ρ. Now, the co-

ordinate vector of the minimal polynomial of ± is a linear combination of

v1 , . . . , vs . To ¬nd it, we form the s — ( + 1) matrix B whose rows consist

of v1 , . . . , vs , and apply Gaussian elimination to B, obtaining an s — ( + 1)

matrix B in reduced row echelon form whose row space is the same as that

of B. Let g be the polynomial whose coordinate vector is the last row of

B . Because of the choice of ordered basis for F [X]¤ , and because B is in

402 Polynomial arithmetic and applications

reduced row echelon form, it is clear that no non-zero polynomial in ker(ρ)

has degree less than that of g. Moreover, as g is already monic (again, by

the fact that B is in reduced row echelon form), it follows that g is in fact

the minimal polynomial of ± over F .

The total amount of work performed by this algorithm is O( 3 ) opera-

tions in F to build the matrix A (this just amounts to computing suc-

cessive powers of ±, that is, O( ) multiplications in E, each of which takes

O( 2 ) operations in F ), and O( 3 ) operations in F to perform both Gaussian

elimination steps.

18.3 Euclid™s algorithm

In this section, F denotes a ¬eld, and we consider the computation of great-

est common divisors in F [X].

The basic Euclidean algorithm for integers is easily adapted to compute

gcd(a, b), for polynomials a, b ∈ F [X]. Analogous to the integer case, we

assume that deg(a) ≥ deg(b); however, we shall also assume that a = 0.

This is not a serious restriction, of course, as gcd(0, 0) = 0, and making

this restriction will simplify the presentation a bit. Recall that we de¬ned

gcd(a, b) to be either zero or monic, and the assumption that a = 0 means

that gcd(a, b) is non-zero, and hence monic.

The following is the analog of Theorem 4.1.

Theorem 18.2. Let a, b ∈ F [X], with deg(a) ≥ deg(b) and a = 0. De¬ne

the polynomials r0 , r1 , . . . , r +1 ∈ F [X], and q1 , . . . , q ∈ F [X], where ≥ 0,

as follows:

a = r0 ,

b = r1 ,

(0 ¤ deg(r2 ) < deg(r1 )),

r0 = r 1 q 1 + r2

.

.

.

(0 ¤ deg(ri+1 ) < deg(ri )),

ri’1 = ri qi + ri+1

.

.

.

(0 ¤ deg(r ) < deg(r

r =r ’1 q ’1 +r ’1 )),

’2

r =r q (r = 0).

’1 +1

Note that by de¬nition, = 0 if b = 0, and > 0 otherwise; moreover,

r = 0.

Then we have r / lc(r ) = gcd(a, b), and if b = 0, then ¤ deg(b) + 1.

18.3 Euclid™s algorithm 403

Proof. Arguing as in the proof of Theorem 4.1, one sees that

gcd(a, b) = gcd(r0 , r1 ) = gcd(r , r +1 ) = gcd(r , 0) = r / lc(r ).

That proves the ¬rst statement.

For the second statement, if b = 0, then the degree sequence

deg(r1 ), deg(r2 ), . . . , deg(r )

is strictly decreasing, with deg(r ) ≥ 0, from which it follows that deg(b) =

deg(r1 ) ≥ ’ 1. 2

This gives us the following Euclidean algorithm for polynomials, which

takes as input polynomials a, b ∈ F [X] with deg(a) ≥ deg(b) and a = 0, and

which produces as output d = gcd(a, b) ∈ F [X].

r ← a, r ← b

while r = 0 do

r ← r mod r

(r, r ) ← (r , r )

d ← r/ lc(r) // make monic

output d

Theorem 18.3. Euclid™s algorithm for polynomials uses O(len(a) len(b))

operations in F .

Proof. The proof is almost identical to that of Theorem 4.2. Details are left

to the reader. 2

Just as for integers, if d = gcd(a, b), then aF [X] + bF [X] = dF [X], and so

there exist polynomials s and t such that as + bt = d. The procedure to

calculate s and t is precisely the same as in the integer case; however, in

the polynomial case, we can be much more precise about the relative sizes

of the objects involved in the calculation.

Theorem 18.4. Let a, b, r0 , r1 , . . . , r +1 and q1 , . . . , q be as in Theo-

rem 18.2. De¬ne polynomials s0 , s1 , . . . , s +1 ∈ F [X] and t0 , t1 , . . . , t +1 ∈

F [X] as follows:

s0 := 1, t0 := 0,

s1 := 0, t1 := 1,

and for i = 1, . . . , ,

si+1 := si’1 ’ si qi , ti+1 := ti’1 ’ ti qi .

404 Polynomial arithmetic and applications

Then:

(i) for i = 0, . . . , + 1, we have si a + ti b = ri ; in particular, s a + t b =

lc(r ) gcd(a, b);

(ii) for i = 0, . . . , , we have si ti+1 ’ ti si+1 = (’1)i ;

(iii) for i = 0, . . . , + 1, we have gcd(si , ti ) = 1;

(iv) for i = 1, . . . , + 1, we have

deg(ti ) = deg(a) ’ deg(ri’1 ),

and for i = 2, . . . , + 1, we have

deg(si ) = deg(b) ’ deg(ri’1 ).

Proof. (i), (ii), and (iii) are proved just as in the corresponding parts of

Theorem 4.3.

For (iv), the proof will hinge on the following facts:

• For i = 1, . . . , , we have deg(ri’1 ) ≥ deg(ri ), and since qi is the

quotient in dividing ri’1 by ri , we have deg(qi ) = deg(ri’1 ) ’ deg(ri ).

• For i = 2, . . . , , we have deg(ri’1 ) > deg(ri ).

We prove the statement involving the ti by induction on i, and leave the

proof of the statement involving the si to the reader.

One can see by inspection that this statement holds for i = 1, since

deg(t1 ) = 0 and r0 = a. If = 0, there is nothing more to prove, so assume

that > 0 and b = 0.

Now, for i = 2, we have t2 = 0 ’ 1 · q1 = ’q1 . Thus, deg(t2 ) = deg(q1 ) =

deg(r0 ) ’ deg(r1 ) = deg(a) ’ deg(r1 ).

Now for the induction step. Assume i ≥ 3. Then we have

deg(ti’1 qi’1 ) = deg(ti’1 ) + deg(qi’1 )

= deg(a) ’ deg(ri’2 ) + deg(qi’1 ) (by induction)

= deg(a) ’ deg(ri’1 )

(since deg(qi’1 ) = deg(ri’2 ) ’ deg(ri’1 ))

> deg(a) ’ deg(ri’3 ) (since deg(ri’3 ) > deg(ri’1 ))

= deg(ti’2 ) (by induction).

By de¬nition, ti = ti’2 ’ ti’1 qi’1 , and from the above reasoning, we see

that

deg(a) ’ deg(ri’1 ) = deg(ti’1 qi’1 ) > deg(ti’2 ),

from which it follows that deg(ti ) = deg(a) ’ deg(ri’1 ). 2

18.4 Computing modular inverses and Chinese remaindering 405

Note that part (iv) of the theorem implies that for i = 1, . . . , + 1, we

have deg(ti ) ¤ deg(a) and deg(si ) ¤ deg(b). Moreover, if deg(a) > 0 and

b = 0, then > 0 and deg(r ’1 ) > 0, and hence deg(t ) < deg(a) and

deg(s ) < deg(b).

We can easily turn the scheme described in Theorem 18.4 into a simple

algorithm, taking as input polynomials a, b ∈ F [X], such that deg(a) ≥

deg(b) and a = 0, and producing as output polynomials d, s, t ∈ F [X] such

that d = gcd(a, b) and as + bt = d:

r ← a, r ← b

s ← 1, s ← 0

t ← 0, t ← 1

while r = 0 do

Compute q, r such that r = r q + r , with deg(r ) < deg(r )