# Computational complexity of solution of Pell equation and more

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.

-

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.

-
,thank you for your answer. – XL _at_China Apr 29 '14 at 3:06
@Bjørn, no --- what I wrote is what it says in Garey and Johnson. – Gerry Myerson Apr 29 '14 at 5:13
Is that a Pell equation or just a simple Diophantine equation? – Bjørn Kjos-Hanssen Apr 29 '14 at 5:16
@Bjørn, I wouldn't call it a Pell equation. It's in reference to the second paragraph of the question XL posted, which was about "computable Diophantine equations" generally. – Gerry Myerson Apr 29 '14 at 5:35
It jumps from p of $ax+by=c$ to NPC of $ax^2+by=c$ – XL _at_China Apr 29 '14 at 9:46

The problem of finding $x$ and $y$ in a given Pell equation $x^2-ny^2=1$ is not known to be solvable in polynomial time, see Wikipedia.

-
,thank you ,It is really strange that computational complexity for so simple a Diophantine equation is still an open problem,And I think it is possibly hopeless to get answer for any other kind of Diophantine equation. – XL _at_China Apr 29 '14 at 2:21
On the other hand, solving Pell's equation is known to be in BQP (that is, to admit a polynomial-time quantum algorithm). See here: cse.psu.edu/~hallgren/pell.pdf – Scott Aaronson Apr 29 '14 at 2:58
And,under GRH,the computational complexity is $$e^{O(log N log log N)}$$,so I intend to believe that GRH is true – XL _at_China Apr 29 '14 at 3:04
@ScottAaronson,thank you,and there is a reference on wiki link to Hall's paper – XL _at_China Apr 29 '14 at 3:12
Pell’s equation is always solvable, so its solvability is most certainly in P. The question is about computing a solution to the equation, which is not a decision problem, but a search problem. So, I don’t even know what’s NP supposed to mean here, but anyway I don’t understand how an exponential lower bound on the number of digits could imply NP-easiness. In fact, if I read NP as TFNP, the fact that the least solution may have superpolynomial length by itself implies the problem is not in TFNP. – Emil Jeřábek Apr 29 '14 at 9:26