# Quadratic Diophantine equation - Polynomial Time Cases

In number theory, solving a Quadratic Diophantine equation (a, b, c constants) $$a*x^2+b*y= c$$ is an NP-Complete problem. Even for a=1, the problem remains NP-Complete.

The solution (x, y) are positive integers.

Query: What are the conditions on values of constants for which solving the problem is Polynomially feasible? Any link to the references?

• Do you have a reference for its NP-completeness? – D.W. May 29 '15 at 16:04
• Garey and Johnson. A7.2. [AN8] – TheoryQuest1 May 29 '15 at 16:07
• The requirement that $x,y$ be positive was not present in the initial iteration of the question, and it does change the problem. It's important to state the problem correctly: its complexity can be sensitive to these kinds of details. – D.W. May 29 '15 at 16:08
• True. I missed that part (was wrong to assume that we are implicitly considering positive cases only). – TheoryQuest1 May 29 '15 at 16:17

If $b$ is prime, you can solve this in polynomial time by letting $x = \sqrt{c/a} \pmod{b}$ and then $y=(c-ax^2)/b$. You can compute modular square roots in polynomial time by standard methods.
If $b$ has known factorization, similar methods can be used (use the Chinese remainder theorem).
Dealing with the requirements $x\ge 0,y \ge 0$ (which were added to the question after I wrote this answer) is more challenging. When $b$ is prime, you can enumerate both modular square roots and see if either of them leads to a valid solution. When $b$ is not prime but has known factorization, in the worst case this might require enumerating exponentially many modular square roots (though you might be able to randomly sample a few square roots and hope that at least one will lead to a positive solution).