about prime number generation

[Marco Bodrato]

Ciao,

Il Sab, 30 Aprile 2022 9:40 pm, Christian Calderon ha scritto:
> Ok. mpz_probab_prime_p performs a BPSW primality check. Looking that up on
> wikipedia it seems to be deterministic for numbers less than 2**64. You

This claim is based on a collection of pseudo-primes that was not checked
by a second author. It would be nice to have another source to confirm
it...

> On Sat, Apr 30, 2022 at 12:12 PM Garcia Moreno-Esteva, Enrique <
> enrique.garciamoreno-esteva at helsinki.fi> wrote:

>> Thank you for your reply! It is useful. However, I need to get primes up
>> to 10^12 (about 2^40), hence my question. I know there are deterministic

Here is a comment from the source of the released GMP-6.2.1 library:
   This implementation of the Baillie-PSW test was checked up to 31*2^46,
 [ https://gmplib.org/repo/gmp-6.2/file/tip/mpz/millerrabin.c#l11 ]

This means that, up to that limit, implementation of nextprime in GMP,
will always return the next prime, and not a pseudo-prime.

>> *From:* Christian Calderon

>> I ran a script to test this. It uses a sieve of eratosthenes and
>> generates
>> a list of all primes less than 0xFFFFFFFF (i.e. 2**32 - 1), and calls
>> nextprime to see if the result is equal to the next prime in the list.

There is something like that in tests/devel/primes.c
If you have the sources of the library
$make -C tests/devel/ primes
$tests/devel/primes n 4294967296
Should perform basically the same tests.


Ĝis,
m