[Math] Most efficient checking algorithm for Pell’s Equation

computational-number-theorynt.number-theory

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?

Best Answer

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.

Related Question