Loading ...
Sorry, an error occurred while loading the content.
 

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

Expand Messages
  • Phil Carmody
    ... 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.