New code for primality testing

Marco Bodrato bodrato at
Sat Jan 5 13:49:04 UTC 2019


Il Mer, 21 Novembre 2018 10:43 pm, Torbjörn Granlund ha scritto:
> "Marco Bodrato" <bodrato at> writes:
>   If we can verify the source of the second claim, since we just
>   implemented BPSW, we should decide to return 2 (surely prime)
>   for all "probable" primes under this threshold.
> We could check ourselves to a gradually larger bound, then insert our
> latest determined bound into the current GMP code and return 2 for
> smaller primes.

I pushed some trivial code to check if our function for primality testing
is returning the correct value.

It sieves the primes using primesieve.c, then tests _ALL_ numbers with
mpz_probab_prime_p(n,10); with the current implementation, this means
using our code for BPSW.

While testing that code, I sieved several (slightly overlapping) chunks of
numbers, the highest one I tried is:

[bodrato at ashell ~]$ time /home/bodrato/gmp-repo/tests/devel/primes
490000000000 500000000000
490163142656 (7220000000)
499826819072 (7460000000)
Prime tests checked in [490000000000 - 500000000000] [721646a400 -

real	45m13.028s

So that we can currently say that, up to 5*10^11, mpz_probab_prime_p could
return 2 instead of 1 for primes. Anyway, this is a small bound if
compared to 2^64...



More information about the gmp-devel mailing list