Hot News!

Recognition of when a large number is prime is important in several cryptographic protocols discussed in class (see Lecture 4 and Lecture 7). I remarked that large primes are obtained in practice by guessing a "random" large number, and checking probabilistically if the number is prime. So a computer routine would output that a certain 150 decimal digit number is prime with probability at least 1-2-20 (or whatever tolerance one is willing to accept, considering the running times of the program and the design and use of the algorithm requiring the prime).

Very, very recently a considerable change in this situation has occurred.

A deterministic polynomial-time test for primality has been found

by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena of the Indian Institute of Technology in Kanpur, India.

This is a major achievment. The paper, dated August 6, 2002, is available in pdf format at The paper is remarkably brief (9 pages) considering the difficult problem it solves. I would certainly expect you to be able to understand the introduction.

This has even gotten some mention in the press (for example, an article in the New York Times). Please note that RSA encryption is protected by the difficulty of factoring, not the difficulty of deciding whether a number is prime. Satisfactorily analyzing and proving the difficulty of factorization has still not been done.

Maintained by and last modified 8/9/2002.