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?
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
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.
-
$\begingroup$ "you have already written down the check" $\:$ More accurately, DrLecter has written in the check. $\hspace{.87 in}$ $\endgroup$– user991Jan 13, 2014 at 23:10
-
$\begingroup$ I was not sure if this was sloppy formatting or not :) $\endgroup$– DrLecterJan 13, 2014 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$– curiousMay 12, 2015 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$– DrLecterMay 13, 2015 at 6:21
$\begingroup$
$\endgroup$
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
