Jonathan Leto jonathan at
Mon May 11 20:45:44 CEST 2009


2009/5/11 Selçuk Keskin <selcukkeskin at>:
> Hi,
> i'm studying on prime numbers with using GMP library. i'm searching how
> mpz_nextprime(rop,op) is running. Which technique this is using?
> And Does this function give wrong number as prime? Is there anybody to help
> me for my that problem?

The mpz_nextprime()  and mpz_probab_prime_p() functions use a
probabilistic Miller-Rabin algorithm, which can indeed return
composite numbers, as detailed by Thomas R. Nicely [1] in his
research. He has very well documented source code [2] that implements
many advanced primality methods that you can use that do not have any
known counter-examples (although they most probably *do* exist). See
[3] for a introduction to these ideas.

In a related note, I am mentoring a student (Bob Kuo) in the Google
Summer of Code 2009 for Math::Primality [4], a Perl 5 CPAN module
which will implement is_prime() for arbitrary precision integers with
the BPSW primality test. This module with use GMP via the Math::GMPz
module [5], which provides a  full interface to the mpz_* functions.
Currently is_strong_pseudoprime() is implemented, which is half of the
BPSW test. The BPSW test is basically asserting that a number is both
a strong pseudoprime and a strong lucas pseudoprime.




Jonathan Leto
jonathan at

More information about the gmp-discuss mailing list