I'm trying to prove one of the properties of the “Modified Rabin Signature Scheme”:

If $\gcd(x, n) = 1$, then $x^{\frac{(p−1)(q−1)}{2}} \equiv 1 \pmod n$

This is what I’ve got so far…


Let $p$ and $q$ be primes such that $p \equiv 3 \pmod 4$ and $q \equiv 3 \pmod 4$

$$p = 4 t_1 + 3 , \, q = 4 t_2 + 3 \,\,\,\,\,\,\,\,\,\,-(I)$$

Then ($s$ = odd)

$$\frac{\phi(n)}{2} = 2 s\\$$

From the “Euler theorem” we know that

$$x^{\phi(n)} \equiv 1 \pmod n$$

Taking square root both sides

$$x^{\frac{\phi(n)}{2}} \equiv \sqrt{1} \pmod n$$


$$x^{\frac{\phi(n)}{2}} \equiv -1 \pmod n \, \text{ i.e. } \, x^{2s} \equiv -1 \pmod n\\ \implies x^{2s} -1 = nk$$

subsituting values of $p, q$ from $(I)$ we get

$$x^{\text{even}} = (\text{odd})k + 1$$

Now, I want to show that

$$x^{\text{even}} \neq (\text{odd})k + 1$$

… but I'm kind of stuck here.

Can anybody help me complete this proof of one of the properties of Modified Rabin Signature?

  • $\begingroup$ The square root operation is not well-defined on $Z_n$. For instance, if $n = 5$, then, $1\cdot 1 = 3 \cdot 3 = 4 \cdot 4 = 1 \pmod n$... $\endgroup$ Commented Jan 31, 2016 at 11:20
  • $\begingroup$ Please, could you write all the hypothesis about the the values $p, q, n,$ and $x$ ? This may help people to understand better the problem. Because you are trying to prove a general implication, but in the proof, you are taking $p$ and $q$ as prime whose residues mod $4$ is $3$... $\endgroup$ Commented Jan 31, 2016 at 11:24
  • $\begingroup$ I suggest you read chapters 2 and 3 of the Handbook of Applied Cryptography. $\endgroup$
    – fkraiem
    Commented Jan 31, 2016 at 12:08
  • 1
    $\begingroup$ Hint: prove that $p=3\pmod4$, $p$ prime, $q=3\pmod4$, $q$ prime, $n=pq$, $\gcd(x,n)=1$ implies $x^{\frac{(p−1)(q−1)}{2}}-1\equiv0\pmod p$ and $x^{\frac{(p−1)(q−1)}{2}}-1\equiv0\pmod q$; then use $p\ne q$ and conclude. $\endgroup$
    – fgrieu
    Commented Jan 31, 2016 at 12:12

1 Answer 1


In short words: when you compute things modulo $n = pq$, you are really computing things simultaneously modulo $p$ and modulo $q$. That's the gist of the Chinese Remainder Theorem. So to prove that $a = b \pmod n$, you just have to prove that $a = b \pmod p$ and $a = b \pmod q$.

Modulo $p$, for any $x$ that is not a multiple of $p$, $x^{p-1} = 1 \pmod p$ (this is Fermat's little theorem). Therefore, $x^{k(p-1)} = 1^k = 1 \pmod p$ for any integer $k$. Now, $p$ and $q$ are big primes, so they are odd. It follows that $q-1$ is even, therefore $(q-1)/2$ is an integer. So $x^{(p-1)(q-1)/2} = 1 \pmod p$. The same holds modulo $q$ for the same reason. By the CRT, you get the result modulo $n$.

Note that while Rabin's cryptosystem is defined with $p = 3 \pmod 4$ and $q = 3 \pmod 4$, these properties are not necessary to demonstrate that $x^{(p-1)(q-1)/2} = 1 \pmod n$. It also works when $p = 1 \pmod 4$ or $q = 1 \pmod 4$. The only requirement is that $x$ is relatively prime to both $p$ and $q$, which is exactly what $\mathrm{gcd}(x,n) = 1$ means.

  • $\begingroup$ whats wrong with my above approach. Can you tell me where I did it wrong. $\endgroup$
    – Atinesh
    Commented Feb 6, 2016 at 13:19

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.