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!