mpz_nextprime

[selcukkeskin at live.com]

What is it using as mathematics rules , formula, technique etc.?


--------------------------------------------------
From: "Jonathan Leto" <jonathan at leto.net>
Sent: Monday, May 11, 2009 9:45 PM
To: "Selçuk Keskin" <selcukkeskin at live.com>
Cc: <gmp-discuss at gmplib.org>; "Bob Kuo" <bobjkuo at gmail.com>
Subject: Re: mpz_nextprime

> 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
>