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.