Level 1 \

Level 2

Figure 11.11: The recursive calls made by the algorithm of Theorem 11.26 form a tree of height and width at most n

Since the product of the children of any node is less than the value of the node itself, we see that the product of the values of nodes at any depth from the root is at most p. The work required at a node with value i, exclusive of work done in recursive calls, is at most a(log. г) for some constant a; the reason is that we determined this work to be on the order of the fourth power of the number of bits needed to represent that value in binary.

Thus, to get an upper bound on the work required by any one level, we must maximize the sum Xj-o(log.2(i!j))\ subject to the constraint that the product JiZ2 - - is at most p. Because the fourth power is convex, the maximum occurs when all of the value is in one of the ijs. If iy - p, and there are no other ijs, then the sum is o(log2P). That is at most an, since n is the number of bits in the binary representation of p, and therefore logj p is at most n.

4, If the qs are all prime, guess a value of x and check that x * ф 1 for any of the qjs. This test assures that x has degree p - 1 modulo p, since if it did not, then its degree would have to divide at least one (p-1)/qj, and we just verified that it did not. Note in justification that any x, raised to any power of its degree, must be 1. The exponentiations can be done by the efficient method described in Section 11.5.3. Thus, there are at most к exponentiations, which is surely no more than n exponentiations, and each one can be performed in O(n) time, giving us a total time of 0{n) for this step.

Lastly, we must verify that this nondeterministic algorithm is polynomial-time. Each of the steps except the recursive step (3) takes time at most 0{n) along any nondeterministic branch. While this recursion is complicated, we can visualize the recursive calls as a tree suggested by Fig. 11.11. At the root is the prime p of n bits that we want to verify. The children of the root are the qjs, which are the guessed factors of p - 1 that we must also verify are prunes. Below each qj are the guessed factors of qj - 1 that we must verify, and so on, until we get down to numbers of at most 2 bits, which are leaves of the tree.

Root level

Our conclusion is that the work required at each depth is at most O(n). Since there are at most n levels, 0{n) work suffices in any branch of the nondeterministic test for whether p is prime. □

Now we know that both the primes and their complement are in AfV. If either were NP-complete, then by Theorem 11.2 we would have a proof that ЛГГ - co-MT.

11.5.6 Exercises for Section 11.5

Exercise 11.5.1: Compute the following modulo 13:

a) in-9.

* b) 9-11. c) 5x8.

* d) 5/8. e) 5

Exercise 11.5.2: We claimed in Section 11.5.4 that for most values of x between 1 and 560, 1=° = 1 modulo 561. Pick some values of x and verify that equation. Be sure to express 560 in binary first, and then compute x modulo 561, for various values of j, to avoid doing 559 multiplications, as we discussed in Section 11.5.3.

Exercise 11.5.3: An integer x between 1 and p - 1 is said to be a quadratic residue modulo p if there is some integer у between 1 and p -1 such that y - x.

* a) What are the quadratic residues modulo 7? You may use the table of

Fig, 11.9 to help answer the question.

b) What are the quadratic residues modulo 13?

! c) Show that if p is a prime, then the number of quadratic residues modulo p is [p- l)/2; i.e., exactly half the nonzero integers modulo p are quadratic residues. Hint: Examine your data from parts (a) and (b). Do you see a pattern explaining why every quadratic residue is the square of two different numbers? Could one integer be the square of three different numbers when p is a prime?

11.6 Summary of Chapter 11

-f The Class co-MV: A language is said to be in co-MV if its complement is in UP. All languages in P are surely in co-MP, but it is likely that there are some languages in MP that are not in co-MP, and vice-versa. In particular, the NP-complete problems do not appear to be in co-MP.

f The Class PS: A language is said to be in PS (polynomial space) if it is accepted by a deterministic TM for which there is a polynomial p(n) such that on input of length n the TM never uses more than p{n) cells of its tape.

4- The Class fPS: We can also define acceptance by a nondeterministic TM whose tape-usage is limited by a polynomial function of its input length. The class of these languages is referred to as MVS. However, Savitchs theorem tells us that VS = MVS. In particular, a NTM with space bound p(n) can be simulated by a DTM using space р{п).

4- Randomized Algorithms and Thiring Machines: Many algorithms use randomness productively. On a real computer, a random-number generator is used to simulate coin-ffipping. A randomized Turing machine can achieve the same random behavior if it is given an additional tape on which a sequence of random bits is written.

-f The Class HP: A language is accepted in random polynomial time if there is a polynomial-time, randomized Turing machine that has at least 50% chance of accepting its input if that input is in the language. If the input is not in the language, then this TM never accepts. Such a TM or algorithm is called Monte-Carlo.

f The Class ZPV: A language is in the class of zero-error, probabilistic polynomial time if it is eiccepted by a randomized Turing machine that always gives the correct decision regarding membership in the language; this TM must run in expected polynomial time, although the worst case may be greater than any polynomial, Such a TM or algorithm is called Las Vegas.

♦ Relationships Among Language Classes: The class co-TlV is the set of complements of languages in RV. The following containments are known; V С ZW С {W n co-nV). Also, nV С MV and therefore со-Тг С co-MV.

f The Primes and MV: Both the primes and the complement of the language of primes - the composite numbers - are in MV. These facts make it unlikely that the primes or composite numbers are NP-complete. Since there are important cryptographic schemes based on primes, such a proof would have offered strong evidence of their security.

4- The Primes and RV: The composite numbers are in RV- The random-polynomial algorithm for testing composlteness is in common use to allow the generation of large primes, or at least large numbers that have an arbitrarily small chance of being composite.