m

(i) (i)

a(i)ˆst mod ni .

←

crt

ˆ ˆrs b

s=1

2. For each r, t = 1, . . . , m, apply the Chinese remainder theorem to

(1) (2) (k)

crt , crt , . . . , crt , obtaining an integer crt , which should be computed

ˆˆ ˆ

as a balanced remainder modulo n, so that n/2 ¤ crt < n/2.

3. Output (crt : r, t = 1, . . . , m).

Note that in Step 2, if our Chinese remainder algorithm happens to be

implemented to return an integer z with 0 ¤ z < n, we can easily get a

balanced remainder by just subtracting n from z if z ≥ n/2.

The correctness of the above algorithm has already been established. Let

us now analyze its running time. The running time of Steps 1a and 1b is

easily seen (see Exercise 3.23) to be O(m2 len(H )2 ). Under our assumption

about the cost of arithmetic modulo small primes, the cost of Step 1c is

O(m3 k), and since k = O(len(H )) = O(len(H) + len(m)), the cost of this

step is O(m3 (len(H) + len(m))). Finally, by Theorem 4.5, the cost of Step 2

is O(m2 len(H )2 ). Thus, the total running time of this algorithm is easily

calculated (discarding terms that are dominated by others) as

O(m2 len(H)2 + m3 len(H) + m3 len(m)).

Compared to (4.1), we have essentially replaced the term m3 len(H)2 by

m2 len(H)2 + m3 len(H). This is a signi¬cant improvement: for example,

66 Euclid™s algorithm

if len(H) ≈ m, then the running time of the original algorithm is O(m5 ),

while the running time of the modular algorithm is O(m4 ).

Exercise 4.6. Apply the ideas above to the problem of computing the

product of two polynomials whose coe¬cients are large integers. First, de-

termine the running time of the “obvious” algorithm for multiplying two

such polynomials, then design and analyze a “modular” algorithm.

4.5 Rational reconstruction and applications

We next state a theorem whose immediate utility may not be entirely ob-

vious, but we quickly follow up with several very neat applications. The

general problem we consider here, called rational reconstruction, is as

follows. Suppose that there is some rational number y that we would like to

ˆ

get our hands on, but the only information we have about y is the following:

ˆ

• First, suppose that we know that y may be expressed as r/t for

ˆ

integers r, t, with |r| ¤ r— and |t| ¤ t— ” we do not know r or t, but

we do know the bounds r— and t— .

• Second, suppose that we know integers y and n such that n is rela-

tively prime to t, and y = rt’1 mod n.

It turns out that if n is su¬ciently large relative to the bounds r— and t— ,

then we can virtually “pluck” y out of the extended Euclidean algorithm

ˆ

applied to n and y. Moreover, the restriction that n is relatively prime to

t is not really necessary; if we drop this restriction, then our assumption is

that r ≡ ty (mod n), or equivalently, r = sn + ty for some integer s.

Theorem 4.6. Let r— , t— , n, y be integers such that r— > 0, t— > 0, n ≥ 4r— t— ,

and 0 ¤ y < n. Suppose we run the extended Euclidean algorithm with

inputs a := n and b := y. Then, adopting the notation of Theorem 4.3, the

following hold:

(i) There exists a unique index i = 1, . . . , + 1 such that ri ¤ 2r— < ri’1 ;

note that ti = 0 for this i.

Let r := ri , s := si , and t := ti .

(ii) Furthermore, for any integers r, s, t such that

r = sn + ty, |r| ¤ r— , and 0 < |t| ¤ t— , (4.6)

we have

r = r ±, s = s ±, and t = t ±,

for some non-zero integer ±.

4.5 Rational reconstruction and applications 67

Proof. By hypothesis, 2r— < n = r0 . Moreover, since r0 , . . . , r , r +1 = 0

is a decreasing sequence, and 1 = |t1 |, |t2 |, . . . , |t +1 | is a non-decreasing

sequence, the ¬rst statement of the theorem is clear.

Now let i be de¬ned as in the ¬rst statement of the theorem. Also, let

r, s, t be as in (4.6).

From part (v) of Theorem 4.3 and the inequality 2r— < ri’1 , we have

