# Finding square roots in $QR_{n}$ when its order has a small factor

I am stuck at a homework problem to find the square root of a quadratic residue $$b$$ in $$Z_n$$ ($$n$$ is not a prime). Currently, I have figured out that there exists a number $$a \in Z_n$$ such that $$a^2 \equiv 1$$. If I understand the theory correctly, that means the order of $$QR_n$$ is a multiple of $$2$$. Since $$QR_n$$ is a subgroup of $$Z_n^*$$, it means the order of $$Z_n^*$$ is also a multiple of $$2$$. I tried to leverage this knowledge to factor $$n$$ (so that I can apply Chinese remainder theorem and find the quadratic residue more efficiently). However, my computation shows that $$n$$ does not admit a small factor (I have checked numbers less than $$10000$$) at all. How can that be? If $$2 \;|\; \phi(n)$$, that implies at least one of $$3, 4, 6$$ should divide $$n$$, right? (I used the table here to save some manual computation.)

Am I going in a wrong direction? Can someone give me a hint in terms of how to find the square roots more efficiently given that we know a number $$a \in Z_n$$ such that $$a^2 \equiv 1$$?

• There always exist at least two $a\in \mathbb{Z}/n\mathbb{Z}$ such that $a^2=1$, namely $a=\pm 1$. If however you now another solution $a\neq \pm1$, then things get interesting because $(a+1)(a-1)=0$ but neither of the factors is zero mod $n$. Taking suitable GCDs should therefore solve your problem. Nov 21 at 16:22
• @MehdiTibouchi I understand how it works now. I can use gcd(a+1, n) and gcd(a-1, n) to find factors of n efficiently.
– ark
Nov 21 at 18:32