3
$\begingroup$

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?

$\endgroup$
0
4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ "you have already written down the check" $\:$ More accurately, DrLecter has written in the check. $\hspace{.87 in}$ $\endgroup$ – user991 Jan 13 '14 at 23:10
  • $\begingroup$ I was not sure if this was sloppy formatting or not :) $\endgroup$ – DrLecter Jan 13 '14 at 23:17
  • $\begingroup$ @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\}$ $\endgroup$ – curious May 12 '15 at 16:45
  • $\begingroup$ @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). $\endgroup$ – DrLecter May 13 '15 at 6:21
1
$\begingroup$

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

$\endgroup$

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.