New code for primality testing

[Marco Bodrato]

Ciao,

Il Gio, 22 Novembre 2018 3:43 pm, Pedro Gimeno ha scritto:
> All primes are guaranteed to pass the test. The question is whether

The primes are guaranteed to pass the test... but the test is not
guaranteed to be correctly implemented :-)

Anyway, we tested all primes up to 2^40, and they pass the current GMP
implementation of the test :-D

> there's a pseudoprime that passes the test. Using the same database of
> pseudoprimes, two independent people have confirmed the 2^64 upper bound.

Using again the same database
(http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html) and the attached
code, we too can confirm that all that composites are correctly detected
by our implementation.

I tested this with both a 64 and a 32 bits variant of the current GMP
(That code directly calls the internal function for the Lucas' part of the
test. It is intended to work only with the current development version).

$ bzcat psps.bz2|time ./composites|cmp - <(bzcat psps.bz2)
1478.37 user 2.09 system 24:42.30 elapsed 99% CPU


Compiled with

gcc -DUSE_MINI_GMP -I./mini-gmp -O2 -o mini-composites composites.c

the attached code can test also the internals of the current mini-gmp.
Again we can confirm that all those composites are correctly detected.
mini- was tested both with 64-bits limbs and with "typedef unsigned char
mp_limb_t;". The latter required some hours.

> Since that database was the same, it doesn't count as an independent
> confirmation.

Yes, confirming the database is not such a simple task...

Ĝis,
m

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