primality test

Hans Aberg haberg at
Wed May 18 18:38:43 CEST 2005

At 09:20 -0700 2005/05/18, Jens Hillenbach wrote:

>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

I mentioned this
in the GNU Bug-GMP list 2002/08/11.

I guess there there are two problems: This is a mathematical proof, 
and there is a way to go in order to produce a practical, efficient 
computer algorithm from it. And second, there is a problem finding 
someone willing to implement it. Probably there are experts in this 
area. Perhaps there is some newsgroup, where people would know.
   Hans Aberg

More information about the gmp-discuss mailing list