What is computational complexity for computing integral solution of Pell equation .It seems to be in P ,and could any one give an algorithm and reference for proof of it's complexity?


And more,could any one give reference for computational complexity for computing integral solution for computable Diophantine equations that have been studied?Thanks.



Computational complexity of solution of Pell equation and more
Given positive integers $a,b,c$, the problem of deciding whether there are positive integers $x,y$ such that $ax^2+by=c$ is NP-complete. This is entry [AN8] on page 250 of Garey and Johnson, Computers and Intractability, where it is attributed to Manders and Adleman, NP-complete decision problems for binary quadratics, J Comput System Sci 16 (1978) 168-184. There is some discussion in the book, and a further reference to Gurari and Ibarra, An NP-complete number theoretic problem, Proc 10th Ann ACM Symp on Theory of Computing (1978) 205-215. 


