about prime number generation

Sat Apr 30 23:39:42 CEST 2022

I worked on nth_prime(n) in a series of patches three years ago
You can see my code in these branches
https://github.com/sethtroisi/libgmp/tree/nth_prime3
https://github.com/sethtroisi/libgmp/tree/nth_prime2
https://github.com/sethtroisi/libgmp/tree/nth_prime
And the pull requests here
https://github.com/sethtroisi/libgmp/pulls

Sadly this never made it upstream as the review process for a faster
next_prime took up all of my energy

In practice I'd recommend you also take a look at the highly optimized code
from kimwalisch
https://github.com/kimwalisch/primecount
https://github.com/kimwalisch/primesieve
Both are available as c / c++ libraries that will do what you want much
faster than my / naive code.

On Sat, Apr 30, 2022 at 12:40 PM <gmp-discuss-request at gmplib.org> wrote:

> Send gmp-discuss mailing list submissions to
>         gmp-discuss at gmplib.org
>
> To subscribe or unsubscribe via the World Wide Web, visit
>         https://gmplib.org/mailman/listinfo/gmp-discuss
> or, via email, send a message with subject or body 'help' to
>         gmp-discuss-request at gmplib.org
>
> You can reach the person managing the list at
>         gmp-discuss-owner at gmplib.org
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of gmp-discuss digest..."
>
>
> Today's Topics:
>
>    1. about prime number generation (Garcia Moreno-Esteva, Enrique)
>    2. Re: about prime number generation (Christian Calderon)
>    3. Re: about prime number generation (Garcia Moreno-Esteva, Enrique)
>    4. Re: about prime number generation (Christian Calderon)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Sat, 30 Apr 2022 12:31:50 +0000
> From: "Garcia Moreno-Esteva, Enrique"
>         <enrique.garciamoreno-esteva at helsinki.fi>
> To: "gmp-discuss at gmplib.org" <gmp-discuss at gmplib.org>
> Subject: about prime number generation
> Message-ID:
>         <
> HE1PR0701MB249252A39F8DEB6DFB0186CAA5FF9 at HE1PR0701MB2492.eurprd07.prod.outlook.com
> >
>
> Content-Type: text/plain; charset="iso-8859-1"
>
> 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
>
>
>
> ------------------------------
>
> Message: 2
> Date: Sat, 30 Apr 2022 12:08:25 -0700
> From: Christian Calderon <calderonchristian73 at gmail.com>
> 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
> Message-ID:
>         <CAC4kXm_nDNNoKMULD72X5Yp-Sj7BdJgV9ObB4FuY6gMW=
> 5tFuQ at mail.gmail.com>
> Content-Type: text/plain; charset="UTF-8"
>
> 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
> >
>
>
> ------------------------------
>
> Message: 3
> Date: Sat, 30 Apr 2022 19:12:10 +0000
> From: "Garcia Moreno-Esteva, Enrique"
>         <enrique.garciamoreno-esteva at helsinki.fi>
> To: Christian Calderon <calderonchristian73 at gmail.com>
> Cc: "gmp-discuss at gmplib.org" <gmp-discuss at gmplib.org>
> Subject: Re: about prime number generation
> Message-ID:
>         <
> HE1PR0701MB2492B088631E87DFE0FE5A18A5FF9 at HE1PR0701MB2492.eurprd07.prod.outlook.com
> >
>
> Content-Type: text/plain; charset="Windows-1252"
>
> 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<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
>
>
> ------------------------------
>
> Message: 4
> Date: Sat, 30 Apr 2022 12:40:38 -0700
> From: Christian Calderon <calderonchristian73 at gmail.com>
> 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
> Message-ID:
>         <
> CAC4kXm-ft3Fob5ddpT-gduo36_6TkhWvG2eLvxSQR85nF5Dy2A at mail.gmail.com>
> Content-Type: text/plain; charset="UTF-8"
>
> 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
> >
> >
>
>
> ------------------------------
>
> Subject: Digest Footer
>
> _______________________________________________
> gmp-discuss mailing list
> gmp-discuss at gmplib.org
> https://gmplib.org/mailman/listinfo/gmp-discuss
>
>
> ------------------------------
>
> End of gmp-discuss Digest, Vol 201, Issue 5
> *******************************************
>