primality test

mgrogue at mgrogue at
Wed May 18 18:55:56 CEST 2005

> I need a deterministic test which decides wether a number is prime or
> not. Unlike the Miller-Rabin-Version which is used by GMP's
> mpz_probab_prime_p (mpz_t n, int reps), I need it really to be
> deterministic. Do you know examples, where Miller-Rabin fails? Which
> test do you use? 
> I read somewhere there is one test which has polynomical complexity.
> Has someone implemented this Agarwal-Kayal-Saxena Primality Test with
> GMP and is willing to share it? 
> Or is it better to use Elliptic Curve Primality Proving? Where do I
> obtain the algorithm or even source?
> Any help is appreciated! Thanks in advance, bye, Jens

Start at and look for your
answers there.  In short the tool you use to prove primality depends
upon the number you are trying to prove prime.  Search for AKS, ECPP,
and PFGW in the messages for more information.

More information about the gmp-discuss mailing list