prime proofs

[Anton Stiglic]

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" <rcs at CS.Arizona.EDU>
To: <cryptography at wasabisystems.com>
Cc: "David Wagner" <daw at mozart.cs.berkeley.edu>
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    rcs at cs.arizona.edu
>
>
> ---------------------------------------------------------------------
> The Cryptography Mailing List
> Unsubscribe by sending "unsubscribe cryptography" to
majordomo at wasabisystems.com
>


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com