Size of inputs and cost of arithmetic computations

Because we shall be working with large integers, we need to adjust how we think about the size of an input and about the cost of elementary arithmetic operations.

In this chapter, a "large input" typically means an input containing "large integers" rather than an input containing "many integers" (as for sorting). Thus, we shall measure the size of an input in terms of the *number of bits* required to represent that input, not just the number of integers in the input. An algorithm with integer inputs *a*_{1}, *a*_{2}, . . . , *a _{k}* is a

The notion of one integer being divisible by another is a central one in the theory of numbers. The notation* d | a* (read "*d* **divides**** ***a*") means that *a* = *kd* for some integer* k*. Every integer divides 0. If *a* > 0 and *d* *| a*, then *|d| *|a|. If *d* *|* *a*, then we also say that *a* is a * multiple* of

If *d* *|* *a* and *d* 0, we say that *d* is a **divisor**** **of* a*. Note that* d* *|* *a* if and only if -*d* *|* *a*, so that no generality is lost by defining the divisors to be nonnegative, with the understanding that the negative of any divisor of *a *also divides *a.* A divisor of an integer *a* is at least 1 but not greater than *|a|*. For example, the divisors of 24 are 1, 2, 3, 4, 6, 8, 12, and 24.

Every integer* a *is divisible by the* trivial divisors* 1 and

