Thus, the entire computation of x~ takes 0{n) time.

11.5.4 Random-Polynomial Primality Testing

We shall now discuss how to use randomized computation to find large prime numbers. More precisely, we shall show that the language of composite numbers is in PP. The method actually used to generate n-bit primes is to pick an n-bit number at random and apply the Monte-Carlo algorithm to recognize composite numbers some large number of times, say 50. If any test says that the number is composite, then we know it is not a prime. If all 50 fail to say that it is composite, there is no more than 2~° probability that it really is composite. Thus, we can fairly safely say that the number is prime and base our secure operation on that fact.

We shall not give the complete algorithm here, but rather discuss an idea that works except in a very small number of cases. Recall Fermats theorem tells us that if p is a prime, then ж-- modulo p is always 1, It is also a fact that if p is a composite number, and there is any x at all for which x~ modulo p is not 1, then for at least half the values of x in the range 1 to p - 1, we shall find # 1.

Thus, we shall use as our Monte-Carlo algorithm for the composite numbers:

1. Pick an X at random in the range 1 to p - 1.

2. Compute x modulo p. Note that if p is an n-bit number, then this calculation takes 0{n) time by the discussion at the end of Section 11.5.3.

3. If x~ Ф 1 modulo p, accept; x is composite. Otherwise, halt without accepting.

If j9 is prime, then x~ = 1, so we always halt without accepting; that is one part of the Monte-Carlo requirement, that if the input is not in the language, then we never accept. For almost all the composite numbers, at least half the values of X will have x ? 1, so we have at least 50% chance of acceptance on any one run of this algorithm; that is the other requirement for an algorithm to be Monte-Carlo.

What we have described so far would be a demonstration that the composite numbers are in PP, if it were not for the existence of a small number of composite numbers с that have x- = 1 modulo c, for the majority of x in the range 1 to с - 1, in particular for those x that do not share a common prime factor with c. These numbers, called Carmickael numbers, require us to do another, more complex test (which we do not describe here) to detect that they are composite. The smallest Carmichael number is 561, That is, one can show x° = 1 modulo 561 for all x that are not divisible by 3, 11, or 17, even though 56l = 3xllxl7is evidently composite. Thus, we shall claim, but without a complete proof, that:

Theorem 11.24: The set of composite numbers is in PP. □

Can We Factor in Random Polynomial Time?

Notice tiiat the algorithm of Section 11.5.4 may tell us that a number is composite, but does not tell us how to factor the composite number. It is believed that there is no way to factor numbers, even using randomness, that takes only polynomial time, or even expected polynomial time. If that assumption were incorrect, then the applications that we discussed in Section 11.5.1 would be insecure and could not be used.

11.5.5 Nondeterministic Primality Tests

Let us now take up another interesting and significant result about testing primality: that the language of primes is in AfP П co-AfP. Therefore the language of composite numbers, the complement of the primes, is also in MP П co-AfP-The significance of this fact is that it is unlikely to be the case that the primes or the composite numbers are NP-complete, for if either were true then we would have the unexpected equality MP = co-MP.

One part is easy: the composite numbers are obviously in MP, so the primes are in co-MP. We prove that fact first.

Theorem 11.25 : The set of composite numbers is in MP.

PROOF; The nondeterministic, polynomial-time algorithm for the composite numbers is:

1. Given cm n-bit number p, guess a factor / of at most n bits. Do not choose f = 1 or f - p, however. This part is nondeterministic, with all possible values of / being guessed along some sequence of choices. However, the time taken by any sequence of choices is 0{n).

2. Divide p by /, and check that the remainder is 0. Accept if so. This part is deterministic and can be carried out Ln time O(n) on a multitape TM.

If p is composite, then it must have at least one factor / other than 1 and p. The NTM, since it guesses all possible numbers of up to n bits, will in some branch guess /. That branch leads to acceptance. Conversely, acceptance by the NTM implies that a factor of p other than 1 or p itself has been found. Thus, the NTM described accepts the language consisting of all and only the composite numbers. □

Recognizing the primes with a NTM is harder. While we were able to guess a reason (a factor) that a number is not a prime, and then check that our guess is correct, how do we guess a reason a number is a prime? The nondeterministic, polynomial-time algorithm is based on the fact (asserted but not proved) that if p is a prime, then there is a number x between 1 and p - 1

Notice that if p is a prime, then p - 1 is neuer a prime, except in the uninteresting case p = 3, The reason is that all primes but 2 are odd.

that has degree p-l- For instance, we observed in Example 11.23 that for the prime p = 7, the numbers 3 and 5 both have degree 6.

While we could guess a number x easily, using the nondeterministic capability of a NTM, it is not immediately obvious how one then checks that x has degree p-l. The reason is that if we apply the definition of degree directly, we need to check that none oi x,x,... ,x~ are 1. To do so requires that we perform p - 3 multiphcations, and that requires time at least 2 , if p is an n-bit number.

A better strategy is to make use of another fact that we assert but do not prove: the degree of x modulo a prime p is a divisor of p - 1. Thus, if we knew the prime factors of p - 1, it would be sufficient to dieck that xP ф 1 for each prime factor q oi p - 1. If none of these powers of x is equal to 1, then the degree of x must be p - 1. The number of these tests is 0{n), so we can perform them all in a polynomial-time algorithm. Of course we cannot factor P - 1 into primes easily. However, nondeterministically we can guess the prime factors of p - 1, and:

a) Check that their product is indeed p -1-

b) Check that each is a prime, using the nondeterministic, polynomial-time algorithm that we have been designing, recursively.

The details of the algorithm, and the proof that it is nondeterministic, polynomial-time, are in the proof of the theorem below.

Theorem 11.26: The set of primes is in nV.

PROOF: Given a number p of n bits, we do the following. First, if n is no more than 2 (i.e., p is 1, 2, or 3), answer the question directly; 2 and 3 are primes, while 1 is not. Otherwise:

1. Guess a list of factors (§1,2, )<?fc), whose binary representations total at most 2n bits, and none of which has more than n - 1 bits. It is permitted for the same prime to appear several times, since p-l may have a factor that is a prime raised to a power greater than 1; e.g., if p = 13, then the prime factors of p - 1 = 12 are in the list (2,2,3). This part is nondeterministic, but each branch takes 0(n) time.

2. Multiply the qs together, and verify that their product is p-1. This part takes no more than 0[n) time and is deterministic.

3. If their product is p - 1, recursively verify that each is a prime, using the algorithm being described here.