about prime number generation

[Christian Calderon]

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
could use that in combination with a wheel to find the next prime.

~ Christian Calderon


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

> Christian,
>
> 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
> versions of Miller Rabin that do this, but I don’t know what variety of
> primality testing you are using, hence the question I posed. If you know
> this, it would be great to know. Thank you indeed! If I succeed in what I
> want to do, then I will require many larger primes. But all primes under
> 2^40 would be great.
>
> Enrique
>
>
> Get Outlook for iOS <https://aka.ms/o0ukef>
> ------------------------------
> *From:* Christian Calderon <calderonchristian73 at gmail.com>
> *Sent:* Saturday, April 30, 2022 10:08:25 PM
> *To:* Garcia Moreno-Esteva, Enrique <
> enrique.garciamoreno-esteva at helsinki.fi>
> *Cc:* gmp-discuss at gmplib.org <gmp-discuss at gmplib.org>
> *Subject:* Re: about prime number generation
>
> Sorry I accidentally emailed this response to Enrique alone, resending it
> to the list.
>
> 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. It
> passed for every prime in the list, nextprime(p[i]) == p[i+1].
>
> ~ Christian Calderon
>
>
> On Sat, Apr 30, 2022 at 6:19 AM Garcia Moreno-Esteva, Enrique <
> enrique.garciamoreno-esteva at helsinki.fi> wrote:
>
> Hello,
>
> I apologize this is not a comment about your webpage, but more a question
> about your library. Would your library contain a function (call it p(n) )
> that generates the n-th prime? If it does not, alternatively, do you have a
> lower bound for  certifiably producing the next prime with the nextprime
> function in your library (it is probabilistic, but such probabilistic
> methods are deterministic below certain bounds, so my question is, what is
> the lower bound for your function)?
>
> I thank you in advance for your help.
>
> Enrique Garcia Moreno-Esteva
>
> _______________________________________________
> gmp-discuss mailing list
> gmp-discuss at gmplib.org
> https://gmplib.org/mailman/listinfo/gmp-discuss
>
>