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

Re: [PrimeNumbers] Appropriate primality test?

Expand Messages
  • 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 1 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 2 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.