4
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 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
    Commented Jul 1, 2014 at 10:50
  • $\begingroup$ @tylo This is basically what my answer says... $\endgroup$
    – Thomas
    Commented Jul 1, 2014 at 10:55

2 Answers 2

Reset to default
9
$\begingroup$

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
$\endgroup$
5
  • $\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
    Commented Jul 1, 2014 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
    Commented Jul 1, 2014 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
    Commented Jul 1, 2014 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
    Commented Jul 3, 2014 at 15:12
  • $\begingroup$ ok done. tq guys. $\endgroup$
    – habillqabill
    Commented Jul 11, 2014 at 8:00
2
$\begingroup$

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

Your Answer

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

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