Sorry, an error occurred while loading the content.

## Re: Appropriate primality test?

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