Theorem: Let $y$ be a quadratic residue in $\mathbb{Z}_N$* where $N=pq$.

There are exactly four integers $x_1, x_2, x_3, x_4$ where $0 < x_1 < x_2 < \frac{N}{2} < x_3 < x_4 < N$ such that $y = x_i^2 \pmod{N}$ for $i=1,2,3,4$.

The above theorem simply states that exactly two of the four roots must be greater than $\frac{N}{2}$.

Most papers will say that this result is well known, without providing any detailed proof. How can we prove that $0 < x_1 < x_2 < \frac{N}{2} < x_3 < x_4 < N$?

  • 1
    $\begingroup$ This can easily be proven by the fact that with a square root $a$, there is also a square root $-a$. And if you look at this pair, one will be between 0 and $N/2$ and the other one between $N/2$ and $N$. $\endgroup$
    – tylo
    Jul 1 '14 at 10:50
  • $\begingroup$ @tylo This is basically what my answer says... $\endgroup$
    – Thomas
    Jul 1 '14 at 10:55

Each root $r$ in $(\mathbb{Z}/n\mathbb{Z})^\times$ has a ``conjugate'' root $-r \equiv n - r$ since trivially $(-r)^2 \equiv r^2 \pmod{n}$.

If there are exactly four roots (each prime factor generally brings in two roots, well, one root and its conjugate, and they generate the roots modulo $n$ via by CRT - see gammatester's answer below for more details) we have exactly two pairs of conjugate roots. In each pair exactly one root will be greater than $n/2$.

By simple arithmetic, one can see that $r < n/2 \iff n-r > n/2$. Thus, assuming that $n$ is odd (which rules out the possibility that $r = n/2$), it follows that exactly one of each conjugate pair of roots is grater than $n/2$.

  • $\begingroup$ But, how we know for sure in each pair exactly one root will be greater than n/2. I;m sorry since i couldnt understand your point. For me, 'In each pair exactly one root will be greater than n/2' is still a plain statement. Dont u think so? $\endgroup$ Jul 1 '14 at 10:24
  • 1
    $\begingroup$ @habillqabill Suppose $n$ is odd. Let $r$ be any integer between $1$ and $n$. Now suppose $r$ is less than $n/2$, then we are done. If $r$ is in fact greater than $n/2$, then $n - r < n/2$ and we are done. Basically, no matter $r$, either $r$ or $n - r$ will be less than $n/2$ (since both will fall on opposite sides of $n/2$). It's a symmetry argument. $\endgroup$
    – Thomas
    Jul 1 '14 at 10:25
  • $\begingroup$ oh yeah, that correct. n should be an odd number. By the way, i'll try to turn your argument into a mathematical statement. I see it all over the places, particularly when involving Rabin primitive, without any explanation. $\endgroup$ Jul 1 '14 at 10:30
  • $\begingroup$ @habillqabill If this answers your question, would you consider accepting it by clicking on the check mark on the left? $\endgroup$
    – Thomas
    Jul 3 '14 at 15:12
  • $\begingroup$ ok done. tq guys. $\endgroup$ Jul 11 '14 at 8:00

This is not correct for all primes $p,q;\;$ even if $p\ne q:\;$ take e.g. $p=2$, $q=5$. Here you have two quadratic residues in $(\mathbb{Z}/n\mathbb{Z})^\times$ namely $1$ and $9\equiv -1,\;$ but both have only two square roots: $$1^2 \equiv 9^2 \equiv 1 \pmod {10}, \quad \text{and}\quad 3^2 \equiv 7^2 \equiv 9 \pmod {10}$$

  • $\begingroup$ Your example is a particular case involving the prime 2 (even number). However, in practical we used large primes, then the theorem will always correct since all other primes are odd numbers. $\endgroup$ Jul 1 '14 at 10:20
  • $\begingroup$ @habillqabill: No, at least you must additionally assume $p\ne q.$ $\endgroup$ Jul 1 '14 at 10:26
  • $\begingroup$ However, if u familiar with Rabin's encryption or modular square root problem, then it is mathematically proven that there are exactly four integers x_i such that y=x^2(mod pq) $\endgroup$ Jul 1 '14 at 10:36
  • 2
    $\begingroup$ Rabin assumes distinct primes and $p\equiv q \equiv 3 \pmod 4$. For the general problem with two odd primes there is another counter example. Take look at $p=q=3:\;$ $$1^2 \equiv 8^2 \equiv 1 \pmod {9}, \quad 2^2 \equiv 7^2 \equiv 4 \pmod {9}, \quad 4^2 \equiv 7^2 \equiv 5 \pmod {9}$$ @tylo: Here $\varphi(9)=6$ is no multiple of 4. $\endgroup$ Jul 1 '14 at 10:50
  • 1
    $\begingroup$ It was not me throwing in Rabin. $\endgroup$ Jul 1 '14 at 11:03

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.