ńņš. 122 |

c ā lc(r)

d ā r/c, s ā s/c, t ā t/c // make monic

output d, s, t

Theorem 18.5. The extended Euclidean algorithm for polynomials uses

O(len(a) len(b)) operations in F .

Proof. Exercise. 2

18.4 Computing modular inverses and Chinese remaindering

In this and the remaining sections of this chapter, we explore various appli-

cations of Euclidā™s algorithm for polynomials. Most of these applications are

analogous to their integer counterparts, although there are some diļ¬erences

to watch for. Throughout this section, F denotes a ļ¬eld.

We begin with the obvious application of the extended Euclidean algo-

rithm for polynomials to the problem of computing multiplicative inverses

in F [X]/(n), where n ā F [X] with := deg(n) > 0.

Given y ā F [X] with deg(y) < , using O( 2 ) operations in F , we can

determine if y is relatively prime to n, and if so, compute y ā’1 mod n as

follows. We run the extended Euclidean algorithm on inputs a := n and

b := y, obtaining polynomials d, s, t such that d = gcd(n, y) and ns + yt = d.

If d = 1, then y does not have a multiplicative inverse modulo n. Otherwise,

if d = 1, then t is a multiplicative inverse of y modulo n. Moreover, by

Theorem 18.4, and the discussion immediately following, deg(t) < , and so

t = y ā’1 mod n.

406 Polynomial arithmetic and applications

If the polynomial n is irreducible, then F [X]/(n) is a ļ¬eld, and the ex-

tended Euclidean algorithm, together with the basic algorithms for addition,

subtraction, and multiplication modulo n, yield eļ¬cient algorithms for per-

forming addition, subtraction, multiplication and division in the extension

ļ¬eld F [X]/(n).

We also observe that the Chinese remainder theorem for polynomials

(Theorem 17.17) can be made computationally eļ¬ective as well:

Theorem 18.6. Given polynomials n1 , . . . , nk ā F [X] and a1 , . . . , ak ā F [X],

where n1 , . . . , nk are pairwise relatively prime, and where deg(ni ) > 0 and

deg(ai ) < deg(ni ) for i = 1, . . . , k, we can compute the polynomial z ā F [X],

such that deg(z) < deg(n) and z ā” ai (mod ni ) for i = 1, . . . , k, where

n := i ni , using O(len(n)2 ) operations in F .

Proof. Exercise (just use the formulas in the proof of Theorem 2.8, which

are repeated below the statement of Theorem 17.17). 2

18.4.1 Chinese remaindering and polynomial interpolation

We remind the reader of the discussion following Theorem 17.17, where the

point was made that when ni = (X ā’ bi ) for i = 1, . . . , k, then the Chinese

remainder theorem for polynomials reduces to Lagrange interpolation. Thus,

Theorem 18.6 says that given distinct elements b1 , . . . , bk ā F , along with

elements a1 , . . . , ak ā F , we can compute the unique polynomial z ā F [X] of

degree less than k such that

z(bi ) = ai (i = 1, . . . , k),

using O(k 2 ) operations in F .

It is perhaps worth noting that we could also solve the polynomial interpo-

lation problem using Gaussian elimination, by inverting the corresponding

Vandermonde matrix. However, this algorithm would use O(k 3 ) operations

in F . This is a speciļ¬c instance of a more general phenomenon: there are

many computational problems involving polynomials over ļ¬elds that can be

solved using Gaussian elimination, but which can be solved more eļ¬ciently

using more specialized algorithmic techniques.

Exercise 18.7. State and re-work the polynomial analog of Exercises 4.3

and 4.4. In the special case of polynomial interpolation, this algorithm is

called Newton interpolation.

18.4 Computing modular inverses and Chinese remaindering 407

18.4.2 Mutual independence and secret sharing

ā¤k

As we also saw in the discussion following Theorem 17.17, for

and ļ¬xed and distinct b1 , . . . , b ā F , the āmulti-point evaluationā map

Ļ : F [X]<k ā’ F Ć— that sends a polynomial z ā F [X] of degree less than k to

(z(b1 ), . . . , z(b )) ā F Ć— is a surjective F -linear map.

If F is a ļ¬nite ļ¬eld, then this has the following probabilistic interpreta-

tion: if the coeļ¬cient vector (z0 , . . . , zkā’1 ) of z is a random variable, uni-

