Exercise 3.21. Let n1 , . . . , nk be positive integers. Show that

k k k

len(ni ) ’ k ¤ len ¤

ni len(ni ).

i=1 i=1 i=1

Exercise 3.22. Show that the product n of integers n1 , . . . , nk , with each

ni > 1, can be computed in time O(len(n)2 ). Do not assume that k is a

constant.

Exercise 3.23. Show that given integers n1 , . . . , nk , with each ni > 1, and

an integer z, where 0 ¤ z < n and n := i ni , we can compute the k integers

z mod ni , for i = 1, . . . , k, in time O(len(n)2 ).

Exercise 3.24. Consider the problem of computing n1/2 for a given non-

negative integer n.

(a) Using binary search, give an algorithm for this problem that runs in

48 Computing with large integers

time O(len(n)3 ). Your algorithm should discover the bits of n1/2

one at a time, from high- to low-order bit.

(b) Re¬ne your algorithm from part (a), so that it runs in time

O(len(n)2 ).

Exercise 3.25. Show how to convert (in both directions) between the base-

10 representation and our implementation™s internal representation of an

integer n in time O(len(n)2 ).

3.4 Computing in Zn

Let n > 1. For ± ∈ Zn , there exists a unique integer a ∈ {0, . . . , n ’ 1} such

that ± = [a]n ; we call this integer a the canonical representative of ±,

and denote it by rep(±). For computational purposes, we represent elements

of Zn by their canonical representatives.

Addition and subtraction in Zn can be performed in time O(len(n)):

given ±, β ∈ Zn , to compute rep(± + β), we simply compute the integer

sum rep(±) + rep(β), subtracting n if the result is greater than or equal

to n; similarly, to compute rep(± ’ β), we compute the integer di¬erence

rep(±) ’ rep(β), adding n if the result is negative. Multiplication in Zn can

be performed in time O(len(n)2 ): given ±, β ∈ Zn , we compute rep(± · β) as

rep(±) rep(β) mod n, using one integer multiplication and one division with

remainder.

A note on notation: “rep,” “mod,” and “[·]n .” In describ-

ing algorithms, as well as in other contexts, if ±, β are elements of

Zn , we may write, for example, γ ← ± + β or γ ← ±β, and it is

understood that elements of Zn are represented by their canonical

representatives as discussed above, and arithmetic on canonical rep-

resentatives is done modulo n. Thus, we have in mind a “strongly

typed” language for our pseudo-code that makes a clear distinction

between integers in the set {0, . . . , n ’ 1} and elements of Zn . If

a ∈ Z, we can convert a to an object ± ∈ Zn by writing ± ← [a]n ,

and if a ∈ {0, . . . , n ’ 1}, this type conversion is purely conceptual,

involving no actual computation. Conversely, if ± ∈ Zn , we can con-

vert ± to an object a ∈ {0, . . . , n ’ 1}, by writing a ← rep(±); again,

this type conversion is purely conceptual, and involves no actual

computation. It is perhaps also worthwhile to stress the distinction

between a mod n and [a]n ” the former denotes an element of the

set {0, . . . , n ’ 1}, while the latter denotes an element of Zn .

Another interesting problem is exponentiation in Zn : given ± ∈ Zn and

a non-negative integer e, compute ±e ∈ Zn . Perhaps the most obvious

way to do this is to iteratively multiply by ± a total of e times, requiring

3.4 Computing in Zn 49

time O(e len(n)2 ). A much faster algorithm, the repeated-squaring algo-

rithm, computes ±e using just O(len(e)) multiplications in Zn , thus taking

time O(len(e) len(n)2 ).

This method works as follows. Let e = (b ’1 · · · b0 )2 be the binary expan-

sion of e (where b0 is the low-order bit). For i = 0, . . . , , de¬ne ei := e/2i ;

the binary expansion of ei is ei = (b ’1 · · · bi )2 . Also de¬ne βi := ±ei for

i = 0, . . . , , so β = 1 and β0 = ±e . Then we have

