Given $a,b,c>0$, is there a procedure to solve $(x,y)\in\Bbb Z:ax^2+by^2=c$ in $O(\log^d c)$ arithmetic operations (either randomized or deterministic) with $d>0$ being fixed?

Is there a connection to Pell's equation?

Also wolfram http://mathworld.wolfram.com/MethodofExclusions.html says Gauss had a method. I am unable to find a reference talking about this method.

  • 1
    $\begingroup$ people.math.carleton.ca/~williams/papers/pdf/165.pdf $\endgroup$ – Will Jagy Apr 1 '15 at 4:19
  • $\begingroup$ Thank you very much. So we do not have one. wolfram says Gauss had a method of exclusions for this exact equation. However I am unable to locate a reference. Would you by any chance know about? $\endgroup$ – T.... Apr 1 '15 at 4:28
  • 1
    $\begingroup$ looking in Dickson's History, it seems likely that this refers to an indefinite form, that is your $ab < 0.$ The method is the one i have answered with, over and over, on MSE for Pell and similar equations. Meanwhile, I think the Disquisitiones has been translated, the two mentions in the History are Article 195 and Article 323, where the phrase "method of exclusions" goes with 323. Note that the positive form case and indefinite are completely different in terms of solving such problems. $\endgroup$ – Will Jagy Apr 1 '15 at 17:08
  • $\begingroup$ Oic if a,b>0, then this paper is possibly only method sofar? $\endgroup$ – T.... Apr 1 '15 at 20:27
  • $\begingroup$ This doesn't answer your main question, but for reference on Gauss' Method of Exclusions I found an old 1928 write-up here: cr.yp.to/bib/1928/lehmer.pdf ...complete with a chain-and-sprocket mechanism for performing it :-D $\endgroup$ – user253804 Jul 11 '15 at 4:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.