In Reutenauer's "Free Lie Algebras", section 7.6.2:
A direct bijection between primitive necklaces of length $n$ over $F$ and the set of irreducible polynomials of degree $n$ in $F[x]$ may be described as follows: let $K$ be the field with $q^n$ elements; it is a vector space of dimension $n$ over $F$, so there exists in $K$ an element $\theta$; such that the set $\{\theta, \theta^q, ..., \theta^{q^{n-1}}\}$ is a linear basis of $K$ over $F$.
With each word $w = a_0\cdots a_{n-1}$ of length $n$ on the alphabet $F$, associate the element $\beta$ of $K$ given by $\beta = a_0\theta + a_1\theta^q + \cdots + a_{n-1} \theta^{q^{n-1}}$. It is easily shown that to conjugate words $w, w'$ correspond conjugate elements $\beta, \beta'$ in the field extension $K/F$, and that $w \mapsto \beta$ is a bijection. Hence, to a primitive conjugation class corresponds a conjugation class of cardinality $n$ in $K$; to the latter corresponds a unique irreducible polynomial of degree $n$ in $F[x]$. This gives the desired bijection.
Based on the comments, it looks like this is not a question specific to Pell's equation, and that you just want to evaluate a single binomial with big inputs as quickly as possible.
If you check the equation directly using fast multiplication algorithms (e.g., Schönhage-Strassen), you can expect the calculation to require about $(\log z )\cdot (\log \log z)$ operations, where $z = \max \{ x, y, D \}$.
If you want a way to quickly find a negative answer, you can check relative sizes and leading digits, then try reduction modulo small integers. If you start with a random negative answer, you can expect it to be eliminated after at most a few divisions (i.e., about $\log z$ operations).
To find a positive answer using modular arithmetic, you can use the Chinese remainder theorem. To prove that the identity holds, it suffices to check it modulo $n$, for $n$ ranging over a collection of positive integers whose least common denominator is larger than $x^2$ and $Dy^2$. It is common to check modulo a large collection of small primes, and this will require about $\log z$ primes and $(\log z)^2$ operations. Another natural choice with a binary computer is Fermat numbers, of the form $2^{2^n}+1$, since the division-with-remainder can be optimized - this ends up looking a lot like direct calculation.
In summary, the advantage of checking modulo small primes is that it lets you quickly eliminate negative answers, and the disadvantage is that (if I'm not mistaken) it is roughly quadratically slower than direct calculation when you have a positive answer. You can choose your method depending on exactly what sort of calculation you plan to do.
Best Answer
Google provides an answer to this question. The first deterministic polynomial time algorithm for this is due to H. W. Lenstra, Jr., in his paper "Finding isomorphisms between finite fields" (Mathematics of Computation, v. 56 (1991), 329-347). Another algorithm appears in the paper by B. Allombert, "Explicit computation of isomorphisms between finite fields" (Finite Fields and their Applications, v. 8 (2002), 332-342). However, the latter paper does not describe the running time of its algorithm, beyond saying that it is fast. An excellent survey of algorithms in number theory is H. W. Lenstra, Jr., "Algorithms in algebraic number theory" (Bulletin of the American Mathematical Society, v. 26 (1992), 211-244). Although it was written 25 years ago, still this is well worth reading.