New code for primality testing

[Marco Bodrato]

Ciao,

Il Mer, 21 Novembre 2018 10:43 pm, Torbjörn Granlund ha scritto:
> "Marco Bodrato" <bodrato at mail.dm.unipi.it> 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.

https://gmplib.org/repo/gmp/rev/8c30f7900f5a

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)
500000269297
Prime tests checked in [490000000000 - 500000000000] [721646a400 -
746a528800].

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

Ĝis,
m

-- 
http://bodrato.it/papers/