0
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\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$
    – Mehdi Tibouchi
    Nov 21 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
    Nov 21 at 18:32

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.