primality test
Hans Aberg
haberg at math.su.se
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
http://www.cse.iitk.ac.in/primality.pdf
in the GNU Bug-GMP list 2002/08/11.
http://mail.gnu.org/mailman/listinfo/bug-gmp
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