Projects page: Improving probable prime algorithms

Bob Kuo bobjkuo at
Sun Nov 1 10:51:17 CET 2009


I was reading over the projects page (
and noticed a blurb about improving the probable prime algorithm. For
this year's Google Summer of Code I implemented the BPSW primality
test in perl using the GMP library (code at and
and there is even a C implementation that we based our implementation
off of (page: code: which uses GMP as well.  The
BPSW primality test is essentially a combination of Miller-Rabin and
Lucas-Selfridge primality tests but no pseudoprime has been found for
all n < 10^15.  If you would like to have this type of algorithm in
GMP I would be more than happy to help in anyway I can.

Secondly, I think it would be useful if you exposed the Miller-Rabin
test directly, with the function allowing the programmer to specify
the base and the number n to be checked.



More information about the gmp-devel mailing list