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?


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.

  • $\begingroup$ This question is not appropriate for this website. The FAQ mentions some other websites you might ask this question. Briefly, if you can factor $N$, then Hensel's lemma plus the Chinese remainder theorem give what you want. $\endgroup$ – Felipe Voloch Jan 18 '13 at 13:11
  • $\begingroup$ Do you really need Hensel's lemma? $\endgroup$ – Dror Speiser Jan 18 '13 at 13:57
  • $\begingroup$ I understand the mathematical content of Felipe's remark, but suppose you don't know how to factor $N$? Is there hope of a solution in that case? (I'd like for people to hold off on the rush to close before this is addressed.) $\endgroup$ – Todd Trimble Jan 18 '13 at 13:58
  • $\begingroup$ @Todd Trimble: the roots of the equation can all be deduced. $\endgroup$ – Charles Matthews Jan 18 '13 at 14:01
  • $\begingroup$ Assuming the "worst" case of N the product of two odd primes, the differences in pairs of the four roots are six numbers, and you can factorise N easily by taking the HCF with three of them ... don't think there is anything here. $\endgroup$ – Charles Matthews Jan 18 '13 at 14:12

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

  • $\begingroup$ Thank you very much, that helps, and I can see how it extends to $N^2/f^2$. $\endgroup$ – Jim White Jan 18 '13 at 15:07
  • $\begingroup$ BTW, I believe the RHS above should be $-2s\lambda$ $\endgroup$ – Jim White Jan 20 '13 at 10:23
  • $\begingroup$ Regarding the last sentence: for most purposes and intents, finding square roots mod $N$ has indeed the same computational complexity as factoring $N$, but it maybe worthwhile to mention that known reductions of factoring to square root computation, as well as known algorithm for computing square roots modulo primes (which is the base step in the opposite reduction) are randomized, and it is open whether one can do these in deterministic polynomial time. $\endgroup$ – Emil Jeřábek Jan 31 '13 at 15:26

Not the answer you're looking for? Browse other questions tagged or ask your own question.