## Appropriate primality test?

Expand Messages
• 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
Message 1 of 3 , Oct 16 1:08 AM
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?)

Kaveh
• ... 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 2 of 3 , Oct 16 2:07 AM
--- 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
• 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 3 of 3 , Oct 16 11:56 PM
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.