Matthias Bauer bauer at
Mon Feb 14 12:21:21 CET 2000

> > Not true...It is possible to deterministically check to see if a number is
> > prime and the workload is FAR less than testing a primes up to the square
> > root.
> Got an algorithm?

author =       {S. Goldwasser and J. Kilian},
title =        {Almost all primes can be quickly certified},
pages =        {316--329},
booktitle =    STOC86,
publisher =    ACM,
address =      {Berkeley},
year =         1986


Francois Morain, ``Implementation of the Atkin-Goldwasser-Kilian
Primality Testing Algorithm,'' INRIA Research Report #911,
October 1988.

There's an implementation for Mathematica:

Have a nice day


More information about the Gnupg-devel mailing list