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

proth sieving optimisations

Expand Messages
  • alexgreenbank
    Hello, New to the list and I ve got a few questions about sieving Proth numbers in relation to the Sierpinski conjecture. I know Mikael Klasson and Paul
    Message 1 of 3 , Jul 14, 2005
    • 0 Attachment
      Hello,

      New to the list and I've got a few questions about sieving Proth
      numbers in relation to the Sierpinski conjecture.

      I know Mikael Klasson and Paul Jobling have written an insanely
      fast siever for x86 via lots of optimisations and hand hackery
      of assembly. I'm using this very program to contribute to the
      SeventeenOrBust.com project.

      I'm looking to get something done in C (although I am using the
      GMP library which does use assembly for some processors). The
      biggest 'problem' with this library is a lack of a modmul
      operation. I might have to grab Knuth and see what I can magic
      up.

      I've 'stolen' lots of good ideas from what I can see in the output
      of proth_sieve during initialisation (finding the optimal mod value
      of n's for each k and combining this into one large group).

      I then implement the baby-steps giant-steps algorithm for solving
      the discrete log (right now it picks 15840 for m instead of using
      sqrt(p) which can be huge).

      I'm just reading up on Silver-Pohlig-Hellman and how that can
      help when p-1 is smooth.

      My main question though, is about removing k or p candidates
      before I even bother trying to calculate the discrete log to
      solve for n. I've noticed that the stat.txt value from
      proth_sieve claims that roughly 1/4 of all p's were 'whacked'
      along with 1/2 of the k values for each p.

      Under what conditions is a k or p not even tested?

      Right now I only have 2 possible conditions, based on requirements
      of Baby-Steps Giant-Steps, but they rarely ever stop a k or p
      being tested.

      1) a whole p is untested if (2^-1 mod p) doesn't exist.
      2) an individial k is untested if (k^-1 mod p) doesn't exist.

      Is it something to do with the Jacobi symbols that are computed
      during initialisation, and I'd guess it has to do with the
      k-values but I just can't see what it could be.

      I had previously looked at the problem a different way, that is
      making me think that there must be a way to detect it:-

      Compute initial_r = k*2+1 mod p.
      If initial_r == 1 then stop, p will never factor k
      set r=initial_r
      set n=1
      while( n < 50000000 ) {
      if( r == 0 ) {
      stop. p is a factor for n
      }
      r=((2*r)+1) mod p
      n=n+1
      if( r == initial_r ) {
      stop. p will never be a factor. cyclic loop of r.
      }
      }

      Many k,p values will enter loops (of a size which is a factor of
      p-1) and r will never equal 0. I could never work out whether it
      was possible to detect this 'in advance'.

      Thanks in advance,

      -Alex
    • Paul Jobling
      Hi Alex, ... If you save away the factors of p-1 when you producd them from your sieve it will help you. ... You are right to think about the Jacobi/Legendre
      Message 2 of 3 , Jul 19, 2005
      • 0 Attachment
        Hi Alex,

        > I'm just reading up on Silver-Pohlig-Hellman and how that can
        > help when p-1 is smooth.

        If you save away the factors of p-1 when you producd them from your sieve it
        will help you.

        > My main question though, is about removing k or p candidates
        > before I even bother trying to calculate the discrete log to
        > solve for n. I've noticed that the stat.txt value from
        > proth_sieve claims that roughly 1/4 of all p's were 'whacked'
        > along with 1/2 of the k values for each p.
        >
        > Under what conditions is a k or p not even tested?

        You are right to think about the Jacobi/Legendre symbol, as that is the
        reason. For Proth numbers, we are interested in whether, for a given k, the
        values k.2^n+1 are 0 mod p, for a range of values of n.

        Consider the even values of n. For these, we want to know if

        k.2^n = -1 (mod p)

        ie that

        k.2^(2m) = -1 (mod p)

        so 2^(2m) = -1.k^(-1) (mod p)

        ie (2^m)^2 = -1.k^(-1) (mod p)

        The LHS is a square, so this can only happen if the RHS is a quadratic
        residue mod p. Similarly, for the odd values of n, it is a question of
        whether -1.(2k)^-1 (mod p) is a quadratic residue mod p. This explains why
        about 1/4 of all p's can be completely ignored - both are quadratic
        non-residues mod p. In some cases, it turns out that we can ignore the odd
        values of n but not the even ones, or vice versa.

        Regards,

        Paul.



        __________________________________________________
        Virus checked by MessageLabs Virus Control Centre.
      • Paul Jobling
        ... I haven t though about this for a long time, but, of course, we don t need the inverses on the RHS, since we can rewrite this to say that (2^m)^(-2) = -1.k
        Message 3 of 3 , Jul 19, 2005
        • 0 Attachment
          > Consider the even values of n. For these, we want to know if
          >
          > k.2^n = -1 (mod p)
          >
          > ie that
          >
          > k.2^(2m) = -1 (mod p)
          >
          > so 2^(2m) = -1.k^(-1) (mod p)
          >
          > ie (2^m)^2 = -1.k^(-1) (mod p)

          I haven't though about this for a long time, but, of course, we don't need
          the inverses on the RHS, since we can rewrite this to say that

          (2^m)^(-2) = -1.k (mod p)

          and since the LHS is still a square, we just see if -k is a QR mod p or not.

          Regards,

          Paul.


          __________________________________________________
          Virus checked by MessageLabs Virus Control Centre.
        Your message has been successfully submitted and would be delivered to recipients shortly.