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

Re: Appropriate primality test?

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