n n

|ti | ¤ < —.

ri’1 2r

From the equalities ri = si n + ti y and r = sn + ty, we have the two congru-

ences:

r ≡ ty (mod n),

ri ≡ ti y (mod n).

Subtracting ti times the ¬rst from t times the second, we obtain

rti ≡ ri t (mod n).

This says that n divides rti ’ ri t. Using the bounds |r| ¤ r— and |ti | <

n/(2r— ), we see that |rti | < n/2, and using the bounds |ri | ¤ 2r— , |t| ¤ t— ,

and 4r— t— ¤ n, we see that |ri t| ¤ n/2. It follows that

|rti ’ ri t| ¤ |rti | + |ri t| < n/2 + n/2 = n.

Since n divides rti ’ ri t and |rti ’ ri t| < n, the only possibility is that

rti ’ ri t = 0. (4.7)

Now consider the two equations:

r = sn + ty

ri = si n + ti y.

Subtracting ti times the ¬rst from t times the second, and using the identity

(4.7), we obtain n(sti ’ si t) = 0, and hence

sti ’ si t = 0. (4.8)

From (4.8), we see that ti | si t, and since from part (iii) of Theorem 4.3,

we know that gcd(si , ti ) = 1, we must have ti | t. So t = ti ± for some ±, and

we must have ± = 0 since t = 0. Substituting ti ± for t in equations (4.7)

and (4.8) yields r = ri ± and s = si ±. That proves the second statement of

the theorem. 2

68 Euclid™s algorithm

4.5.1 Application: Chinese remaindering with errors

One interpretation of the Chinese remainder theorem is that if we “encode”

an integer z, with 0 ¤ z < n, as the sequence (a1 , . . . , ak ), where ai = z mod

ni for i = 1, . . . , k, then we can e¬ciently recover z from this encoding. Here,

of course, n = n1 · · · nk , and the integers n1 , . . . , nk are pairwise relatively

prime.

But now suppose that Alice encodes z as (a1 , . . . , ak ), and sends this

encoding to Bob; however, during the transmission of the encoding, some

(but hopefully not too many) of the values a1 , . . . , ak may be corrupted. The

question is, can Bob still e¬ciently recover the original z from its corrupted

encoding?

To make the problem more precise, suppose that the original, correct

encoding of z is (a1 , . . . , ak ), and the corrupted encoding is (˜1 , . . . , ak ). Let

a ˜

us de¬ne G ⊆ {1, . . . , k} to be the set of “good” positions i with ai = ai , ˜

and B ⊆ {1, . . . , k} to be the set of “bad” positions i with ai = ai . We shall

˜

assume that |B| ¤ , where is some speci¬ed parameter.

Of course, if Bob hopes to recover z, we need to build some redundancy

into the system; that is, we must require that 0 ¤ z ¤ Z for some Z that is

somewhat smaller than n. Now, if Bob knew the location of bad positions,

and if the product of the integers ni at the good positions exceeds Z, then

Bob could simply discard the errors, and reconstruct z by applying the

Chinese remainder theorem to the values ai and ni at the good positions.

However, in general, Bob will not know a priori the location of the bad

positions, and so this approach will not work.

Despite these apparent di¬culties, Theorem 4.6 may be used to solve the

problem quite easily, as follows. Let P be an upper bound on the product

of any of the integers n1 , . . . , nk (e.g., we could take P to be the product

of the largest ni ). Further, let us assume that n ≥ 4P 2 Z.

Now, suppose Bob obtains the corrupted encoding (˜1 , . . . , ak ). Here is

a ˜

what Bob does to recover z:

1. Apply the Chinese remainder theorem, obtaining an integer y, with

0 ¤ y < n and y ≡ ai (mod ni ) for i = 1, . . . , k.

˜

2. Run the extended Euclidean algorithm on a := n and b := y, and let

r , t be the values obtained from Theorem 4.6 applied with r— := ZP

and t— := P .

3. If t | r , output r /t ; otherwise, output “error.”

We claim that the above procedure outputs z, under our assumption that

the set B of bad positions is of size at most . To see this, let t := i∈B ni .