RSA

[Matthias Bauer]

Hi,
> > 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?

@inproceedings{GoldwasserKi86,
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
}

And 

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

There's an implementation for Mathematica:

http://www.mathsource.com/MathSource22/Enhancements/NumberTheory/0200-956/PrimeQ.m

Have a nice day

Matthias