for which an error occurred. Then by construction, tz ≡ 0 (mod ni ) and

ty ≡ 0 (mod ni ), and so (18.3) holds for this i. Thus, (18.2) holds, from

which it follows that the values r , t obtained from Theorem 18.7 satisfy

r r tz

== = z.

t t t

One easily checks that both the procedures to encode and decode a value z

run in time O(k 2 ). The above scheme is an example of an error correcting

code called a Reed“Solomon code. Note that we are completely free to

choose the ¬nite ¬eld F however we want, just so long as it is big enough.

An attractive choice in some settings is to choose F = Z2 [Y]/(f ), where

f ∈ Z2 [Y] is an irreducible polynomial; with this choice, elements of F may

be encoded as bit strings of length deg(f ).

18.5 Rational function reconstruction and applications 413

One can combine the above error correction technique with the idea of

secret sharing (see §18.4.2) to obtain a secret sharing scheme that is robust,

even in the presence of erroneous (as opposed to just missing) shares. More

precisely, Alice can share a secret s ∈ F among parties P1 , . . . , Pm , in such

a way that (1) if less than k parties pool their shares, Alice™s secret remains

well hidden, and (2) from any k shares, we can correctly reconstruct Alice™s

secret, provided at most of the shares are incorrect, and k ≥ 2 + k .

To do this, Alice chooses z1 , . . . , zk ’1 ∈ F at random, sets z0 := s, and

k ’1 i

i=0 zi X ∈ F [X], and computes the ith share as ai := z(bi ), for

z :=

i = 1, . . . , m. Here, we assume that the bi are distinct, non-zero elements of

F . Now, just as in §18.4.2, as long as less than k parties pool their shares,

Alice™s secret remains well hidden; however, provided k ≥ 2 + k , we can

correctly and e¬ciently reconstruct Alice™s secret given any k values ai , as

˜

long as at most of the ai di¬er from the corresponding value of ai .

˜

18.5.2 Application: recovering rational functions from their

reversed formal Laurent series

We now discuss the polynomial analog of the application in §4.5.2. This is an

entirely straightforward translation of the results in §4.5.2, but we shall see

in the next chapter that this problem has its own interesting applications.

Suppose Alice knows a rational function z = s/t ∈ F (X), where s and t

are polynomials with deg(s) < deg(t), and tells Bob some of the high-order

coe¬cients of the reversed formal Laurent series (see §17.7) representing z

in F ((X’1 )). We shall show that if deg(t) ¤ M and Bob is given the bound

M on deg(t), along with the high-order 2M coe¬cients of z, then Bob can

determine z, expressed as a rational function in lowest terms.

∞ ’i

So suppose that z = s/t = i=1 zi X , and that Alice tells Bob the

coe¬cients z1 , . . . , z2M . Equivalently, Alice gives Bob the polynomial

y := z1 X2M ’1 + · · · + z2M ’1 X + z2M = zX2M .

Let us de¬ne n := X2M , so that y = zn . Here is Bob™s algorithm for

recovering z:

1. Run the extended Euclidean algorithm on inputs a := n and b := y,

and let s , t be as in Theorem 18.7, using r— := M and t— := M .

2. Output s , t .

We claim that z = ’s /t . To prove this, observe that since y = zn =

(ns)/t , if we set r := (ns) mod t, then we have

r = sn ’ ty, deg(r) < r— , 0 ¤ deg(t) ¤ t— , and r— + t— ¤ deg(n).

414 Polynomial arithmetic and applications

It follows that the polynomials s , t from Theorem 18.7 satisfy s = s ± and

’t = t ± for some non-zero polynomial ±. Thus, s /t = ’s/t, which proves

the claim.

We may further observe that since the extended Euclidean algorithm guar-

antees that gcd(s , t ) = 1, not only do we obtain z, but we obtain z expressed

as a fraction in lowest terms.

It is clear that this algorithm takes O(M 2 ) operations in F .

The following exercises are the polynomial analogs of Exercises 4.7, 4.9,

and 4.10.

Exercise 18.11. Let F be a ¬eld. Show that given polynomials s, t ∈

