PROOF: Suppose we are given a polynomial-time-bounded Monte-Carlo TM Ml for a language L. We can construct a nondeterministic TM M2 for L with the same time bound. Whenever Mi examines a random bit for the first time, M2 chooses, nondeterministically, both possible values for that bit, and writes it on a tape of its own that simulates the random tape of Mi. M3 accepts whenever Mi accepts, and does not accept otherwise.

Suppose w is in L. Then since Mi has at least a 50% probability of accepting w, there must be some sequence of bits on its random tape that leads to acceptance of w. M2 will choose that sequence of bits, among others, and therefore also accepts when that choice is made. Thus, w is in L(M3). However, if w is not in L, then no sequence of random bits will make Mi accept, and therefore no sequence of choices makes M2 accept. Thus, w is not in L{M2). □

Figure 11.8 shows the relationship between the classes we have introduced and the other nearby classes.

Figure 11.8; Relationship of ZPP and PP to other classes

11.5 The Complexity of Primality Testing

In this section, we shall look at a particular problem: testing whether an integer is a prime. We begin with a motivating discussion concerning the way primes

and primaJity testing are essential ingredients in computer-security systems. We then show that the primes are in both AfP and co-J\fP. Finally, we discuss a randomized algorithm that shows the primes are in HP as well.

11,5.1 The Importance of Testing Primality

An integer p is prime if the only integers that divide p evenly are 1 and p itself. If an integer is not a prime, it is said to be composite. Every composite number can be written as a product of primes in a unique way, except for the order of the factors.

Example 11.20: The first few primes are 2, 3, 5, 7, 11, 13, and 17. The integer 504 is composite, and its prime factorization is 2 x 3 x 7. О

There are a number of techniques that enhance computer security, for which the most common methods in use today rely on the assumption that it is hard to factor numbers, that is, given a composite number, to find its prime factors. In particular, these schemes, based on what are called RSA codes (for R. Rivest, A. Shamir, and L, Adelman, the inventors of the technique), use integers of, say, 128 bits that are the product of two primes, each of about 64 bits. Here are two scenarios in which primes play an important part.

Public-Key Cryptography

You want to buy a book from an on-line bookseller. The seller asks for your credit-card number, but it is too risky to type the number into a form and have the form transmitted over phone fines or the Internet. The reason is that someone could be snooping on your line, or otherwise intercept packets as they travel over the Internet.

To avoid a snooper being able to read your card utunber, the seller sends your browser a key k, perhaps the 128-bit product of two primes that the sellers computer has generated just for this purpose. Your browser uses a function у = fk{x} that takes both the key к and the data x that you need to encrypt. The function /, which is part of the RSA scheme, may be generally known, including to potential snoopers, but it is believed that without knowing the factorization of k, the inverse function f such that x = fiy) cannot be computed in time that is less than exponential in the length of fc.

Thus, even if a snooper sees у and knows how / works, without first figuring out what к is and then factoring it, the snooper cannot recover x, which is in this case your credit-card number. On the other hand, the on-line seller, knowing the factorization of key к because they generated it in the first place, can easily apply f and recover x from y.

Public-Key Signatures

The original scenario for which RSA codes were developed is the following. You would like to be able to sign email so that people could easily determine

that the email was from you, and yet no one could forge your name to an email. For instance, you might wish to sign the message x - I promise to pay Sally Lee $10, but you dont want Sally to be able to create the signed message herself, or for a third party to create such a signed message without your knowledge.

To support these aims, you pick a key fc, whose prime factors only you know. You publish к widely, say on your Web site, so anyone can apply the function Д. to any message. If you want to sign the message x above and send it to Sally, you compute у = fk{x) and send у to Sally instead. Sally can get Д, your public key, from your Web site, and with it compute x = fk{y)- Thus, she knows that you have indeed promised to pay $10.

If you deny having sent the message y, Sally can argue before a judge that only you know the function , and it would be impossible for either her or any third party to have discovered that function. Thus, only you could have created y. This system rehes on the likely-but-unproven assumption that it is too hard to factor numbers that are the product of two large primes.

Requirements Regarding Complexity of Primality Testing

Both scenarios above are believed to work and to be secure, rn the sense that it really does take exponential time to factor the product of two large primes. The complexity theory we have studied here and in Chapter 10 enter into the study of security and cryptography in two ways:

1. The construction of pubhc keys requires that we be able to find large primes quickly. It is a basic fact of number theory that the probability of an n-bit number being a prime is on the order of 1/n. Thus, if we had a polynomial-time {in n, not in the value of the prime itself) way to test whether an n-bit number was prime, we could pick numbers at random, test them, and stop when we found one to be prime. That would give us a polynomial-time Las-Vegas algorithm for discovering primes, since the expected number of numbers we have to test before meeting a prime of 71 bits is about n. For instance, if we want 64-bit primes, we would have to test about 64 integers on the average, although by bad luck we could have to try indefinitely more than that. Unfortunately, there does not appear to be a guaranteed, polynomial-time test for primes, although there is a Monte-Carlo Algorithm that is polynomial-time, as we shall see in Section 11.5,4.

2. The security of RSA-based cryptography depends on there being no polynomial (in the number of bits of the key) way to factor in general, in particular no way to factor a number known to be the product of exactly two large primes. We would be very happy if we could show that the set of primes is an NP-complete language, or even that the set of composite numbers was NP-complete. For then, a polynomial factoring algorithm would prove V - ЯТ, since it would yield polynomial-time