Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
14  
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 '10 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 '10 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 '10 at 17:07
1  
Another counterexample to "Mathoverflow is for research level mathematics questions" thesis. –  Victor Protsak Jul 20 '10 at 6:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.