## Re: [PrimeNumbers] Sieving k*2^n+1 with constant k

Expand Messages
• ... This is basically the big steps baby steps discrete logarithm algorithm. The fixed k sieve is a discrete logarithm problem. I did think about it in the
Message 1 of 3 , Apr 24, 2002
--- jbrennen <jack@...> wrote:
> Take the square root of the size of the range, rounded up:
> Q = (ceil(sqrt(v-u+1))).
> For 0 <= a < Q, compute r_0[a] = (k*2^a)%p.
> For 0 <= b < Q, compute r_1[b] = (-1/(2^(u+b*Q)))%p.
> If there are no common elements in r_0 and r_1, then the

This is basically the big steps baby steps discrete logarithm
algorithm. The fixed k sieve is a discrete logarithm problem.
I did think about it in the past, but dismissed it as I thought the
u-v range was too small for the
O(sqrt(v-u).(O(1)+ln(v-u)) with possibly large constant factor
vs.
O(v-u) with tiny halvemod constant factor
to be a win.

However, take v to hundreds of thousands band beyond, and you're
talking favourable asymptotics certainly.
(I was only thinking of several tens of thousands when I looked at
it).

Go for it. You have nothing to lose but the creation of a sieve
that's great for _really_ large ranges, and that's not a huge
hardship is it!

Phil

__________________________________________________
Do You Yahoo!?
Yahoo! Games - play chess, backgammon, pool and more
http://games.yahoo.com/
Your message has been successfully submitted and would be delivered to recipients shortly.