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 $f|N$.  
  

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?



Square Roots of Unity modulo  N^2
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^2-1}{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$.


