ν ← ν + gj · ±, ± ← „ (±)

Alternatively, one could use a Horner-like algorithm:

ν←0

for j ← k down to 0 do

ν ← „ (ν) + gj · β

With this implementation, Algorithm MP uses an expected number of O( 2 )

operations in F , an expected number of O( ) evaluations of „ , and space

for O( ) elements of F . Of course, the “warehouse” strategy is faster than

the “just in time” strategy by a constant factor, but it uses about times

as much space; thus, for large , using the “just in time” strategy is a very

good time/space trade-o¬.

19.4 Solving sparse linear systems 437

The invertible case. Now consider the case where „ is invertible, and

we want to solve (19.4) for a given δ ∈ V . We may as well assume that

δ = 0, since otherwise, γ = 0 is the unique solution to (19.4). We proceed

as follows. First, using Algorithm MP as discussed above, compute the

minimal polynomial φ of the sequence S de¬ned in (19.5), using β := δ. Let

φ = m cj Xj , where cm = 1 and m > 0. Then we have

j=0

c0 δ + c1 „ (δ) + · · · + cm „ m (δ) = 0. (19.6)

We claim that c0 = 0. To prove the claim, suppose that c0 = 0. Then

applying „ ’1 to (19.6), we would obtain

c1 δ + · · · + cm „ m’1 (δ) = 0,

which would imply that φ/X is a generating polynomial for S, contradicting

the minimality of φ. That proves the claim.

Since c0 = 0, we can apply „ ’1 to (19.6), and solve for γ = „ ’1 (δ) as

follows:

γ = ’c’1 (c1 δ + · · · + cm „ m’1 (δ)).

0

To actually compute γ, we use the same “just in time” strategy as was

used in the implementation of the computation of g S in Algorithm MP,

which costs O( 2 ) operations in F , O( ) evaluations of „ , and space for O( )

elements of F .

The non-invertible case. Now consider the case where „ is not invertible,

and we want to ¬nd non-zero vector γ ∈ V such that „ (γ) = 0. The idea

is this. Suppose we choose an arbitrary, non-zero element β of V , and use

Algorithm MP to compute the minimal polynomial φ of the sequence S

de¬ned in (19.5), using this value of β. Let φ = m cj Xj , where m > 0

j=0

and cm = 1. Then we have

c0 β + c1 „ (β) + · · · + cm „ m (β) = 0. (19.7)

Let

γ := c1 β + · · · cm „ m’1 (β).

We must have γ = 0, since γ = 0 would imply that φ/X is a non-zero

generating polynomial for S, contradicting the minimality of φ. If it happens

that c0 = 0, then equation (19.7) implies that „ (γ) = 0, and we are done.

As before, to actually compute γ, we use the same “just in time” strategy

as was used in the implementation of the computation of g S in Algorithm

MP, which costs O( 2 ) operations in F , O( ) evaluations of „ , and space for

O( ) elements of F .

438 Linearly generated sequences and applications

The above approach fails if c0 = 0. However, in this “bad” case, equation

(19.7) implies that β = ’c’1 „ (γ); that is, β ∈ img(„ ). One way to avoid

0

such a “bad” β is to randomize: as „ is not surjective, the image of „ is a

subspace of V of dimension strictly less than , and therefore, a randomly

chosen β lies in the image of „ with probability at most 1/|F |. So a simple

technique is to choose repeatedly β at random until we get a “good” β.

The overall complexity of the resulting algorithm will be as required: O( 2 )

expected operations in F , O( ) expected evaluations of „ , and space for O( )

elements of F .

As a special case of this situation, consider the problem that arose in

Chapter 16 in connection with algorithms for computing discrete logarithms

and factoring. We had to solve the following problem: given an — ( ’ 1)

matrix M with entries in a ¬nite ¬eld F , containing 1+o(1) non-zero entries,

¬nd a non-zero vector v ∈ F 1— such that vM = 0. To solve this problem,

we can augment the matrix M , adding an extra column of zeros, to get an

— matrix M . Now, let V = F 1— and let „ be the F -linear map on V

that sends γ ∈ V to γM . A non-zero solution γ to the equation „ (γ) = 0

will provide us with the solution to our original problem; thus, we can apply

the above technique directly, solving this problem using 2+o(1) expected

operations in F , and space for 1+o(1) elements of F . As a side remark, in

this particular application, we can choose a “good” β in the above algorithm

