Efficient quadratic residue mod 2^32

I want to determine if a value is a quadratic residue mod $2^{32}$. I've developed a very fast pre-screening method based on a Bloom Filter that identifies quadratic residues for mod $2^7=128$ in just a couple multiplies, but it can't extend to much higher powers efficiently.

The general method of testing for quadratic residues will work, using Hensel lifting to find a modular square root if it exists, but I wonder if there are any shortcuts given the specific modulus of $2^{32}$.

This is for a computer search, so efficiency using 32 or 64 bit math helps.

flag	asked Jul 19 2010 at 6:36 MathMonkey 103●1●3

A number $n$ is a square modulo $2^k$ if and only if $n=2^{2r}m$ where $m\equiv1$ (mod 8) or (mod $2^{k-2r}$) (whichever modulus is smaller.) – Robin Chapman Jul 19 2010 at 6:41

Robin, that sounds like it's quite computable! Could you add that as an answer so we can vote and discuss it? What's the logic or derivation behind that conclusion? – MathMonkey Jul 19 2010 at 16:07

It is induction on Robin's $k.$ You will need to do some exercises and read between the lines a little, but see "Integral Quadratic Forms" by George Leo Watson and the more recent "p-adic Numbers: An Introduction" by Fernando Q. Gouvea. Any book on integral or rational quadratic forms does 2-adic squares at some point. – Will Jagy Jul 19 2010 at 17:07

Another counterexample to "Mathoverflow is for research level mathematics questions" thesis. – Victor Protsak Jul 20 2010 at 6:48

Browse other questions tagged nt.number-theory quadratic-residues computer-algebra or ask your own question.

question feed