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