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

  • $\begingroup$ 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. $\endgroup$ Commented Nov 21, 2023 at 16:22
  • $\begingroup$ @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. $\endgroup$
    – ark
    Commented Nov 21, 2023 at 18:32


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.