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]