F [X] and integer k, with deg(s) < deg(t) and k > 0, we can compute the

kth coe¬cient in the reversed formal Laurent series representing s/t using

O(len(k) len(t)2 ) operations in F .

Exercise 18.12. Let F be a ¬eld. Let z ∈ F ((X’1 )) be a reversed formal

Laurent series whose coe¬cient sequence is ultimately periodic. Show that

z ∈ F (X).

Exercise 18.13. Let F be a ¬eld. Let z = s/t, where s, t ∈ F [X], deg(s) <

deg(t), and gcd(s, t) = 1. Let d > 1 be an integer.

(a) Show that if F is ¬nite, there exist integers k, k such that 0 ¤ k < k

and sdk ≡ sdk (mod t).

(b) Show that for integers k, k with 0 ¤ k < k , the sequence of coef-

¬cients of the reversed Laurent series representing z is (k, k ’ k)-

periodic if and only if sdk ≡ sdk (mod t).

(c) Show that if F is ¬nite and X t, then the reversed Laurent series rep-

resenting z is purely periodic with period equal to the multiplicative

order of [X]t ∈ (F [X]/(t))— .

(d) More generally, show that if F is ¬nite and t = Xk t , with X t ,

then the reversed Laurent series representing z is ultimately periodic

with pre-period k and period equal to the multiplicative order of

[X]t ∈ (F [X]/(t ))— .

18.5.3 Applications to symbolic algebra

Rational function reconstruction has applications in symbolic algebra, anal-

ogous to those discussed in §4.5.3. In that section, we discussed the appli-

cation of solving systems of linear equations over the integers using rational

18.6 Faster polynomial arithmetic (—) 415

reconstruction. In exactly the same way, one can use rational function re-

construction to solve systems of linear equations over F [X]”the solution to

such a system of equations will be a vector whose entries are elements of

F (X), the ¬eld of rational functions.

18.6 Faster polynomial arithmetic (—)

The algorithms discussed in §3.5 for faster integer arithmetic are easily

adapted to polynomials over a ring. Throughout this section, R denotes

a non-trivial ring.

Exercise 18.14. State and re-work the analog of Exercise 3.32 for R[X].

Your algorithm should multiply two polynomials over R of length at most

using O( log2 3 ) operations in R.

It is in fact possible to multiply polynomials over R of length at most

using O( len( ) len(len( ))) operations in R ” we shall develop some of the

ideas that lead to such a result below in Exercises 18.23“18.26 (see also the

discussion in §18.7).

In Exercises 18.15“18.21 below, assume that we have an algorithm that

multiplies two polynomials over R of length at most using at most M ( )

operations in R, where M is a well-behaved complexity function (as de¬ned

in §3.5).

Exercise 18.15. State and re-work the analog of Exercise 3.34 for R[X].

Exercise 18.16. This problem is the analog of Exercise 3.35 for R[X]. Let

us ¬rst de¬ne the notion of a “¬‚oating point” reversed formal Laurent series

z , which is represented as a pair (a, e), where a ∈ R[X] and e ∈ Z ” the

ˆ

value of z is aXe ∈ R((X’1 )), and we call len(a) the precision of z . We

ˆ ˆ

’1 )) if z has precision

say that z is a length k approximation of z ∈ R((X

ˆ ˆ

’1 )) with deg( ) ¤ ’k, which is the same

k and z = (1 + )z for ∈ R((X

ˆ

as saying that the high-order k coe¬cients of z and z are equal. Show

ˆ

how to compute ” given monic b ∈ R[X] and positive integer k ” a length

k approximation of 1/b ∈ R((X’1 )) using O(M (k)) operations in R. Hint:

using Newton iteration, show how to go from a length t approximation

of 1/b to a length 2t approximation, making use of just the high-order 2t

coe¬cients of b, and using O(M (t)) operations in R.

Exercise 18.17. State and re-work the analog of Exercise 3.36 for R[X].

Assume that b is a monic polynomial.

Exercise 18.18. State and re-work the analog of Exercise 3.37 for R[X].

416 Polynomial arithmetic and applications

Conclude that a polynomial of length can be evaluated at points using