RE: [PrimeNumbers] proth sieving optimisations
> Consider the even values of n. For these, we want to know ifI haven't though about this for a long time, but, of course, we don't need
> 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 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.
Virus checked by MessageLabs Virus Control Centre.