|
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 foundThis is a major achievment. The paper, dated August 6, 2002, is available in pdf format at http://www.cse.iitk.ac.in/primality.pdf. 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. |