about prime number generation

Garcia Moreno-Esteva, Enrique enrique.garciamoreno-esteva at helsinki.fi
Sat Apr 30 21:12:10 CEST 2022


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.


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<mailto:enrique.garciamoreno-esteva at helsinki.fi>> wrote:

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>

More information about the gmp-discuss mailing list