about prime number generation

[Garcia Moreno-Esteva, Enrique]

Thank you! This is very useful to know. If it is fast enough, it will work. Just out of curiosity, how quickly did you get the primes below 2^32?

Enrique

Get Outlook for iOS<https://aka.ms/o0ukef>
________________________________
From: Christian Calderon <calderonchristian73 at gmail.com>
Sent: Saturday, April 30, 2022 10:40:38 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

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<mailto: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<mailto:calderonchristian73 at gmail.com>>
Sent: Saturday, April 30, 2022 10:08:25 PM
To: Garcia Moreno-Esteva, Enrique <enrique.garciamoreno-esteva at helsinki.fi<mailto:enrique.garciamoreno-esteva at helsinki.fi>>
Cc: gmp-discuss at gmplib.org<mailto:gmp-discuss at gmplib.org> <gmp-discuss at gmplib.org<mailto: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<mailto: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<mailto:gmp-discuss at gmplib.org>
https://gmplib.org/mailman/listinfo/gmp-discuss