Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
"you have already written down the check" $\:$ More accurately, DrLecter has written in the check. $\hspace{.87 in}$ –  Ricky Demer Jan 13 at 23:10
    
I was not sure if this was sloppy formatting or not :) –  DrLecter Jan 13 at 23:17
    
Thank you for your good explanation! –  user4811 Jan 14 at 0:16

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.