Re: Mersenne: Is 2 mod ((2^p) - 1) square?

Hi folks >Benny Van Houdt asked about checking 2 mod Mp for "square-ness". [digest >#537] >The hard way is to square every number from sqrt(Mp) to Mp-1, mod Mp, for >equality to 2. This will take ~`(Mp-sqrt(Mp)) square/mod operations, or >O(Mp)...too long. Just a suggestion to you all... don't

Mersenne: Is 2 mod ((2^p) - 1) square?

Benny Van Houdt asked about checking 2 mod Mp for "square-ness". [digest #537] The hard way is to square every number from sqrt(Mp) to Mp-1, mod Mp, for equality to 2. This will take ~`(Mp-sqrt(Mp)) square/mod operations, or O(Mp)...too long. Another way to look at this: if x == 2 (mod Mp), then