330 CHAPTER 5 Analysis of Algorithms
(b) Suppose that cracking a public key cryptogram depends on finding the smallest 50-
digit prime. Suppose that a single execution mod of takes 0.01 nanoseconds (10-11
seconds)^3 and that the rest of the above program takes no time at all. Approximately
how long would it take, in years, to verify that a 50-digit number is prime?
(c) If n is a k digit prime number, approximately how many times does ShortenedPrimal-
ityTest execute the key operation? How much does this speed up our time from part
(b)?
(d) Show that ShortenedPrimalityTest correctly determines whether input integer n is
prime.
In fact, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena of the Indian Institute of Tech-
nology showed that primality can be tested in polynomial time in the number of digits
in n.
More recent work has been based not on testing primality but, rather, on factoring
large integers, which seems to be harder.3 This is sure to be an unrealistic assumption no matter how fast microprocessors get: With numbers of this size,
the amount of time to do one mod operation will almost certainly depend on the length of the number.