over function ¬elds). Depending on the setting and many implementation

details, such asymptotically fast algorithms for multiplication and division

can be signi¬cantly faster than the quadratic-time algorithms, even for quite

moderately sized inputs of practical interest. However, the fast Euclidean

algorithms are only useful for signi¬cantly larger inputs.

19

Linearly generated sequences and applications

In this chapter, we develop some of the theory of linearly generated se-

quences. As an application, we develop an e¬cient algorithm for solv-

ing sparse systems of linear equations, such as those that arise in the

subexponential-time algorithms for discrete logarithms and factoring in

Chapter 16. These topics illustrate the beautiful interplay between the arith-

metic of polynomials, linear algebra, and the use of randomization in the

design of algorithms.

19.1 Basic de¬nitions and properties

Let F be a ¬eld, let V be an F -vector space, and consider an in¬nite sequence

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

where ±i ∈ V for i = 0, 1, 2 . . . . We say that S is linearly generated (over

F ) if there exist scalars a0 , . . . , ak’1 ∈ F such that the following recurrence

relation holds:

k’1

±k+i = aj ±j+i (for i = 0, 1, 2, . . .).

j=0

In this case, all of the elements of the sequence S are determined by the initial

segment ±0 , . . . , ±k’1 , together with the coe¬cients a0 , . . . , ak’1 de¬ning the

recurrence relation.

The general problem we consider is this: how to determine the coe¬cients

de¬ning such a recurrence relation, given a su¬ciently long initial segment

of S. To study this problem, it turns out to be very useful to rephrase the

problem slightly. Let g ∈ F [X] be a polynomial of degree, say, k, and write

423

424 Linearly generated sequences and applications

k j

g= j=0 gj X . Next, de¬ne

k

g S := gj ±j .

j=0

Then it is clear that S is linearly generated if and only if there exists a

non-zero polynomial g such that

(Xi g) S = 0 (for i = 0, 1, 2, . . .). (19.1)

Indeed, if there is such a non-zero polynomial g, then we can take

a0 := ’(g0 /gk ), a1 := ’(g1 /gk ), . . . , ak’1 := ’(gk’1 /gk )

as coe¬cients de¬ning the recurrence relation for S. We call a polynomial g

satisfying (19.1) a generating polynomial for S. The sequence S will in

general have many generating polynomials. Note that the zero polynomial is

technically considered a generating polynomial, but is not a very interesting

one.

Let G(S) be the set of all generating polynomials for S.

Theorem 19.1. G(S) is an ideal of F [X].

Proof. First, note that for any two polynomials f, g, we have (f + g) S =

(f S) + (g S) ” this is clear from the de¬nitions. It is also clear that

for any c ∈ F and f ∈ F [X], we have (cf ) S = c · (f S). From these

two observations, it is immediately clear that G(S) is closed under addition

and scalar multiplication. It is also clear from the de¬nition that G(S) is

closed under multiplication by X; indeed, if (Xi f ) S = 0 for all i ≥ 0, then

certainly, (Xi (Xf )) S = (Xi+1 f ) S = 0 for all i ≥ 0. But any non-empty

subset of F [X] that is closed under addition, multiplication by elements of

F , and multiplication by X is an ideal of F [X] (see Exercise 9.27). 2

Since all ideals of F [X] are principal, it follows that G(S) is the ideal of

F [X] generated by some polynomial φ ∈ F [X] ” we can make this polyno-

mial unique by choosing the monic associate (if it is non-zero), and we call

this polynomial the minimal polynomial of S. Note that S is linearly

generated if and only if φ = 0.

We can now restate our main objective as follows: given a su¬ciently

long initial segment of a linearly generated sequence, determine its minimal

polynomial.

Example 19.1. Of course, one can always de¬ne a linearly generated se-

quence by simply choosing an initial sequence ±0 , ±1 , . . . , ±k’1 , along with

19.1 Basic de¬nitions and properties 425

the coe¬cients g0 , . . . , gk’1 of a generating polynomial g := g0 + g1 X + · · · +

gk’1 Xk’1 + Xk . One can enumerate as many elements of the sequence as

one wants by using storage for k elements of V , along with storage for the

coe¬cients of g, as follows:

(β0 , . . . , βk’1 ) ← (±0 , . . . , ±k’1 )

repeat

output β0

β ← ’ k’1 gj βj j=0

(β0 , . . . , βk’1 ) ← (β1 , . . . , βk’1 , β )

forever

Because of the structure of the above algorithm, linearly generated se-

quences are sometimes also called shift register sequences. Also observe

that if F is a ¬nite ¬eld, and V is ¬nite dimensional, the value stored in

the “register” (β0 , . . . , βk’1 ) must repeat at some point, from which it fol-

lows that the linearly generated sequence must be ultimately periodic (see

de¬nitions above Exercise 4.8). 2

Example 19.2. Linearly generated sequences can also arise in a natural

way, as this example and the next illustrate. Let E := F [X]/(f ), where

f ∈ F [X] is a monic polynomial of degree > 0, and let ± be an element

of E. Consider the sequence S := (1, ±, ±2 , · · · ) of powers of ±. For any

polynomial g = k gj Xj ∈ F [X], we have

j=0

k

gj ±j = g(±).

g S=

j=0

Now, if g(±) = 0, then clearly (Xi g) S = ±i g(±) = 0 for all i ≥ 0. Conversely,

if (Xi g) S = 0 for all i ≥ 0, then in particular, g(±) = 0. Thus, g is a

generating polynomial for S if and only if g(±) = 0. It follows that the

minimal polynomial φ of S is the same as the minimal polynomial of ± over

F , as de¬ned in §17.5. Furthermore, φ = 0, and the degree m of φ may be

characterized as the smallest positive integer m such that 1, ±, . . . , ±m are

linearly dependent; moreover, as E has dimension over F , we must have

m¤ . 2

Example 19.3. Let V be a vector space over F of dimension > 0, and let

„ : V ’ V be an F -linear map. Let β ∈ V , and consider the sequence S :=

(±0 , ±1 , . . .), where ±i = „ i (β); that is, ±0 = β, ±1 = „ (β), ±2 = „ („ (β)),

426 Linearly generated sequences and applications

k j ∈ F [X], we have

and so on. For any polynomial g = j=0 gj X

k

gj „ j (β),

g S=

j=0

and for any i ≥ 0, we have

k k

(Xi g) S = gj „ i+j (β) = „ i gj „ j (β) = „ i (g S).

j=0 j=0

Thus, if g S = 0, then clearly (Xi g) S = „ i (g S) = „ i (0) = 0 for all i ≥ 0.

Conversely, if (Xi g) S = 0 for all i ≥ 0, then in particular, g S = 0. Thus,

g is a generating polynomial for S if and only if g S = 0. The minimal

polynomial φ of S is non-zero and its degree m is at most ; indeed, m may be

characterized as the least non-negative integer such that β, „ (β), . . . , „ m (β)

are linearly dependent, and since V has dimension over F , we must have

m¤ .

The previous example can be seen as a special case of this one, by taking

V to be E, „ to be the ±-multiplication map on E, and setting β to 1. 2

The problem of computing the minimal polynomial of a linearly generated