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