Programming ECC - Pell Equations

Pell Equations

For details see my notes on Pell equations.

Suppose we wish to solve

x^{2} - D y^{2} = 1

where $D$ is not a square. First we compute the continued fraction expansion of $\sqrt{D}$ .

\begin{matrix} P_{0} & = & 0 \\ Q_{0} & = & 1 \\ a_{0} & = & ⌊ \sqrt{D} ⌋ \\ P_{1} & = & a_{0} \\ Q_{1} & = & D - a_{0}^{2} \\ a_{n} & = & ⌊ \frac{a_{0} + P_{n}}{Q_{n}} ⌋ \\ P_{n} & = & a_{n - 1} Q_{n - 1} - P_{n - 1} \\ Q_{n} & = & \frac{D - P_{n}^{2}}{Q_{n - 1}} \end{matrix}

Then the continued fraction expansion of $\sqrt{D}$ is

\sqrt{D} = [a_{0}; a_{1}, . . ., a_{k + 1}, a_{1}, . . ., a_{k + 1}, . . .]

It turns out $a_{k + 1} = 2 a_{0}$ .

The convergents are computed by

\begin{matrix} p_{0} & = & a_{0} \\ p_{1} & = & a_{0} a_{1} + 1 \\ p_{n} & = & a_{n} p_{n - 1} + p_{n - 2} \\ q_{0} & = & 1 \\ q_{1} & = & a_{1} \\ q_{n} & = & a_{n} q_{n - 1} + q_{n - 2} \end{matrix}

The convergents satisfy

p_{n}^{2} - D q_{n}^{2} = (- 1)^{n + 1} Q_{n + 1}

and $(x, y) = (p_{k}, q_{k})$ is the smallest integer solution of the Pell equation for odd $k$ , and $(x, y) = (p_{2 k + 1}, q_{2 k + 1})$ if $k$ is even. From a minimal positive solution $(t, u)$ , we may generate the other positive solutions $(x, y)$ via

x + y \sqrt{D} = (t + u \sqrt{D})^{n}

for all positive $n$ .

Generalized Pell Equations

Now consider the equation

x^{2} - D y^{2} = N

If $N^{2} < D$ we may do the following. Compute the convergents $p_{n}, q_{n}$ until the smallest integer solution of the Pell equation $x^{2} - D y^{2} = 1$ is found. In the meantime, check if each $p_{n}, q_{n}$ satisfies $p_{n}^{2} - D q_{n}^{2} = N / f^{2}$ for some $f > 0$ . If so, append $(f p_{n}, f q_{n})$ to the list of solutions.

We now use this list of solutions to generate all other solutions. If $(r, s)$ is on the list, and $(t, u)$ is a minimal positive solution of the corresponding Pell equation, then we have a family of solutions $(x, y)$ given by

x + y \sqrt{D} = (r + s \sqrt{D}) (t + u \sqrt{D})^{n}

for all positive $n$ .

If $N^{2} \geq D$ then one possibility is brute force. If $N > 0$ set $L_{1} = 0, L_{2} = \sqrt{N (t - 1) / 2 D)}$ , otherwise set $L_{1} = \sqrt{- N / D}, L_{2} = \sqrt{- N (t + 1) / (2 D)}$ . For $L_{1} \leq y \leq L_{2}$ check if $N + D y^{2} = x^{2}$ for some integer $x$ . If so, then append $(x, y)$ to the list of fundamental solutions. Also append $(- x, y)$ if not equivalent to $(x, y)$ . (TODO: can avoid since we don’t want negative solutions?) Then proceed as above to generate all solutions.