So I'm given the following as a problem:

When $p$ and $q$ are distinct odd primes and $N = pq$, the points in $Z^∗_N$ have either zero or four square roots. A quarter of the points have four square roots; the rest have no square root. The four square roots of $x ∈ Z^∗_N$ will look like $±a, ±b$. (Of course, −a means N − a since we’re working modulo N.) Suppose that I give you an efficient deterministic algorithm S that, on input x that has square roots, finds some square root. (If x does not have a square root, it returns ⊥.) Use S to make an efficient probabilistic algorithm F that factors N.

I am not asking for a solution to the problem, rather an understanding of what "four square roots" could possibly mean? How can a single element $x∈ Z^∗_N$ have "four square roots"?


"$x$ has four square roots" means there are four distinct elements $r$ in the group such that $r^2 = x$.

For example, in $\mathbf{Z}_{15}^\times$ the element $1$ has four square roots, which are $1$, $4$, $11$, and $14$ (note that $11 \equiv -4$ and $14 \equiv -1 \pmod{15}$).


I want to give a proof and solution here. Suppose $x^2 \equiv m\pmod{N}$ has a root $x=x_{0}$, then we can obtain another three roots as following:

Let $x_{0} \equiv x_{1}\pmod{p}$ and $x_{0} \equiv x_{2}\pmod{q}$ respectively.Thus,

  • $x^2 \equiv m\pmod{p}$ has exactly two square roots, that's $x \equiv x_{1}\pmod{p}$ and $x \equiv p-x_{1}\pmod{p}$.
  • similarly, $x^2 \equiv m\pmod{q}$ has exactly two square roots, that's $x \equiv x_{2}\pmod{q}$ and $x \equiv q-x_{2}\pmod{q}$.
    From Chinese Remainder Theorem, the congruence equation $x^2 \equiv m\pmod{N}$ has exactly four roots.They are the roots in the combination
    \begin{equation} \left\{ \begin{array}{cl} x \equiv x_{1}\pmod{p} & \\ & \\ x\equiv x_{2}\pmod{q} & \end {array}\right. \end{equation} \begin{equation} \left\{ \begin{array}{cl} x \equiv x_{1}\pmod{p} & \\ & \\ x\equiv q-x_{2}\pmod{q} & \end {array}\right. \end{equation} \begin{equation} \left\{ \begin{array}{cl} x \equiv p-x_{1}\pmod{p} & \\ & \\ x\equiv x_{2}\pmod{q} & \end {array}\right. \end{equation} \begin{equation} \left\{ \begin{array}{cl} x \equiv p-x_{1}\pmod{p} & \\ & \\ x\equiv q-x_{2}\pmod{q} & \end {array}\right. \end{equation} We denoted the first two equation's root by $a$, $b$, then ($N-a$) and ($N-b$) are respectively roots of the last two equations.
    From the above, the four square roots are $a$, $b$, ($N-a$) and ($N-b$).
    That is worth mentioning, when $p, q$ are Blum primes, i.e. $p\equiv q \equiv3 \pmod{4}$, $x \equiv\pm m^{\frac{p+1}{4}} \pmod{p}$ are exactly the roots of equation $x^2 \equiv m\pmod{p}$.
  • $\begingroup$ This does not answer the question, which was about what the term "square root" means in this context. $\endgroup$ – fkraiem Apr 4 '17 at 6:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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