# Possible to check if $a \in \mathrm{QR}_n$?

It is possible to check $a \in \mathrm{QR}_p \text{ iff } a^{(p-1)/2} \equiv 1\ (\bmod\ p)$ if $p$ is a prime.

$n$ is a large RSA modulus. Is it also possible to check if $a \in \mathrm{QR}_n$ if the factorization of $n$ is unknown?

It is possible to check $a \in \mathrm{QR}_p \text{ iff } a^{(p-1)/2} \equiv 1\ (\bmod\ p)$ if $p$ is a prime.

Yes, you have already written down the check, which is known as Euler's criterion.

$n$ is a large RSA modulus. Is it also possible to check if $a \in \mathrm{QR}_n$ if the factorization of $n$ is unknown?

You can use the Jacobi symbol if the factorization is unknown to find out if $a\in \mathrm{QNR}_n$, i.e., if the Jacobi symbol is $-1$.

But if the Jacobi symbol yields $+1$, then you can either have a quadratic residue or a pseudosquare, i.e., a quadratic non-residue yielding Jacobi symbol $+1$.

Distinguishing pseudosquares from quadratic residues modulo an RSA modulus if the factorization is unknown is known as the quadratic residuosity problem which is believed to be a hard problem and is the basis for some cryptographic constructions such as the Goldwasser-Micali encryption scheme.

For generic algorithms this problem can be shown to be equivalent to factoring.

• "you have already written down the check" $\:$ More accurately, DrLecter has written in the check. $\hspace{.87 in}$ – user991 Jan 13 '14 at 23:10
• I was not sure if this was sloppy formatting or not :) – DrLecter Jan 13 '14 at 23:17
• @DrLecter But since the adversary knows that $Jacobi(a)=1$ it means that there exists for sure $y$ such that $y^2=x \mod n$. So adversary can decide whethera has QR since it known that $a \in \{\mathbb{J}=1\}$ – curious May 12 '15 at 16:45
• @curious (I guess a should be y?a) No, we are talking about composites which are hard to factor not primes. If the Jacobi is 1 it could still be a non-square (a pseudo-square). – DrLecter May 13 '15 at 6:21

DrLecter's answer is right. But here I just to give a supplementary answer to this question. If we consider this problem in signed quadratic residues ,then it is the other way around.signed quadratic residues is defined as $$\mathbb{QR}_N^+=\{|x|:x\in\mathbb{QR}_N\}$$ where $|x|$ is the absolute value of $x$, and is represented as a signed integer in the set $\{-(N-1)/2,\dots,(N-1)/2\}$.Because when we consider the membership in this group, we can use this relationship $\mathbb{QR}_N^+=\mathbb{J}_N^+=\mathbb{J}_N \cap[(N-1)/2]$($\mathbb{J}_N$ denotes the subgroup of $\mathbb{Z}_N^*$ with Jacobi symbol $+1$ and $\mathbb{J}_N^+=\{|x|:x\in\mathbb{J}_N\}$ ) to check if $a \in \mathbb{QR}_N^+$ even if the factorization of $N$ is unknown.So, this offer a solution if you have to check $a \in \mathbb{QR}_N$.

For details, you may refer to the original paper in here