Skip to main content
1 of 2
Siksek
  • 3.1k
  • 19
  • 29

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

Siksek
  • 3.1k
  • 19
  • 29