Browse Groups

• 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
View Source
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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.