Consider an equation of the form:


where A-F are integer coefficients (binary quadratic Diophantine equation). I consider here the most general form, so assume all coefficients are non-zero.

Is there an efficient algorithm which can compute integer solutions for this type of equation?

  • 1
    $\begingroup$ mathoverflow.net/questions/142938/… $\endgroup$ – adrianN Oct 5 '16 at 10:04
  • $\begingroup$ Did you google? $\endgroup$ – adrianN Oct 5 '16 at 10:06
  • $\begingroup$ That post is not exactly the answer for the question. Yes, I did google it (great piece of advice BTW, seriously). Finally I found the answer here: google.pl/…. As for now indeed such algorithms exist, but for general form of BQDE the integer solution can be found in exponential time. $\endgroup$ – plktrautman Oct 5 '16 at 10:18
  • $\begingroup$ You should write an answer to your own question then :) $\endgroup$ – adrianN Oct 5 '16 at 10:44
  • $\begingroup$ For the future, if you know of a resource that answers a related question but doesn't quite answer the question, it would be better to explain in the question what you've found and why it's not quite what you were looking for. Approaching this from the perspective of sharing knowledge and background makes your question more interesting and useful to others. $\endgroup$ – D.W. Oct 5 '16 at 17:05

Yes, such algorithms exist, i.e., if only BDQE has integer solutions, then those solutions can be found computationally, however - in exponential time. There is no polynomial time algorithm to tackle it in the general form (at least on a classical, non-quantum computer).

There's more information in Jeff Lagarias's slides for his talk Complexity of Diophantine Equations.

| cite | improve this answer | |

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.