My question relates to square roots of unity modulo N, ie $r^2 = 1 \mod N$.
I have an efficient algorithm for obtaining these for arbitrary $N$. But for a given $N$ what I really want is to obtain the roots for all $N_f = \frac {N^2}{f^2}$ for all $fN$.
My question is simply this  can these all be deduced from the square roots of unity mod $N$? Or do I need multiple invocations of my root finder?



closed as off topic by Felipe Voloch, Chris Godsil, Charles Matthews, Franz Lemmermeyer, Chandan Singh Dalawat Jan 18 '13 at 14:34
Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.
Given the square roots of $1$ modulo $N$ you can deduce the square roots of $1$ modulo $N^2$ just by using Hensel's Lemma (without factoring). Specifically let $r$ be one of the square roots of $1$ modulo $N^2$. Then $r \equiv s \pmod{N}$ where $s$ is one of the square roots of $1$ modulo $N$. Now $r=s+\lambda N$ and you want to find $\lambda$ modulo $N$. You want $$ (s+\lambda N)^2 1 \equiv 0 \pmod{N^2} $$ which is the same as $$ \frac{s^21}{N} \equiv 2s \lambda \pmod{N}. $$ So the problem reduces to solving this congruence modulo $N$. Incidentally, in complexity terms the problem of finding square roots modulo $N$ isn't easier than factoring $N$. 

