The contribution of Pratt was to be the first to publish a proof that the certificate can be verified in polynomial time (thus proving that PRIMES is in NP).
--Anton ----- Original Message ----- From: "Richard Schroeppel" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Cc: "David Wagner" <[EMAIL PROTECTED]> Sent: Friday, March 07, 2003 5:06 PM Subject: prime proofs > Dave Wagner writes > > ... Here's a simple method, due to Pratt. ... > > People were doing this fourty years before Pratt's paper. > See, for example, Dick Lehmer's 1933 paper "Hunting Big Game > in the Theory of Numbers", where he describes proving primality > for a 19 digit divisor of 2^95+1. It's on my web page at > > http://www.cs.arizona.edu/~rcs/biggame4 > > Or see Math. Comp. in the early 1970s for examples with more > depth in the recursions. > > Rich Schroeppel [EMAIL PROTECTED] > > > --------------------------------------------------------------------- > The Cryptography Mailing List > Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED] > --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]