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

RE: [PrimeNumbers] proth sieving optimisations

Expand Messages
  • 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 1 of 3 , Jul 19, 2005
      > 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.