formly distributed over F Ć—k , then the random variable (z(b1 ), . . . , z(b )) is

uniformly distributed over F Ć— (see part (a) of Exercise 8.22). Put another

way, the collection {z(b) : b ā F } of random variables is -wise independent,

where each individual z(b) is uniformly distributed over F . Clearly, given

z and b, we can eļ¬ciently compute the value of z(b), so this construction

gives us a nice way to build eļ¬ectively constructible, -wise independent

collections of random variables for any , thus generalizing the construc-

tions in Example 6.17 and Exercise 6.16 of pairwise and 3-wise independent

collections.

As a particular application of this idea, we describe a simple secret shar-

ing scheme. Suppose Alice wants to share a secret among some number

m of parties, call them P1 , . . . , Pm , in such a way that if less than k parties

share their individual secret shares with one another, then Aliceā™s secret is

still well hidden, while any subset of k parties can reconstruct Aliceā™s secret.

She can do this as follows. Suppose her secret s is (or can be encoded as)

an element of a ļ¬nite ļ¬eld F , and that b0 , b1 , . . . , bm are some ļ¬xed, distinct

elements of F , where b0 = 0. This presumes, of course, that |F | ā„ m + 1. To

share her secret s, Alice chooses z1 , . . . , zkā’1 ā F at random, and sets z0 :=

s. Let z ā F [X] be the polynomial whose coeļ¬cient vector is (z0 , . . . , zkā’1 );

that is,

kā’1

zi Xi .

z=

i=0

For i = 1, . . . , m, Alice gives party Pi its share

ai := z(bi ).

For the purposes of analysis, it is convenient to deļ¬ne

a0 := z(b0 ) = z(0) = z0 = s.

Clearly, if any k parties pool their shares, they can reconstruct Aliceā™s

secret by interpolating a polynomial of degree less than k at k points ā” the

constant term of this polynomial is equal to Aliceā™s secret s.

408 Polynomial arithmetic and applications

It remains to show that Aliceā™s secret remains well hidden provided less

than k parties pool their shares. To do this, ļ¬rst assume that Aliceā™s secret

s is uniformly distributed over F , independently of z1 , . . . , zkā’1 (we will

relax this assumption below). With this assumption, z0 , z1 , . . . , zkā’1 are

independently and uniformly distributed over F . Now consider any subset

of k ā’ 1 parties; to simplify notation, assume the parties are P1 , . . . , Pkā’1 .

Then the random variables a0 , a1 , . . . , akā’1 are mutually independent. The

variables a1 , . . . , akā’1 are of course the shares of P1 , . . . , Pkā’1 , while a0 is

equal to Aliceā™s secret (the fact that a0 has two interpretations, one as the

value of z at a point, and one as a coeļ¬cient of z, plays a crucial role

in the analysis). Because of mutual independence, the distribution of a0 ,

conditioned on ļ¬xed values of the shares a1 , . . . , akā’1 , is still uniform over

F , and so even by pooling their shares, these k ā’ 1 parties would have

no better chance of guessing Aliceā™s secret than they would have without

pooling their shares.

Continuing the analysis of the previous paragraph, consider the condi-

tional probability distribution in which we condition on the event that a0 = s

for some speciļ¬c, ļ¬xed value of s ā F . Because the z0 , z1 , . . . , zkā’1 were ini-

tially independently and uniformly distributed over F , and because z0 = a0 ,

in this conditional probability distribution, we have z0 = s and z1 , . . . , zkā’1

are independently and uniformly distributed over F . So this conditional

probability distribution perfectly models the secret sharing algorithm per-

formed by Alice for a speciļ¬c secret s, without presuming that s is drawn

from any particular distribution. Moreover, because the a0 , a1 , . . . , akā’1

were initially independently and uniformly distributed over F , when we con-

dition on the event a0 = s, the variables a1 , . . . , akā’1 are still independently

and uniformly distributed over F .

The argument in the previous two paragraphs shows that

for any ļ¬xed secret s, the shares a1 , . . . , am are (k ā’1)-wise in-

dependent, with each individual share ai uniformly distributed

over F .

This property ensures that Aliceā™s secret is perfectly hidden, provided that

less than k parties pool their shares: for any secret s, these parties just see

a bunch of random values in F , with no particular bias that would give any

hint whatsoever as to the actual value of s.

ńņš. 122 |