2
$\begingroup$

The paper "The Knowledge Complexity of Interactive Proof Systems" uses the language of quadratic nonresidues defined via the following excerpt from page 293 as an example of constructing an interactive proof system.

Example 1: Let $Z_m^*$ denote the set of integers between $1$ and $m$ that are relatively prime with $m$. An element $a \in Z_m^*$ is a quadratic residue mod $n$ [sic] if $ a = x^2 \mod{m}$ for some $x \in Z_m^*$, else it is a quadratic nonresidue. Now let $L = \{(m, x) | x \in \mathbb{Z}_m^* \text{is a quadratic nonresidue\}}$. Notice that $L \in \textbf{NP}$: a prover needs only to compute the factorization of $m$ and send it to the verifier without any further interaction.

Given that $n$ is not defined in the context of the example, I assume this to be a typo and that the authors meant $m$. My question is about the last sentence. The authors provide no further detail afterwards about what the verifier would do with this factorization to verify quadratic nonresiduosity. In pursuit of more details, I cracked open Arora-Barak where the following treatment of the above is given in section 8.1 example 8.9.

Here is another example for an interactive proof for a language not known to be in $\textbf{NP}$. We say that a number $a$ is a quadratic residue mod $p$ if there is another number $b$ such that $a \cong b^2 \mod{p}$. Such a $b$ is called the square root of $a \mod{p}$. ... the language QNR of pairs $(a, p)$ such that $p$ is a prime and $a$ is not a quadratic residue modulo $p$ has no natural short membership proof and is not known to be in $\textbf{NP}$. But it does have a simple interactive proof if the verifier is probabilistic.

Now if the language QNR described in Arora-Barak is not in $\textbf{NP}$, how could its "superset" the language $L$ described in the paper be in $\textbf{NP}$? If the paper is correct then we could easily construct a verifier which would prove that QNR is in $\textbf{NP}$: for any $(a, p)$ the certificate would consist of the certificate of the membership of $(p, a)$ in $L$ in addition to a certificate for the primality of $p$.

$\endgroup$
4
$\begingroup$

When the modulus is a prime $p$, you can compute quadratic residuosity in polynomial time using the Legendre symbol: $x$ is a quadratic residue mod $p$ iff $(x|p)=1$ or $0$.

When the modulus is a prime power $p^\alpha$, then you can do the same: I believe $x$ is a quadratic residue mod $p^\alpha$ iff $(x|p)=1$ or $0$. I believe this can be proven using Hensel lifting.

When the modulus is a number $n$ with known prime factorization $n=p_1^{\alpha_1} \cdots p_k^{\alpha_k}$, you can use the Chinese remainder theorem: $x$ is a quadratic residue mod $n$ iff it is a quadratic residue mod $p_i$ for all prime factors $p_i$ of $n$.

This means that quadratic nonresiduosity mod $n$ can be computed in polynomial time when the factorization of $n$ is known or given. This also means that, as far as I can see, the language QNR should be in NP: a natural certificate is a prime $p$ that divides $n$, and such that $(a|p)=-1$. The verifier can verify that $p$ is prime in polynomial time and compute the Legendre symbol $(a|p)$ in polynomial time. At least, that's how it seems to me.

I don't know why Arora-Barak say that QNR is not known to be NP. This makes me suspect that I may have misunderstood something, as they know way more about computational complexity than I do.

$\endgroup$
5
  • $\begingroup$ So Arora-Barak is wrong? $\endgroup$
    – kotu
    May 25 at 22:49
  • 2
    $\begingroup$ @kotu, I don't know. Arora and Barak know way more than me, so if my impression is contrary to them, I'm inclined to think it's more likely that I've misunderstood something than that they got something wrong. Depending on how old your copy of the book is, perhaps it was written before the proof that PRIMES is in P, in which case everything they write makes sense; my answer basically argues that the problem is in NP, and relies upon the fact that PRIMES is in P: the witness is a prime $p$ that divides $n$, and the verifier must verify that $p$ is a prime. $\endgroup$
    – D.W.
    May 25 at 23:03
  • $\begingroup$ I appreciate you taking the time to answer regardless. In the "chapter notes and history" section of chapter 7 in my book they refer to the paper which proved PRIMES is in P, so now I'm just more confused =P $\endgroup$
    – kotu
    May 25 at 23:10
  • 1
    $\begingroup$ @kotu, got it, thank you. I'm confused, too. I hope someone here who knows more computational complexity than I will be able to help us clear this up. $\endgroup$
    – D.W.
    May 26 at 0:10
  • 1
    $\begingroup$ I just sent an email to an account that the authors maintain for improvements to the book. I'll provide an update here if they ever respond. $\endgroup$
    – kotu
    May 26 at 1:04

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.