Proven Primes

[Anton Stiglic]

> I thought that finding them was the hard part, and verifying one once
found
> was relatively easy.  I used the probable prime test in the Java
BigInteger
> package.  It sounds like, from some of the list traffic, that there are
> better tests.

Chapter 4 of the HAC gives a good introduction to all of this.

http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf

There are probabilistic primality tests (e.g. Miller-Rabin), there are
primality
proving algorithms (e.g. Jacoby Sum Test, ECPP), some of which give a
certificate
of primality that can be verified using a different algorithm. Some of the
tests work
on integers of special forms (e.g. Mersenne numbers), others work on all
integers.
There are also algorithms that generate integers that are guaranteed to be
prime
(e.g. Maurer's algorithm),  these are not tests...

--Anton


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