An integer *a* > 1 whose only divisors are the trivial divisors 1 and *a* is said to be a* prime *number (or, more simply, a

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,... .

Exercise 33.1-1 asks you to prove that there are infinitely many primes. An integer *a* > 1 that is not prime is said to be a* composite *number (or, more simply, a

Given an integer *n*, the integers can be partitioned into those that are multiples of *n *and those that are not multiples of* n*. Much number theory is based upon a refinement of this partition obtained by classifying the nonmultiples of* n* according to their remainders when divided by *n. *The following theorem is the basis for this refinement. The proof of this theorem will not be given here (see, for example, Niven and Zuckerman [151]).

The value* q *= *a*/*n* is the * quotient* of the division. The value

a=a/nn+ (amodn)

amodn=a-a/nn.

Given a well-defined notion of the remainder of one integer when divided by another, it is convenient to provide special notation to indicate equality of remainders. If (*a* mod *n*) = (*b* mod* n*), we write* a * *b *(mod *n*) and say that *a* is **equivalent**** **to* b,* modulo* n*. In other words,* a* *b *(mod* n*) if *a* and* b* have the same remainder when divided by* n. *Equivalently, *a * *b* (mod *n*) if and only if *n* *|* (*b* - *a*). We write *a* *b* (mod *n*) if *a* is not equivalent to *b*, modulo *n*. For example, 61 6 (mod 11). Also, -13 22 2 (mod 5).

The integers can be divided into *n *equivalence classes according to their remainders modulo *n*. The **equivalence class modulo n**** **containing an integer *a* is

[a]= {_{n}a+kn:k} .Z

Z= {[_{n }a]: 0_{n }an- 1}.

Z= {0, 1,...,_{n}n- 1},

If *d* is a divisor of *a* and also a divisor of *b*, then *d *is a* common divisor *of

An important property of common divisors is that

d|aandd|bimpliesd| (a+b) andd| (a-b).

d|aandd|bimpliesd| (ax+by)

for any integers *x *and *y*. Also, if *a* *| **b*, then either *|a| * *|b|* or *b* = 0, which implies that

a|bandb|aimpliesa=b.

The * greatest common divisor* of two integers

The following are elementary properties of the gcd function:

gcd(a,b) = gcd(b,a),

gcd(a,b) = gcd(-a,b),

gcd(a,b) = gcd(|a| ,|b|),

gcd(a,0) =|a|,

gcd(a,ka) =|a| for anykZ.

amods=a-qs

=a-q(ax+by)

=a(1 -qx) +b(-qy),

For any integers *a* and *b*, if *d* *| *a* and *d* *| *b* then *d* *| gcd(*a, b*) .*

For all integers *a* and *b* and any nonnegative integer *n*,

gcd(an, bn) =ngcd(a, b).

For all positive integers *n, a*, and *b*, if *n* *| *ab* and gcd(*a, n*) = 1, then *n* *| *b*.

* Proof *The proof is left as Exercise 33.1-4.

Two integers *a, b* are said to be **relatively prime**** **if their only common divisor is 1, that is, if gcd(*a, b*) = 1. For example, 8 and 15 are relatively prime, since the divisors of 8 are 1, 2, 4, and 8, while the divisors of 15 are 1, 3, 5, and 15. The following theorem states that if two integers are each relatively prime to an integer *p*, then their product is relatively prime to *p*.

For any integers *a, b*, and *p*, if gcd(*a, p*) = 1 and gcd(*b, p*) = 1, then gcd(*ab*, *p*) = 1.

* Proof *It follows from Theorem 33.2 that there exist integers

ax+py= 1,

bx'+py'= 1.

Multiplying these equations and rearranging, we have

ab(xx') + p(ybx' + y'ax + pyy') = 1.

We say that integers *n*_{1}, *n*_{2}, . . ., *n _{k}* are

An elementary but important fact about divisibility by primes is the following.

For all primes *p *and all integers *a, b,* if *p | *ab*, then *p | *a* or *p* *| *b*.*

A consequence of Theorem 33.7 is that an integer has a unique factorization into primes.

A composite integer *a* can be written in exactly one way as a product of the form

where the *p _{i} *are prime,

* Proof *The proof is left Exercise 33.1-10.

As an example, the number 6000 can be uniquely factored as 2^{4.}3^{.}5^{3}.

Prove that if *a* | *b* and *b* | *c*, then *a* | *c*.

Prove that if *p *is prime and 0 < *k* < *p*, then gcd (*k*, *p*) = 1.

Prove that if *p* is prime and 0 <* k* < *p*, then . Conclude that for all integers *a*, *b*, and primes *p*,

(a+b)^{p}a+^{p}b(mod^{p}p).

Prove that if *a* and *b *are any integers such that *a* *| *b* and *b* > 0, then*

(xmodb) moda=xmoda

for any *x*. Prove, under the same assumptions, that

xy(modb) impliesxy(moda)

For any integer *k* > 0, we say that an integer *n* is a * kth power* if there exists an integer

Prove equations (33.8)--(33.12).

Show that the gcd operator is associative. That is, prove that for all integers *a*, *b*, and *c*,

gcd(a, gcd(b,c)) = gcd(gcd(a,b),c) .

Give an efficient algorithm to convert a given *-*bit (binary) integer to a decimal representation. Argue that if multiplication or division of integers whose length is at most * takes time *M*(*), then binary-to-decimal conversion can be performed in time (*M*(*) lg *). (*Hint*: Use a divide-and-conquer approach, obtaining the top and bottom halves of the result with separate recursions.)

In this section, we use Euclid's algorithm to compute the greatest common divisor of two integers efficiently. The analysis of running time brings up a surprising connection with the Fibonacci numbers, which yield a worst-case input for Euclid's algorithm.

Euclid's algorithm for computing greatest common divisors is based on the following theorem.

For any nonnegative integer *a* and any positive integer *b*,

gcd(a,b) = gcd(b,amodb) .

gcd(a,b) | gcd(b,amodb).

gcd (b,amodb) | gcd(a,b).

Using equation (33.7) to combine equations (33.16) and (33.17) completes the proof.

EUCLID (a,b)

1ifb= 0

2then returna

3else returnEUCLID(b,amodb)

As an example of the running of EUCLID, consider the computation of gcd (30,21):

EUCLID(30, 21) = EUCLID(21, 9)

= EUCLID(9, 3)

= EUCLID(3, 0)

= 3 .

In this computation, there are three recursive invocations of EUCLID.

b+ (amodb) =b+ (a-a/bb)

a,

since *a* > *b* > 0 implies *a*/*b* 1. Thus,

ab+ (amodb)

F+ 1 +_{k }F_{k}

=F+2 ._{k}

The following theorem is an immediate corollary of this lemma.

For any integer *k* 1, if *a* > *b* 0 and *b* < *F _{k}*+1, then the invocation EUCLID (

gcd(F+1,_{k}F) = gcd(_{k}F, (_{k}F+1 mod_{k}F))_{k}

= gcd(F,_{k}F-1) ._{k}

Thus, Euclid(*F _{k}*+1,

d= gcd(a,b) =ax+by.

a b/abd x y

-------------------------

99 78 1 3 -11 14

78 21 3 3 3 -11

21 15 1 3 -2 3

15 6 2 3 1 -2

6 3 2 3 0 1

3 0 -- 3 1 0

EXTENDED-EUCLID(a,b)

1fb= 0

2then return(a, 1, 0)

3 (d',x',y')EXTENDED-EUCLID(b,amodb)

4 (d,x,y) (d',y',x'-a/by')

5return(d,x,y)

Figure 33.1 illustrates the execution of EXTENDED-EUCLID with the computation of gcd(99,78).

d' =bx' + (amodb)y' .

d=bx'+ (a-a/bb)y'

=ay' +b(x' -a/by') .

Prove that equations (33.13)--(33.14) imply equation (33.15).

Compute the values (*d, x, y*) that are output by the invocation EXTENDED-EUCLID(899, 493).

Prove that for all integers *a, k*, and *n*,

gcd(a, n) = gcd(a+kn, n).

What does EXTENDED-EUCLID(*F _{k }*+ 1,

Define the gcd function for more than two arguments by the recursive equation gcd(*a*_{0}, *a*_{l}, . . . , * _{n}*) = gcd(

Define lcm(*a*_{1}, *a*_{2}, . . . , *a _{n}*) to be the

Informally, we can think of modular arithmetic as arithmetic as usual over the integers, except that if we are working modulo *n*, then every result *x* is replaced by the element of {0, 1, . . . , *n* - 1} that is equivalent to *x*, modulo *n* (that is, *x* is replaced by *x* mod *n*). This informal model is sufficient if we stick to the operations of addition, subtraction, and multiplication. A more formal model for modular arithmetic, which we now give, is best described within the framework of group theory.

A * group* (

1. **Closure:** For all *a, b * *S*, we have *a* *b* *S*.

2. **Identity:** There is an element *e * S* such that *e* *a* = *a* *e* = *a* for all *a* *S*.*

3. **Associativity:** For all *a, b, c ** S*, we have (*a* *b*) *c* = *a* (*b* c).

4. **Inverses:** For each *a* *S*, there exists a unique element *b* *S* such that *a* *b* = *b* *a* = *e*.

As an example, consider the familiar group (**Z**, +) of the integers **Z** under the operation of addition: 0 is the identity, and the inverse of *a* is -*a*. If a group (*S*, ) satisfies the **commutative law***a* *b* = *b* *a* for all *a, b* *S*, then it is an * abelian group.* If a group (

a+ba'_{ + b'}(modn) ,

aba'_{b'}(modn) .

+0 1 2 3 4 5_{6 }_{15 }1 2 4 7 8 11 13 14

-------------------- -------------------------------------

0 0 1 2 3 4 5 1 1 2 4 7 8 11 13 14

1 0 2 3 4 5 0 2 2 4 8 14 1 7 11 13

2 0 3 4 5 0 1 4 4 8 1 13 2 14 7 11

3 0 4 5 0 1 2 7 7 14 13 4 11 2 1 8

4 0 5 0 1 2 3 8 8 1 2 11 4 13 14 7

5 5 0 1 2 3 4 11 11 7 14 2 13 1 8 4

13 13 11 7 1 14 8 4 2

14 14 13 11 8 7 4 2 1

(a) (b)

Thus, we define addition and multiplication modulo *n*, denoted +* _{n}* and

[a]+_{n}[_{n}b]= [_{n }a+b],_{n }

[a]nn[b]n= [ab]_{n}.

Using this definition of addition modulo *n*, we define the * additive group modulo n* as (

The system (**Z*** _{n,}* +

* Proof *Associativity and commutativity of +

([a]+_{n}[_{n}b]) +_{n}[_{n}c]= [(_{n }a+b) +c]_{n}

= [a+ (b+c)]_{n}

= [a]+_{n}([_{n}b]+_{n}[_{n}c]),_{n}

[a]+_{n}[_{n}b]= [_{n }a+b]_{n}

= [b+a]_{n}

= [b]+_{n}[_{n}a]_{n }.

Using the definition of multiplication modulo *n*, we define the* multiplicative group modulo n* as . The elements of this group are the set of elements in

The system is a finite abelian group.

ax+ny= 1

ax1 (modn).

axb(modn) ,

[a]_{n }[_{n}x]= [_{n }b]._{n }

The size of is denoted (*n*). This function, known as * Euler's phi function*, satisfies the equation

(p) =p- 1.

If *n* is composite, then (*n*) < *n* - 1.

If (*S, *) is a group, *S*' *S*, and (*S*', ) is also a group, then (*S*', ) is said to be a * subgroup* of (

* Proof *The proof is left as Exercise 33.3-2.

The following theorem provides an extremely useful constraint on the size of a subgroup.

If (*S*, ) is a finite group and (*S*, ) is a subgroup of (*S*, ), then |*S**'*| is a divisor of |*S|. *

*A *subgroup* S*' of a group *S* is said to be a * proper* subgroup if

If *S*' is a proper subgroup of a finite group *S*, then |*S*'*| * |*S|/2. *

For example, if we take *a* = 2 in the group *Z*_{6}, the sequence *a*^{(1)}, *a*^{(2)}, . . . is

2, 4, 0, 2, 4, 0, 2, 4, 0,... .

a= {a^{(k)}:k1}.

We say that *a* * generates* the subgroup

a^{(i) }a^{(j)}=a^{(i+j)},

*a* is closed and therefore, by Theorem 33.14, *a* is a subgroup of *S*. For example, in **Z**_{6},we have

0 = {0} ,

1 = {0, 1, 2, 3, 4, 5} ,

2 = {0, 2, 4} .

1 = {1} ,

2 = {1, 2, 4} ,

3 = {1, 2, 3, 4, 5, 6} .

The* order* of

If (*S*, ) is a finite group with identity *e*, then for all *a * S*,*

a^{(|S|)}= e.

* Proof *Lagrange's theorem implies that ord(

Show that if *p* is prime and *e* is a positive integer, then

(p) =^{e}p1^{e-}(p- 1) .

List all of the subgroups of **Z**_{9} and of .

We now consider the problem of finding solutions to the equation

axb(modn),

For any positive integers *a* and *n*, if *d* = gcd(*a, n*), then

a=d= {0,d, 2d,..., ((n/d)- l)d},

|a| =n/d .

The equation *ax ** b *(mod *n*) is solvable for the unknown *x* if and only if gcd(*a, n*) *| *b*. *

x_{0 }= x'(b/d) mod n.

**Proof**** **Since *ax*' *d* (mod *n*), we have

ax_{0}ax'(b/d) (modn)

d(b/d) (modn)

b(modn) ,

and thus *x*_{0} is a solution to *ax ** b (mod n*).

MODULAR-LINEAR-EQUATION-SOLVER(a,b,n)

1 (d,x',y') EXTENDED-EUCLID(a,n)

2ifd | b

3thenx_{0}x'(b/d) mod n

4fori0tod- 1

5doprint (x_{0}+ i(n/d)) modn

6elseprint "no solutions"

The procedure MODULAR-LINEAR-EQUATION-SOLVER works as follows. Line 1 computes *d* = gcd(*a, n*) as well as two values *x*'*' and *y*'*' such that *d = ax*' + ny*'*, demonstrating that *x*'*' is a solution to the equation *ax*' ** d* (mod *n*). If *d* does not divide *b*, then the equation *ax ** b* (mod *n*) has no solution, by Corollary 33.21. Line 2 checks if *d ** b*; if not, line 6 reports that there are no solutions. Otherwise, line 3 computes a solution *x*_{0} to equation (33.22), in accordance with Theorem 33.23. Given one solution, Theorem 33.24 states that the other *d* - 1 solutions can be obtained by adding multiples of (*n/d*), modulo *n*. The **for** loop of lines 4-5 prints out all *d* solutions, beginning with *x*_{0} and spaced (*n/d*) apart, modulo *n*.

The following corollaries of Theorem 33.24 give specializations of particular interest.

For any *n* > 1, if gcd(*a,n*) = 1, then the equation *ax ** b *(mod* n*) has a unique solution modulo *n*.

For any *n > *1, if gcd(*a, n*) = 1, then the equation

ax1 (modn)

has a unique solution, modulo *n*. Otherwise, it has no solution.

gcd(a, n) = 1 = ax + ny

implies *ax ** *1 (mod* n*). Thus, (*a*^{-1}* *mod* n*) can be computed efficiently using EXTENDED-EUCLID.

Find all solutions to the equation 35*x* 10 (mod 50).

Consider the following change to line 3 of MODULAR-LINEAR-EQUATiON-SOLVER:

3thenx_{0}x'(b/d) mod (n/d)

Will this work? Explain why or why not.

Let *f*(*x*)* ** f*_{0}* + f _{1}x + + f_{t}x + . . . + f_{t}x^{t} *(mod

Around A.D. 100, the Chinese mathematician solved the problem of finding those integers *x* that leave remainders 2, 3, and 2 when divided by 3, 5, and 7 respectively. One such solution is *x* = 23; all solutions are of the form 23 + 105*k* for arbitrary integers *k*. The "Chinese remainder theorem" provides a correspondence between a system of equations modulo a set of pairwise relatively prime moduli (for example, 3, 5, and 7) and an equation modulo their product (for example, 105).

a (a_{l}, a_{2}, . . . , a_{k),}

a_{i}= a mod n_{i}

a(a_{l},a_{2, . . . , }a) ,_{k}

b(b_{1},b_{2}, . . . ,b_{k}) ,

(a+ b) modn((a_{l}+b_{l}) modn_{1}, . . . , (a+_{k}b) mod_{k}n) ,_{k}

(a- b) modn((a_{l}-b_{l}) modn_{l}, . . . , (a-_{k}b) mod_{k}n) ,_{k}

(ab) modn_{ (a}1_{b}1_{ mod n}l_{, . . . , a}k_{b}k_{ mod n}k_{) .}

c=_{i}m(_{i}m_{j}^{-l}_{ }modn)_{i}

for *i = *1, 2, . . . , *k*, we have

a(a_{l}c_{1}+a_{2}c_{2}+ . . . +a) (mod_{k}c_{k}n) .

c(0, 0, . . . , 0, 1, 0, . . . , 0) ,_{i }

The following corollaries will be used later in this chapter.

xa(mod_{i }n),_{i}

for *i* = 1, 2, . . . , *k*, has a unique solution modulo *n* for the unknown *x*.

xa(modn)_{i}

for *i* = 1, 2, . . . , *k* if and only if

xa(modn) .

As an example of the Chinese remainder theorem, suppose we are given the two equations

a2 (mod 5) ,

a3 (mod 13) ,

c_{1 }= 13(2 mod 5) = 26 ,

c_{2 }= 5(8 mod 13) = 40 ,

a2^{.}26 + 3 40 (mod 65)

52 + 120 (mod 65)

42 (mod 65) .

0 1 2 3 4 5 6 7 8 9 10 11 12

------------------------------- ---------------------

0 0 40 15 55 30 5 45 20 60 35 10 50 25

1 26 1 41 16 56 31 6 46 21 61 36 11 51

2 52 27 2 42 17 57 32 7 47 22 62 37 12

3 13 53 28 3 43 18 58 33 8 48 23 63 38

4 39 14 54 29 4 44 19 59 34 9 49 24 64

See Figure 33.3 for an illustration of the Chinese remainder theorem, modulo 65.

Find all solutions to the equations *x* 4 (mod 5) and *x* 5 (mod 11).

Find all integers *x* that leave remainders 1, 2, 3, 4, 5 when divided by 2, 3, 4, 5, 6, respectively.

Argue that, under the definitions of Theorem 33.27, if gcd(*a, n*) = 1, then

Just as it is natural to consider the multiples of a given element *a*, modulo *n*, it is often natural to consider the sequence of powers of *a*, modulo *n*, where :

a^{0},a^{1},a^{2},a^{3},... ,

i0 1 2 3 4 5 6 7 8 9 10 11 ...

---------------------------------------------------

3mod 7 1 3 2 6 4 5 1 3 2 6 4 5 ...^{i}

whereas the powers of 2 modulo 7 are

i0 1 2 3 4 5 6 7 8 9 10 11 ...

---------------------------------------------------

2mod 7 1 2 4 1 2 4 1 2 4 1 2 4 ...^{i}

* Proof *By equation (33.21), (

If , then every element in is a power of *g*, modulo *n*, and we say that g is a **primitive root*** *or a * generator* of . For example, 3 is a primitive root, modulo 7. If possesses a primitive root, we say that the group is

If *g* is a primitive root of and *a* is any element of , then there exists a *z* such that *g ^{z}*

If *g* is a primitive root of , then the equation *g ^{x}*

* Proof *Suppose first that

g^{x }g(^{y+k}n)^{(mod n)}

g(^{y}g^{}(n)^{)}k^{(mod n)}

gl^{y}(mod^{k }n)

g(mod^{y }n).

If *p* is an odd prime and *e* 1, then the equation

x^{2}1 (modp)^{e}

has only two solutions, namely *x* = 1 and *x* = - 1.

(g^{ind}_{n,g}^{(x)})^{2}g^{ind}_{n,g}^{(l) }(modn) .

2 ind(_{n,g}x) 0 (mod (n)) .

A number *x* is a * nontrivial square root of 1, modulo n*, if it satisfies the equation

If there exists a nontrivial square root of 1, modulo *n*, then *n* is composite.

A frequently occurring operation in number-theoretic computations is raising one number to a power modulo another number, also known as * modular exponentiation*. More precisely, we would like an efficient way to compute

MODULAR-EXPONENTIATION(a,b,n)

1c0

2d1

3 letb,_{k}b-1, . . . ,_{k}b_{0}be the binary representation ofb

4forikdownto0

5doc2c

6d(dd) modn

7ifb= 1_{i}

8thencc+ 1

9d(da) modn

10returnd

i9 8 7 6 5 4 3 2 1 0

-------------------------------------------------

b1 0 0 0 1 1 0 0 0 0_{i }

c1 2 4 8 17 35 70 140 280 560

d7 49 157 526 160 241 298 166 67 1

a^{2c }modn= (a)^{c}^{2}modn,

a+l mod^{2c}n=a. (a)2 mod^{c}n,

A public-key cryptosystem can be used to encrypt messages sent between two communicating parties so that an eavesdropper who overhears the encrypted messages will not be able to decode them. A public-key cryptosystem also enables a party to append an unforgeable "digital signature" to the end of an electronic message. Such a signature is the electronic version of a handwritten signature on a paper document. It can be easily checked by anyone, forged by no one, yet loses its validity if any bit of the message is altered. It therefore provides authentication of both the identity of the signer and the contents of the signed message. It is the perfect tool for electronically signed business contracts, electronic checks, electronic purchase orders, and other electronic communications that must be authenticated.

In a public-key cryptosystem, each participant has both a * public key* and a

M=S(_{A}P(_{A}M)) ,

M=P(_{A}S_{A}(M))

Bob obtains Alice's public key *P _{A}* (from a public directory or directly from Alice).

Bob computes the **ciphertext***C* = *P _{A}*(

Alice computes her **digital signature*** * for the message* M*' using her secret key *S _{A}* and the equation

Alice sends the message/signature pair (*M**',*) to Bob.

An important property of a digital signature is that it is verifiable by anyone who has access to the signer's public key. A signed message can be verified by one party and then passed on to other parties who can also verify the signature. For example, the message might be an electronic check from Alice to Bob. After Bob verifies Alice's signature on the check, he can give the check to his bank, who can then also verify the signature and effect the appropriate funds transfer.

2. Compute *n* by the equation *n* = *pq*.

5. Publish the pair *P* = (*e, n*,) as his * RSA public key*.

6. Keep secret the pair *S* = (*d, n*) as his * RSA secret key*.

P(M) =M(mod^{e}n) .

The transformation of a ciphertext *C* associated with a secret key *S* = (*d, n*) is

S(C) =C(mod^{d}n) .

* Proof *From equations (33.39) and (33.40), we have that for any

P(S(M))= S(P(M))= M(mod^{ed}n).

Since *e* and *d* are multiplicative inverses modulo (*n*) = (*p* - 1)(*q* - 1),

ed= 1 +k(p- 1)(q- 1)

for some integer *k*. But then, if (mod *p*), we have (using Theorem 33.31)

M^{ed}M(M- 1)^{p}(^{k}q- 1) (modp)

M(1)(^{k}q- 1) (modp)

M(modp).

Also, *M ^{ed}*

M^{ed}M(modp)

M^{ed}M(modq)

for all *M*. Thus, by Corollary 33.29 to the Chinese remainder theorem,

M^{ed}M(modn)

A similar hybrid approach is often used to make digital signatures efficiently. In this approach, RSA is combined with a public **one-way hash function***h*--a function that is easy to compute but for which it is computationally infeasible to find two messages *M* and *M*'* such that *h*(*M*) = *h*(*M*'*). The value *h(M)* is a short (say, 128-bit) "fingerprint" of the message *M*. If Alice wishes to sign a message *M*, she first applies *h* to *M* to obtain the fingerprint *h*(*M*), which she then signs with her secret key. She sends (*M, S _{A}*(

Finally, we note that the use of * certificates* makes distributing public keys much easier. For example, assume there is a "trusted authority"

Prove that RSA is multiplicative in the sense that

PA(M1)PA(M2)PA(M1M2)(mod n) .

In this section, we consider the problem of finding large primes. We begin with a discussion of the density of primes, proceed to examine a plausible (but incomplete) approach to primality testing, and then present an effective randomized primality test due to Miller and Rabin.

For many applications (such as cryptography), we need to find large "random" primes. Fortunately, large primes are not too rare, so that it is not too time-consuming to test random integers of the appropriate size until a prime is found. The * prime distribution function* (

One simple approach to the problem of testing for primality is * trial division*. We try dividing

We now consider a method for primality testing that "almost works" and in fact is good enough for many practical applications. A refinement of this method that removes the small defect will be presented later. Let denote the nonzero elements of** Z*** _{n}*:

We say that *n* is a * base-a pseudoprime* if

a1 1 (mod^{n - }n).

The following procedure pretends in this manner to be checking the primality of *n*. It uses the procedure MODULAR-EXPONENTIATION from Section 33.6. The input *n *is assumed to be an integer larger than 2.

Unfortunately, we cannot eliminate all the errors by simply checking equation (33.42) for a second base number, say *a* = 3, because there are composite integers *n* that satisfy equation (33.42) for* all* . These integers are known as * Carmichael numbers*. The first three Carmichael numbers are 561, 1105, and 1729. Carmichael numbers are extremely rare; there are, for example, only 255 of them less than 100,000,000. Exercise 33.8-2 helps explain why they are so rare.

We next show how to improve our primality test so that it won't be fooled by Carmichael numbers.

The Miller-Rabin primality test overcomes the problems of the simple test PSEUDOPRIME with two modifications:

It tries several randomly chosen base values *a* instead of just one base value.

The pseudocode for the Miller-Rabin primality test follows. The input *n* > 2 is the odd number to be tested for primality, and *s* is the number of randomly chosen base values from to be tried. The code uses the random-number generator RANDOM from Section 8.3: RANDOM(1, *n* - 1) returns a randomly chosen integer *a* satisfying 1 *a* *n* - 1. The code uses an auxiliary procedure WITNESS such that WITNESS(*a, n*) is TRUE if and only if *a* is a "witness" to the compositeness of *n*--that is, if it is possible using *a* to prove (in a manner that we shall see) that *n* is composite. The test WITNESS(*a, n*) is similar to, but more effective than, the test

WITNESS(a,n)

1 letb,_{k}b,...,_{k-1}b_{0}n -_{ be the binary representation of }1

2d1

3forikdownto0

4doxd

5d(dd) modn

6ifd= 1 andx1 andxn- 1

7then returnTRUE

8ifbi= 1

9thend(da) modn

10ifd1

11then returnTRUE

12returnFALSE

This completes our proof of the correctness of WITNESS. If the invocation WITNESS(*a, n*) outputs TRUE, then *n* is surely composite, and a proof that *n* is composite can be easily determined from *a* and *n*. We now examine the Miller-Rabin primality test based on the use of WITNESS.

If MILLER-RABIN outputs PRIME, then there is a small chance that it has made an error. Unlike PSEUDOPRIME, however, the chance of error does not depend on *n*; there are no bad inputs for this procedure. Rather, it depends on the size of *s* and the "luck of the draw" in choosing base values *a*. Also, since each test is more stringent than a simple check of equation (33.42), we can expect on general principles that the error rate should be small for randomly chosen integers *n*. The following theorem presents a more precise argument.

*Case 1*: There exists an such that

x- 1 1 (mod^{n }n).

(p -1)p- 1 |^{e }p- 1.^{e }

Define *t* and *u* so that *n *- 1 = 2* ^{t}u*, where

â = a^{u}, a^{2u}, a^{22u}, . . . , a^{2tu}^{ ,}

wv(modn_{1}) ,

w1 (modn_{2}) .

w^{2ju}-1 (modn_{1}) ,

w^{2ju}1 (modn_{2}) .

Together with Corollary 33.29, these equations imply that

and so *w* *B*. Since , we have that . Thus, . We conclude that *B* is a proper subgroup of .

In either case, we see that the number of witnesses to the compositeness of *n* is at least (*n* - 1)/2.

It is possible to strengthen Euler's theorem slightly to the form

Prove that (*n*) | (*n*). A composite number *n* is a Carmichael number if (*n*) |*n* - 1. The smallest Carmichael number is 561 = 3 11 17; here, (*n*) = 1cm(2, 10, 16) = 80, which divides 560. Prove that Carmichael numbers must be both "square-free" (not divisible by the square of any prime) and the product of at least three primes. For this reason, they are not very common.

Suppose we have an integer *n* that we wish to * factor*, that is, to decompose into a product of primes. The primality test of the preceding section would tell us that

Trial division by all integers up to *B* is guaranteed to factor completely any number up to *B*^{2}. For the same amount of work, the following procedure will factor any number up to *B*^{4} (unless we're unlucky). Since the procedure is only a heuristic, neither its running time nor its success is guaranteed, although the procedure is very effective in practice.

POLLARD-RHO(n)

1i1

2x_{1}RANDOM(0,n- 1)

3yx_{1}

4k2

5whileTRUE

6doii+ l

8dgcd(y-x,_{i}n)

9ifd1 anddn

10thenprintd

11ifi=k

12thenyx_{i}

13k2k

is used on line 7 to produce the next value of *x _{i }*in the infinite sequence

x_{1},x_{2},x_{3},x_{4},...;

x_{1},x_{2},x_{4},x_{8},x_{16},... .

We analyze the behavior of this procedure by studying how long it takes a random sequence modulo *n* to repeat a value. Since **Z*** _{n}* is finite, and since each value in the sequence (33.49) depends only on the previous value, the sequence (33.49) eventually repeats itself. Once we reach an

for all *i*. Furthermore, it follows from the Chinese remainder theorem that

(xmodn) modp=xmodp,

Referring to the execution history shown in Figure 33.7(a), when does POLLARD-RHO print the factor 73 of 1387?

On most computers, the operations of subtraction, testing the parity (odd or even) of a binary integer, and halving can be performed more quickly than computing remainders. This problem investigates the **binary gcd**** *** algorithm*, which avoids the remainder computations used in Euclid's algorithm.

* a. *Prove that if

**b.*** *Prove that if *a* is odd and *b* is even, then gcd(*a, b*) = gcd(*a*, *b*/2).

* c. *Prove that if

33-2 Analysis of bit operations in Euclid's algorithm

* a.* Show that using the ordinary "paper and pencil" algorithm for long division--dividing

33-3 Three algorithms for Fibonacci numbers

This problem compares the efficiency of three methods for computing the *n*th Fibonacci number F* _{n}*, given

* b. *Show how to compute

Let *p* be an odd prime. A number is a **quadratic residue*** *if the equation x^{2} = *a* (mod *p*) has a solution for the unknown *x*.

**a***. *Show that there are exactly (*p* - 1)/2 quadratic residues, modulo *p*.

* b. *If

* c. *Prove that if

The randomized primality-testing algorithm presented here is due to Miller [147] and Rabin [166]; it is the fastest randomized primality-testing algorithm known, to within constant factors. The proof of Theorem 33.39 is a slight adaptation of one suggested by Bach [15]. A proof of a stronger result for MILLER-RABIN was given by Monier[148, 149]. Randomization appears to be necessary to obtain a polynomial-time primality-testing algorithm. The fastest deterministic primality-testing algorithm known is the Cohen-Lenstra version [45] of the primality test by Adleman, Pomerance, and Rumely [3]. When testing a number *n* of length lg(*n* + 1) for primality, it runs in (lg *n*)* ^{O}*(1g 1g 1g

The concept of a public-key cryptosystem is due to Diffie and Hellman [54]. The RSA cryptosystem was proposed in 1977 by Rivest, Shamir, and Adleman [169]. Since then, the field of cryptography has blossomed. In particular, many new techniques have been developed for proving cryptosystems to be secure. For example, Goldwasser and Micali [86] show that randomization can be an effective tool in the design of secure public-key encryption schemes. For signature schemes, Goldwasser, Micali, and Rivest [88] present a digital-signature scheme for which every conceivable type of forgery is provably as difficult as factoring. Recently, Goldwasser, Micali, and Rackoff [87] introduced a class of "zero-knowledge" encryption schemes for which it can be proven (under certain reasonable assumptions) that no party learns more than he is supposed to learn from a communication.

The best algorithms for factoring large numbers have a running time that grows roughly exponentially with the square root of the length of the number *n* to be factored. The quadratic-sieve factoring algorithm, due to Pomerance [158], is perhaps the most efficient such algorithm in general for large inputs. Although it is difficult to give a rigorous analysis of this algorithm, under reasonable assumptions we can derive a running-time estimate of *L*(*n*)^{1+o(1)}, where . The elliptic-curve method due to Lenstra [137] may be more effective for some inputs than the quadratic-sieve method, since, like Pollard's rho method, it can find a small prime factor *p* quite quickly. With this method, the time to find *p* is estimated to be .