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

| improve this answer | |
  • $\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$ – habillqabill 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$ – habillqabill 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$ – habillqabill 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}$$

| improve this answer | |
  • $\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$ – habillqabill Jul 1 '14 at 10:20
  • $\begingroup$ @habillqabill: No, at least you must additionally assume $p\ne q.$ $\endgroup$ – gammatester 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$ – habillqabill 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$ – gammatester Jul 1 '14 at 10:50
  • 1
    $\begingroup$ It was not me throwing in Rabin. $\endgroup$ – gammatester 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.