Here's the deal: I'm a little burned out of late and so I'm hoping some of you here can help out in developing a really fast test using only (or mostly) bitwise operators. It's not that I can't figure it out or anything...just a bit too bleary to channel those creative forces to pull it all together.
The mathematical description is actually quite simple (does vbulletin support math markup?). In pseudocode:
Alternately (and probably more concisely), "constraint" could be defined as:Code:constraint(n){ 2^((n-1)/2) % n == (n-1) } special(n){ constraint(n) && constraint((n-1)/2) }
...where the above is obviously a modular square root.Code:constraint(n){ sqrt(2^(n-1)) == -1 (mod n) }
Oh, and the implementation should ideally be bit-width-neutral (ie: not tailored to 32-bits or what have you).
Any and all help would be greatly appreciated!