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?
$\begingroup$
$\endgroup$
9
-
$\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 VolochCommented Jan 18, 2013 at 13:11
-
$\begingroup$ Do you really need Hensel's lemma? $\endgroup$– Dror SpeiserCommented Jan 18, 2013 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 TrimbleCommented Jan 18, 2013 at 13:58
-
$\begingroup$ @Todd Trimble: the roots of the equation can all be deduced. $\endgroup$– Charles MatthewsCommented Jan 18, 2013 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 MatthewsCommented Jan 18, 2013 at 14:12
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
3
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$ Commented Jan 18, 2013 at 15:07
-
$\begingroup$ BTW, I believe the RHS above should be $-2s\lambda$ $\endgroup$ Commented Jan 20, 2013 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$ Commented Jan 31, 2013 at 15:26