# Cocks IBE Scheme: why is -a a quadratic residue mod n?

In the Cocks IBE scheme it is required for the hash function, that the Jacobi symbol of its output and the universally available moduls $n = p*q$ is $+1$, so:

$\Big(\frac{H(ID)}{n}\Big) = \Big(\frac{a}{n}\Big) = \Big(\frac{a}{p}\Big) * \Big(\frac{a}{q}\Big) = +1$

So, either both Jacobi symbols $\Big(\frac{a}{p}\Big)$ and $\Big(\frac{a}{q}\Big)$ are $+1$ or $-1$. In the frist case, $+a$ is a quadratic residue modulo $n$, because its the product of two numbers that are quadratic residue mod $n$. So far its clear to me. However, in the latter case, why is $-a$ a quadratic residue?

In Cocks paper [1] it says: The latter case arises because by construction $p$ and $q$ are both congruent to 3 mod 4, and so $\Big(\frac{-1}{p}\Big) = \Big(\frac{-1}{q}\Big) = -1$

If I try solve it for the case that $-a$ is a quadratic residue mod $n$, and that both $\Big(\frac{a}{p}\Big) = \Big(\frac{a}{q}\Big) = -1$,

I come to the following result:

$\Big(\frac{-a}{n}\Big) = \Big(\frac{-a}{p}\Big) * \Big(\frac{-a}{q}\Big) = \Big(\frac{a}{p}\Big) * \Big(\frac{-1}{p}\Big) * \Big(\frac{a}{q}\Big) * \Big(\frac{-1}{q}\Big)$

$= \Big(\frac{a}{p}\Big) * (-1) * \Big(\frac{a}{q}\Big) * (-1) = \Big(\frac{a}{p}\Big) * \Big(\frac{a}{q}\Big) = (-1) * (-1) = +1$

However, in the last step both Jacobi symbols are $-1$, and thus $-a$ cannot be a quadratic residue mod $n$, because it is the product of two quadratic nonresidues?

I must have made a mistake somewhere, but I don't see it.

[1] Clifford Cocks: An Identity Based Encryption Scheme based on Quadratic Residues, 2001.

• Quoting Wikipedia: modulus some composite not a prime power, the product of two nonresidues may be either a residue, a nonresidue, or zero
– fgrieu
Dec 9 '14 at 17:39
• If the product can be either a residue, a nonresidue or zero, how can it be ensured that $-a$ is a quadratic residue modulo $n$? It could also be a nonresidue potentially? Dec 9 '14 at 17:46

If $a$ is a nonresidue mod $p$, then since $-1$ is also a nonresidue mod $p$ by construction, $-a$ is a residue mod $p$. And likewise mod $q$, so $-a$ is a residue mod $pq$.
• Just to make it clear for me: by construction it is (for case two): $\Big(\frac{a}{p}\Big) = -1$ and $\Big(\frac{-1}{p}\Big) = -1$. So it holds that: $\Big(\frac{-a}{p}\Big) = \Big(\frac{a}{p}\Big) * \Big(\frac{-1}{p}\Big) = (-1) * (-1) = +1$. But, as fgrieu said, the product of two nonresidues can also be a nonresidue again. Why must $-a$ be a residue mod $p$? Dec 9 '14 at 18:05