without randomization: just choose β := (0, . . . , 0, 1), which is clearly not

in the image of „ .

19.5 Computing minimal polynomials in F [X]/(f ) (II)

Let us return to the problem discussed in §18.2: F is a ¬eld, f ∈ F [X] is

a monic polynomial of degree > 0, and E := F [X]/(f ) = F [·], where

· := [X]f ; we are given an element ± ∈ E, and want to compute the minimal

polynomial φ ∈ F [X] of ± over F . As discussed in Example 19.2, this problem

is equivalent to the problem of computing the minimal polynomial of the

sequence

(±i := ±i , i = 0, 1, . . .),

S := (±0 , ±1 , . . .)

and the sequence has full rank; therefore, we can use Algorithm MP in §19.3

directly to solve this problem, assuming F is a ¬nite ¬eld.

If we use the “just in time” strategy in the implementation of Algorithm

MP, as was used in §19.4, we get an algorithm that computes the minimal

polynomial of ± using O( 3 ) expected operations in F , but space for just

O( 2 ) elements of F . Thus, in terms of space, this approach is far superior

19.5 Computing minimal polynomials in F [X]/(f ) (II) 439

to the algorithm in §18.2, based on Gaussian elimination. In terms of time

complexity, the algorithm based on linearly generated sequences is a bit

slower than the one based on Gaussian elimination (but only by a constant

factor). However, if we use any subquadratic-time algorithm for polynomial

arithmetic (see §18.6 and §18.7), we immediately get an algorithm that runs

in subcubic time, while still using linear space. In the exercises below, you

are asked to develop an algorithm that computes the minimal polynomial

of ± using just O( 2.5 ) operations in F , at the expense of requiring space

for O( 1.5 ) elements of F ” this algorithm does not rely on fast polynomial

arithmetic, and can be made even faster if such arithmetic is used.

Exercise 19.7. Let f ∈ F [X] be a monic polynomial of degree > 0 over a

¬eld F , and let E := F [X]/(f ). Also, let · := [X]f ∈ E. For computational

purposes, we assume that elements of E and DF (E) are represented as co-

ordinate vectors with respect to the usual “polynomial” basis 1, ·, . . . , · ’1 .

For β ∈ E, let Mβ denote the β-multiplication map on E that sends ± ∈ E

to ±β ∈ E, which is an F -linear map from E into E.

(a) Show how to compute ” given as input the polynomial f de¬ning

E, along with a projection π ∈ DF (E) and an element β ∈ E ” the

projection π —¦ Mβ ∈ DF (E), using O( 2 ) operations in F .

(b) Show how to compute ” given as input the polynomial f de¬ning

E, along with a projection π ∈ DF (E), an element ± ∈ E, and a

parameter k > 0 ”all of the k values

π(1), π(±), . . . , π(±k’1 )

using just O(k + k 1/2 2 ) operations in F , and space for O(k 1/2 )

elements of F . Hint: use the same hint as in Exercise 18.4.

Exercise 19.8. Let f ∈ F [X] be a monic polynomial over a ¬nite ¬eld F

of degree > 0, and let E := F [X]/(f ). Show how to use the result of the

previous exercise, as well as Exercise 18.4, to get an algorithm that computes

the minimal polynomial of ± ∈ E over F using O( 2.5 ) expected operations

in F , and space for O( 1.5 ) operations in F .

Exercise 19.9. Let f ∈ F [X] be a monic polynomial of degree > 0 over

a ¬eld F (not necessarily ¬nite), and let E := F [X]/(f ). Further, suppose

that f is irreducible, so that E is itself a ¬eld. Show how to compute

the minimal polynomial of ± ∈ E over F deterministically, satisfying the

following complexity bounds:

(a) O( 3 ) operations in F and space for O( ) elements of F ;

440 Linearly generated sequences and applications

2.5 ) 1.5 )

(b) O( operations in F and space for O( elements of F .

19.6 The algebra of linear transformations (—)

Throughout this chapter, one could hear the whispers of the algebra of linear

transformations. We develop some of the aspects of this theory here, leaving

a number of details as exercises. It will not play a role in any material that

follows, but it serves to provide the reader with a “bigger picture.”

Let F be a ¬eld and V be a non-trivial F -vector space. We denote by

LF (V ) the set of all F -linear maps from V into V . Elements of LF (V )

are called linear transformations. We can make LF (V ) into an F -vector

space by de¬ning addition and scalar multiplication as follows: for „, „ ∈