ROADMAP

References

* Description of PARI primality algorithms: http://www.math.u-bordeaux.fr/~belabas/pari/doc/faq.html

To be Done

* More user documentation, explain the general idea of the algorithm used

Hairy Details

* Math::GMPz implements all the hairy details of GMP

Other Possibilities

Already Done

* Port iBPSW from spec/bpsw/bpsw1.c

       is_prime($N) <==> iBPSW(N,1)

This is basically trial division, followed by a is_strong_pseudoprime(),
followed by a is_strong_lucas_pseudoprime()

There are many optimizations to made for small arguments

Main function: is_prime(), to replace Math::PARI::is_prime()

It may take optional arguments for power-users, but we want to have a really
simple function for people to call like this:

   is_prime($x) ? foo() : bar();

which "does what I mean."

** next_prime()

This function is merely a wrapper around is_prime(), which takes a starting
number and increments it until is_prime() returns true and then returns that
number.

This should only require a small number of tests, most of the work is in making the necessary components of is_prime().

* Port iMillerRabin from spec/bpsw/trn.c , this will be is_strong_pseudoprime()

* implement base b pseudoprime test, a.k.a n is in psp(b) this is is_pseudoprime()

* Port iStrongLucasSelfridge(mpz_t) from spec/bpsw/trn.c , this will be is_strong_lucas_pseudoprime()

References

* Description of PARI primality algorithms: http://www.math.u-bordeaux.fr/~belabas/pari/doc/faq.html