Modular square roots problem which is $NP$ hard

Question

It is well known extracting modular square roots modulo a composite number factors the modulus.

On other hand given $u,v>0$ and an integer $n$, deciding if there is a factor of $n$ in $[u,v]$ is $NP$ hard by https://cstheory.stackexchange.com/questions/4769/an-np-complete-variant-of-factoring?rq=1.

Is there a version of modular roots problem which is $NP$ hard?

Answer 1

According to the paper NP-complete decision problems for quadratic polynomials (Thm. 2) by K. Manders and L. Adleman the following problem $A$ is NP-complete thus in particular NP-hard:

Given $\alpha, \beta, \gamma\in\mathbb{N}$, decide $$ \exists x\in[0,\gamma]: x^2\equiv\alpha\bmod\beta. $$

The problem remains NP-complete when a prime factorization of $\beta$ is given.

The complexity of the problem relies on the combination of $\beta$ being potentially arbitrarily composite and the bound $\gamma$.

The problem $B$ given $\alpha, \beta\in\mathbb{N}$, decide $$ \exists x\in\mathbb{N}: x^2\equiv\alpha\bmod\beta, $$ can be solved efficiently by Euler's criterion provided $\beta$ is prime.

For $\beta$ prime there are even practical solutions to explicitly find $x$ and not only decide $B$, which will turn out to be useful for generalizations. E.g. Shank's algorithm or Cipolla's algorithm. Shank's algorithm relies on having a primitive root $\bmod\beta$ and Cipolla's algorithm on finding a quadratic non-residue $\bmod\beta$ of specific type. Both problems are not known to be in P unconditionally, but supposing the Riemann hypothesis finding primitive roots is. Thus the problem is conditionally in P.

Moreover, these algorithms also work for $\beta$ a prime power. For prime powers you could alternatively employ Hensel lifting which works in polynomial time. For composites $\beta$ with known prime factorization you can use Chinese remaindering to combine solutions for the prime power factors to find any (not necessarily bounded) root efficiently.

For $\beta=p^k$ a prime power with $p\neq 2$ and $p\nmid\alpha$ the number of square roots modulo $\beta$ is $2$ or $0$, i.e. at most $2$. Therefore deciding the bounded version in this case, i.e. a restriction of $A$, is also conditionally in P. Since the number of square roots grows in the worst case with $2^m$, where $m$ is the number of distinct prime factors of $\beta$, and each of these $2^m$ square roots can be found efficiently, restricting $A$ to a fixed $m$ is also conditionally in P. However, since $2^m$ grows (in the worst case) superpolynomially in the bit length of $\beta$, this kind of reasoning cannot be applied to the unrestricted $A$.

In the comments Gerry Myerson pointed out that the number of square roots for $\beta=p^k$ a prime power

• when $p\mid\alpha$ can be as large as $2p^{\lfloor k/2\rfloor}$ (e.g. for $k=2\ell+1$ look at $x^2\equiv p^{2\ell}\bmod p^{2\ell+1}$ for $p\neq 2$ and at $x^2\equiv p^{2(\ell-1)}\bmod p^{2\ell+1}$ for $p=2$) and
• when $p=2\nmid\alpha$ can be as large as $4$ (e.g. for $k\geq 3$ look at $x^2\equiv 1\bmod 2^k$),

exceeding the usual $2$. Nevertheless even in these cases the structure of the square roots can be controlled well enough such that restricting $A$ to $\beta$ having at most $m$ distinct prime factors and at most one of them occurs in the prime factorization of $\alpha$ is conditionally in P.

To give an explicit example $$x^2=25^2\bmod 5^9 \Rightarrow \mathbb{L}=\{\pm25+i\cdot 5^7:0\leq i<5^2\}.$$ This structure of arithmetic progression is preserved under Chinese remaindering. $$x^2=25^2\bmod 5^9\cdot 3^2\cdot 7 \Rightarrow \mathbb{L}=\{\pm(25+j\cdot5^7)+i\cdot 5^7\cdot 3^2\cdot 7:j\in\{0,18,35,53\}\wedge 0\leq i<5^2\}.$$ This progression can be used in general to efficiently look for bounded solutions. Since the details become rather technical I leave it at this example.

If however $\beta$ has at most $m$ prime factors and $\alpha$ can have more than one prime factor in common with $\beta$ then deciding if a solution is bounded by $\gamma$ seems to be related to the NP-complete unbounded knapsack problem with fixed number of items $m$. It is not quite the same because of modular arithmetic. If this problem would be fixed parameter tractable in $m$, then the general restricted $A$ would be conditionally in P, but I am ignorant of that. Cf. this preprint for fixed parameter tractability for knapsack problems.

Thus $B$ with given prime factorization for $\beta$ is conditioned on RH in P, so is the restricted version of $A$ where $\beta$ is a prime power resp. has at most a fixed number of distinct prime factors only one of which divides $\alpha$, while the general $A$ is NP-complete, even with given prime factorization for $\beta$.