Re. mpz_probab_prime_p() failures

Alan McFarlane alan.mcfarlane at
Mon Dec 5 02:38:00 CET 2005

Thanks for the link, ideal...

In respect of your comments, I'm actually looking for odd composites and as
such mpz_probab_prime_p returning a 1 could be potentially damaging to the
final outcome.

The algorithm I use, unfortunately tests *every* odd composite and I know of
no way to improve the algorithm - even having read all current texts in the
field. Whilst I've currently been able to test numbers up to 32 bits, my aim
is to hit the 64-bit mark, a slow process, but one I feel will be worthwhile
for my research.


for n = 3 to 2^64 - 1 step 3
    if mpz_probab_prime_p(n, 5) = 0 // misses occasional composites!!!
    end if


Changing the second line to

    if mpz_probab_prime_p(n, 5) <> 2

would mean testing lots of prime numbers, slowing down the whole process
dramatically. Also, changing the iteration count slows the process down
however that is something I may be able to do armed with the information
from Mr. Nicely's site.

If I'm right in reading Mr. Nicely's site correctly, there are a range of
numbers, some rather small, which mpz_probab_prime_p thinks are probably
prime, when they are in fact composite. I agree that this may not cause a
problem with those individuals interested in searching for primes, however
in my case, it would case a severe problem.

As to the machines in question, I run the algorithm on 3 custom built 64-bit
systems, with (darned expensive, but worth every penny) exceptionally high
quality memory, and perform a double check on a third machine (which runs a
totally different operating system). I've also been able to verify my
run against a 3rd party who performed an equivalent test a few years back,
but did not continue his research.
-------------- next part --------------
An HTML attachment was scrubbed...

More information about the gmp-discuss mailing list