Loading ...
Sorry, an error occurred while loading the content.

Appropriate primality test?

Expand Messages
  • Kaveh
    Hi Everybody, There are roughly 2.4 x 10^17 primes in the range [10^18,10^19] and I need to find a random 5.5 x 10^10 of them. 1. Knowing that sieving is
    Message 1 of 3 , Oct 16, 2006
    • 0 Attachment
      Hi Everybody,

      There are roughly 2.4 x 10^17 primes in the range [10^18,10^19] and
      I need to find a random 5.5 x 10^10 of them.

      1. Knowing that sieving is prohibitively slow in that range, what is
      the fastest deterministic primality test I should use?

      2. My initial thought is to consider numbers of the special form
      (2^a)(3^b)+1 or more generally (p^a)(q^b)(r^c)+1. Does that help
      with computation speed?

      3. Any other suggestions for special number forms (considering the
      required density in the range of question) whose primality can be
      proved in reasonable time? (a few microseconds?)

      Appreciating your feedback in advance,

      Kaveh
    • Phil Carmody
      ... How do you know that sieving is prohibitively slow? Can you show me your comparison of the time it takes to generate a sequence of prime numbers using a
      Message 2 of 3 , Oct 16, 2006
      • 0 Attachment
        --- Kaveh <kaveh_vejdani@...> wrote:
        > Hi Everybody,
        >
        > There are roughly 2.4 x 10^17 primes in the range [10^18,10^19] and
        > I need to find a random 5.5 x 10^10 of them.
        >
        > 1. Knowing that sieving is prohibitively slow in that range, what is
        > the fastest deterministic primality test I should use?

        How do you know that sieving is prohibitively slow? Can you show me your
        comparison of the time it takes to generate a sequence of prime numbers using a
        sieve designed for large numbers of primes of that size compared to a test
        which uses a PRP test?

        However, if you want random candidates, you aren't going to get that from a
        sieved contiguous block.

        > 2. My initial thought is to consider numbers of the special form
        > (2^a)(3^b)+1 or more generally (p^a)(q^b)(r^c)+1. Does that help
        > with computation speed?

        Nope. It seriously reduces the randomness of the candidates though.

        > 3. Any other suggestions for special number forms (considering the
        > required density in the range of question) whose primality can be
        > proved in reasonable time? (a few microseconds?)

        Selecting particular forms is incompatible with requiring random candidates.

        Phil

        () ASCII ribbon campaign () Hopeless ribbon campaign
        /\ against HTML mail /\ against gratuitous bloodshed

        [stolen with permission from Daniel B. Cristofani]

        __________________________________________________
        Do You Yahoo!?
        Tired of spam? Yahoo! Mail has the best spam protection around
        http://mail.yahoo.com
      • Phil Carmody
        Brought back on-list with permission. ... Good - you ve done your research - that sieve is a smart design. The C GPL code is not brilliant, but it s so simple
        Message 3 of 3 , Oct 16, 2006
        • 0 Attachment
          Brought back on-list with permission.

          --- Kaveh <kaveh_vejdani@...> wrote:
          > --- In primenumbers@yahoogroups.com, Phil Carmody <thefatphil@...> wrote:
          > > --- Kaveh <kaveh_vejdani@...> wrote:
          > > > Hi Everybody,
          > > >
          > > > There are roughly 2.4 x 10^17 primes in the range [10^18,10^19]
          > and
          > > > I need to find a random 5.5 x 10^10 of them.
          > > >
          > > > 1. Knowing that sieving is prohibitively slow in that range,
          > what is
          > > > the fastest deterministic primality test I should use?
          > >
          > > How do you know that sieving is prohibitively slow? Can you show
          > me your
          > > comparison of the time it takes to generate a sequence of prime
          > numbers using a
          > > sieve designed for large numbers of primes of that size compared
          > to a test
          > > which uses a PRP test?
          >
          > Oliveira e Silva's best algorithm

          Good - you've done your research - that sieve is a smart design.
          The C GPL code is not brilliant, but it's so simple that it can be
          easily improved. It's the sieve I had in mind.

          > takes almost 10 seconds to sieve
          > an interval of 10^9 integers starting at 10^18. This means it will
          > take me 10^11 seconds (3170 years) to sieve [10^18,10^19]. Isn't
          > this prohibitive?

          But you only need a tiny fraction of the primes in that range.
          IIRC, you only need 10^-6 of the primes, so you'd take about a day.

          > PRP test is no good. I need definitive primes.

          The Jaeschke/Moxham bounds for PRP tests apply. So each prime will
          cost you about 5 PRP tests to guarantee real primality.

          > > However, if you want random candidates, you aren't going to get
          > that from a
          > > sieved contiguous block.
          >
          > That's true. However, I can sacrifice randomness for the benefit of
          > speed.

          Then chose a random residue r in the totients of 19#, and
          a random value n such that (n+a)*19#+r is in [10^18..10^19]
          for a in [1..1000000000], and then sieve that arithmetic
          progression. You'll find 10^8 primes in that range. Repeat
          as often as necessary.

          It's certainly true that stopping a sieve early and then just
          PRP-ing what remains (enough times), is an alternative technique
          However, the sieving cutoff can only be found by testing your
          particular implementations. I would be surprised if sieving to
          10^7 was too far. Perhaps sieving to 10^9 is too far.

          > > > 2. My initial thought is to consider numbers of the special form
          > > > (2^a)(3^b)+1 or more generally (p^a)(q^b)(r^c)+1. Does that help
          > > > with computation speed?
          > >
          > > Nope. It seriously reduces the randomness of the candidates though.
          >
          > Isn't there any fast algorithm to generate definitive primes? Any
          > special conditions in primality tests to speeds them up?

          Repeated SPRP tests, where you also compare sqrt(-1) between SPRP tests.
          If you select r such that r==1 (mod 3) in the above AP constuction, then
          you can also compare cube roots of -1 which will permit you to do fewer tests.

          Phil

          () ASCII ribbon campaign () Hopeless ribbon campaign
          /\ against HTML mail /\ against gratuitous bloodshed

          [stolen with permission from Daniel B. Cristofani]

          __________________________________________________
          Do You Yahoo!?
          Tired of spam? Yahoo! Mail has the best spam protection around
          http://mail.yahoo.com
        Your message has been successfully submitted and would be delivered to recipients shortly.