The answers to this HW must be submitted by a word-processed hard copy.
Hand written answers are not acceptable!


Homework on PRIMES is in P, due Tues, 4/15/08 at the start of class.

Read article:  "PRIMES is in P", M. Agrawal, N. Kayal, N. Saxena, 
Annals of Mathematics, 160 (2004), 781 - 793.

1.a.  What is the year of this paper, solving PRIMES?

1.b. What is the earliest date given in this paper for partial
solutions to this problem?

2. For your answer to #1b, why was that partial solution not
satisfactory?

3. Regarding the pseudocode given, p. 784, 

"Algorithm for Primality Testing",

Step 4 is only relevant for numbers less than a certain value.
Modify the algorithm with a conditional statement that avoids 
computing step #4 if it is not appropriate.

a. What is the pseudocode for this step?

b. Where should this step be inserted?

4. The main result is 

"Theorem 4.1.  The algorithm above returns PRIME if and only if n is prime."

a. One direction is trivial.  Make a full statement of the trivial result
in the form of "If ..., then ....".

b. Give a full statement of the converse "If ..., then ..." that is
nontrivial to prove.

5. Does this result imply that "P = NP"? 
Briefly, justify your answer.