mpz_nextprime

[Jonathan Leto]

Howdy,

2009/5/11 Selçuk Keskin <selcukkeskin at live.com>:
> 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.

Cheers,


[1] http://www.trnicely.net/misc/mpzspsp.html
[2] http://www.trnicely.net/misc/bpsw.html
[3] http://leto.net/x/2009/01/primes-primality-and-psuedopri.html
[4] http://github.com/leto/math--primality/tree/master
[5] http://search.cpan.org/dist/Math-GMPz/


-- 

Jonathan Leto
jonathan at leto.net
http://leto.net