0

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.

Turbo
  • 6,221
  • 1
    http://people.math.carleton.ca/~williams/papers/pdf/165.pdf – Will Jagy Apr 01 '15 at 04:19
  • 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? – Turbo Apr 01 '15 at 04:28
  • 1
    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. – Will Jagy Apr 01 '15 at 17:08
  • Oic if a,b>0, then this paper is possibly only method sofar? – Turbo Apr 01 '15 at 20:27
  • This doesn't answer your main question, but for reference on Gauss' Method of Exclusions I found an old 1928 write-up here: http://cr.yp.to/bib/1928/lehmer.pdf ...complete with a chain-and-sprocket mechanism for performing it :-D –  Jul 11 '15 at 04:40
  • Also, here's a Google Books excerpt translating part of the relevant section of the Disquisitiones: http://tinyurl.com/pbnhx3z (see bottom half of page). –  Jul 11 '15 at 04:46

0 Answers0