Пример. Возьмём $D=61$. Ненулевое (фундаментальное) решение известное и «необычно большое»:
$$x_1=1766319049,y_1=226153980,$$ потому что
$$1766319049^2-61\cdot 226153980^2=1.$$
Метод нахождения бесконечной последовательности решений (кратко и формально).
1) Нахождение фундаментального решения через цепную дробь корня. Разложите $\sqrt{D}$ в периодическую непрерывную цепную дробь
$$\sqrt{D}=[a_0;(a_1,a_2,\dots ,a_k)],$$ где $k$ — длина периода. Пусть $p_n/q_n$ — n-ая приближённая дробь (сходящаяся). Тогда фундаментальное решение $(x_1,y_1)$ даётся так:
- если $k$ чётно, то $(x_1,y_1)=(p_{k-1},q_{k-1})$;
- если $k$ нечётно, то $(x_1,y_1)=(p_{2k-1},q_{2k-1})$.
(Идея: продолжение периода один или два раза даёт подходящую приближающую дробь, которая удовлетворяет уравнению.)
2) Генерация всех решений. Если найдено фундаментальное решение $x_1+y_1\sqrt{D}$, то все положительные целые решения получаются степенями этого юнита в поле $\mathbb{Q}(\sqrt{D})$:
$$x_n+y_n\sqrt{D}=(x_1+y_1\sqrt{D}{)}^n,n=1,2,3,\dots$$ Эквивалентно рекуррентно:
$$x_{n+1}=x_1{x}_n+D{y}_1{y}_n,y_{n+1}=x_1{y}_n+y_1{x}_n,$$ или через матрицу
$$\left(\begin{array}{cc}{x}_n& D{y}_n\\ y_n& x_n\end{array}\right)={\left(\begin{array}{cc}{x}_1& D{y}_1\\ y_1& x_1\end{array}\right)}^n.$$
Как меняется сложность при различном $D$ (кратко).
- Ключевой параметр — длина периода $k$ цепной дроби $\sqrt{D}$ и величина фундаментального юнита $x_1+y_1\sqrt{D}$. Если $k$ маленькое, то обычно $x_1,y_1$ небольшие (напр., $D=2$: $(x_1,y_1)=(3,2)$; $D=3$: $(2,1)$; $D=5$: $(9,4)$). Если $k$ большое (или нечётное и требует удвоения периода), то $x_1,y_1$ могут быть очень большими — как в примере $D=61$.
- Вычислительная стоимость: получение цепной дроби до периода требует порядка $O(k)$ шагов, но числа в шаге растут до размера порядка числа цифр $x_1$. Поэтому реальная сложность определяется (i) длиной периода $k$ и (ii) стоимостью операций с большими целыми числами (умножение/деление больших целых). При простых алгоритмах время примерно пропорционально $k$ умножённому на стоимость арифметики с числом длины $N$ (где $N$ — число десятичных цифр $x_1$).
- Поведение «в худшем случае»: для некоторых $D$ фундаментальное решение экспоненциально велико по отношению к $\sqrt{D}$ (существуют примеры с очень большими $x_1$), поэтому вычисления становятся тяжёлыми. Нет простого формулы для размера $x_1$ в терминах $D$; поведение весьма вариативно и связано с арифметикой квадратичного поля (регулятор, класс-группа).
- Практические ускорения: быстрое целочисленное умножение, алгоритмы для цепных дробей квадратичных иррациональностей, использование модульных и блоковых методов, методы в теории идеалов в $\mathbb{Q}(\sqrt{D})$ — всё это существенно снижает время на большие $D$.
Короткое резюме: метод — вычислить периодическую цепную дробь $\sqrt{D}$, взять соответствующую сходящуюся дробь как фундаментальное решение, затем возводить в степени для получения всех решений. Сложность сильно зависит от длины периода и от величины фундаментального решения; для некоторых $D$ (например, $61$) фундаментальное решение чрезвычайно велико, что делает вычисления ресурсоёмкими.