0

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?

flag
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. – Felipe Voloch Jan 18 at 13:11
Do you really need Hensel's lemma? – Dror Speiser Jan 18 at 13:57
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.) – Todd Trimble Jan 18 at 13:58
@Todd Trimble: the roots of the equation can all be deduced. – Charles Matthews Jan 18 at 14:01
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. – Charles Matthews Jan 18 at 14:12
show 4 more comments

closed as off topic by Felipe Voloch, Chris Godsil, Charles Matthews, Franz Lemmermeyer, Chandan Singh Dalawat Jan 18 at 14:34

1 Answer

5

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

link|flag
Thank you very much, that helps, and I can see how it extends to $N^2/f^2$. – Jim White Jan 18 at 15:07
BTW, I believe the RHS above should be $-2s\lambda$ – Jim White Jan 20 at 10:23
Thanks---I've corrected it now. – Samir Siksek Jan 20 at 11:56
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. – Emil Jeřábek Jan 31 at 15:26

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