What is the most computationally efficient way to check, given $x,y,D$ that they satisfy Pell's equation (positive or negative) ($x^2-Dy^2=1$)? (Obviously the question is concerned with very large values of $x,y,D$.)

I know (I think) that it'll have to be checking mod $p$ but I just can't find the right balance between computation time required for factorizing $x,y$ or $D$ and brute-force calculations.

Update: What I said about mod $p$ had to do with the fact that I thought that with Pell especially there might be some computationally efficient way to get a distinguished set of primes (and then the question was how best to balance the 'finding' with the moding) - but as Carnahan indicates the case might not be more special than that of evaluating any binomial. I think I'm pretty much covered by what Carnahan says, though I would be interested to know how these bounds on the number of operations are obtained. Also does it really follow that there is no more efficient way to evaluate a 'close' possible triple (i.e. one that has passed a mod-small-prime or log test) than to use multiplication algorithms? Is that obvious?