- --- Kaveh <kaveh_vejdani@...> wrote:
> Hi Everybody,

How do you know that sieving is prohibitively slow? Can you show me your

>

> 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?

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

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

> (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

Selecting particular forms is incompatible with requiring random candidates.

> required density in the range of question) whose primality can be

> proved in reasonable time? (a few microseconds?)

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 - Brought back on-list with permission.

--- Kaveh <kaveh_vejdani@...> wrote:> --- In primenumbers@yahoogroups.com, Phil Carmody <thefatphil@...> wrote:

Good - you've done your research - that sieve is a smart design.

> > --- 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

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

But you only need a tiny fraction of the primes in that range.

> 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?

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

Then chose a random residue r in the totients of 19#, and

> that from a

> > sieved contiguous block.

>

> That's true. However, I can sacrifice randomness for the benefit of

> speed.

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

Repeated SPRP tests, where you also compare sqrt(-1) between SPRP tests.

> > > (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?

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