Is quadratic nonresiduosity in $\textbf{NP}$?

Question

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$.

Answer 1

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.