Return to Answer

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

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.

The problem $B$ given $\alpha, \beta\in\mathbb{N}$, decide $$ \exists x\in\mathbb{N}: x^2\equiv\alpha\bmod\beta $$ has some practical solutions provided $\beta$ is prime. 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.

Since the number of square roots modulo a prime power is at most $2$, deciding the bounded version for $\beta$ a prime power, 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$.

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, while the general $A$ is NP-complete, even with given prime factorization for $\beta$.

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.

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

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 $$ has some practical solutions provided $\beta$ is prime. 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.

Since the number of square roots modulo a prime power is at most $2$, deciding the bounded version for $\beta$ a prime power, 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$.

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, while the general $A$ is NP-complete, even with given prime factorization for $\beta$.

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 $$ has some practical solutions provided $\beta$ is prime. 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.

Since the number of square roots modulo a prime power is at most $2$, deciding the bounded version for $\beta$ a prime power, 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$.

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, while the general $A$ is NP-complete, even with given prime factorization for $\beta$.