Re: [PrimeNumbers] Sieving k*2^n+1 with constant k
- --- jbrennen <jack@...> wrote:
> Take the square root of the size of the range, rounded up:This is basically the big steps baby steps discrete logarithm
> 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
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
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
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!
Do You Yahoo!?
Yahoo! Games - play chess, backgammon, pool and more