ei = 2ei+1 + bi and βi = βi+1 · ±bi for i = 0, . . . , ’ 1.

2

This idea yields the following algorithm:

β ← [1]n

for i ← ’ 1 down to 0 do

β ← β2

if bi = 1 then β ← β · ±

output β

It is clear that when this algorithm terminates, we have β = ±e , and that

the running-time estimate is as claimed above. Indeed, the algorithm uses

squarings in Zn , and at most additional multiplications in Zn .

The following exercises develop some important e¬ciency improvements

to the basic repeated-squaring algorithm.

Exercise 3.26. The goal of this exercise is to develop a “2t -ary” variant of

the above repeated-squaring algorithm, in which the exponent is e¬ectively

treated as a number in base 2t , rather than in base 2.

(a) Show how to modify the repeated squaring so as to compute ±e using

+O(1) squarings in Zn , and an additional 2t + /t+O(1) multiplica-

tions in Zn . As above, ± ∈ Zn and len(e) = , while t is a parameter

that we are free to choose. Your algorithm should begin by building

t

a table of powers [1], ±, . . . , ±2 ’1 , and after that, it should process

the bits of e from left to right in blocks of length t (i.e., as base-2t

digits).

(b) Show that by appropriately choosing the parameter t, we can bound

the number of additional multiplications in Zn by O( / len( )). Thus,

from an asymptotic point of view, the cost of exponentiation is es-

sentially the cost of squarings in Zn .

(c) Improve your algorithm from part (a), so that it only uses + O(1)

squarings in Zn , and an additional 2t’1 + /t + O(1) multiplications

50 Computing with large integers

in Zn . Hint: build a table that contains only the odd powers of ±

t

among [1], ±, . . . , ±2 ’1 .

Exercise 3.27. Suppose we are given ±1 , . . . , ±k ∈ Zn , along with non-

negative integers e1 , . . . , ek , where len(ei ) ¤ for i = 1, . . . , k. Show how to

compute

e

e

β := ±11 · · · ±kk

using + O(1) squarings in Zn and an additional + 2k + O(1) multiplica-

tions in Zn . Your algorithm should work in two phases: in the ¬rst phase,

the algorithm uses just the values ±1 , . . . , ±k to build a table of all possible

products of subsets of ±1 , . . . , ±k ; in the second phase, the algorithm com-

putes β, using the exponents e1 , . . . , ek , and the table computed in the ¬rst

phase.

Exercise 3.28. Suppose that we are to compute ±e , where ± ∈ Zn , for

many -bit exponents e, but with ± ¬xed. Show that for any positive integer

parameter k, we can make a pre-computation (depending on ±, , and k)

that uses + O(1) squarings in Zn and 2k + O(1) multiplications in Zn , so

that after the pre-computation, we can compute ±e for any -bit exponent e

using just /k + O(1) squarings and /k + O(1) multiplications in Zn . Hint:

use the algorithm in the previous exercise.

Exercise 3.29. Let k be a constant, positive integer. Suppose we are given

±1 , . . . , ±k ∈ Zn , along with non-negative integers e1 , . . . , ek , where len(ei ) ¤

for i = 1, . . . , k. Show how to compute

e

e

β := ±11 · · · ±kk

using +O(1) squarings in Zn and an additional O( / len( )) multiplications

in Zn . Hint: develop a 2t -ary version of the algorithm in Exercise 3.27.

Exercise 3.30. Let m1 , . . . , mr be integers, each greater than 1, and let

m := m1 · · · mr . Also, for i = 1, . . . , r, de¬ne mi := m/mi . Given ± ∈ Zn ,

show how to compute all of the quantities

±m1 , . . . , ±mr

using a total of O(len(r) len(m)) multiplications in Zn . Hint: divide and

conquer.

Exercise 3.31. The repeated-squaring algorithm we have presented here

processes the bits of the exponent from left to right (i.e., from high order

to low order). Develop an algorithm for exponentiation in Zn with similar

complexity that processes the bits of the exponent from right to left.

3.5 Faster integer arithmetic (—) 51