Кратко о задаче. Уравнение Пелля
$$x^2-D{y}^2=1$$ при невырожденном параметре $D$ (не квадрат) имеет бесконечно много целых решений. Все решения порождаются фундаментальным решением $(x_1,y_1)$ (наименьшим по $x>1$):
$$x_n+y_n\sqrt{D}=(x_1+y_1\sqrt{D}{)}^n,n\in \mathbb{Z}.$$
1) Предварительная редукция.
- Если $D=r^{2}d$ с целым $r>1$, то достаточно рассмотреть квадратно-свободный $d$, положив $Y=ry$. То есть всегда можно перейти к квадратно‑свободному $D$.
2) Классический алгоритм (цепные дроби).
- Теорема Лагранжа: цепная дробь $\sqrt{D}=[a_0;\overline{a_1,\dots ,a_{\ell }}]$ периодична. Пусть $p_k/q_k$ — k‑ая сокращённая дробь (convergent).
- Правило для фундаментального решения:
- если длина периода $\ell$ чётна, то $(x_1,y_1)=(p_{\ell -1},q_{\ell -1})$;
- если $\ell$ нечётна, то $(x_1,y_1)=(p_{2\ell -1},q_{2\ell -1})$.
- Алгоритм: поочерёдно вычислять частные цепной дроби $(a_i)$ для $\sqrt{D}$ до получения требуемого convergent; вернуть соответствующий $p,q$.
Короткое обоснование: периодичность даёт равенства вида $p_k^2-D{q}_k^2=\pm 1$; парность периода определяет знак и нужный индекс.
3) Альтернативы и практические методы.
- метод Чакрава́лы (индийский алгоритм) — часто быстро на практике, гибок и экономит память;
- алгоритмы в теории алгебраических чисел (инфраструктура полей, алгоритмы Хафнера—МакКьюли, Бухманна) — вычисляют фундаментальную единицу/регулятор в реальном квадратичном поле; дают субэкспоненциальную (эвристическую) сложность $L_{|D|}(1/2,\cdot )$ и применимы для очень больших $D$.
4) Сложность и поведение по $D$.
- Входной размер $n$ обычно измеряется как число бит в $D$, т.е. $n\approx \log D$.
- Проблема: число бит в $x_1$ (и в промежуточных convergents) может быть экспоненциальным по отношению к $n$. Поэтому алгоритм цепных дробей в худшем случае требует времени и памяти, экспоненциальных по $n$ (потому что нужно обработать числа длины $\approx \log x_1$).
- На практике для большинства $D$ фундаментальное решение невелико и цепные дроби очень эффективны. Но существуют «плохие» $D$ с огромными $x_1$ (классический пример: $D=61$ даёт очень большое $x_1$), что делает задачу вычислительно тяжёлой.
- Современные алгоритмы (Hafner–McCurley, Buchmann) дают вычисление фундаментальной единицы в субэкспоненциальное время в среднем/эвристически, что практично для больших $D$.
5) Как свойства $D$ влияют на сложность (качественно).
- Структура разложения на простые влияет на арифметику в поле $\mathbb{Q}(\sqrt{D})$: как простые «расщепляются» (квадратичная вычетность) определяет арифметику идеалов, класс‑группу и регулятор.
- Регулятор $R$ связан с модулем фундаментальной единицы через $\log (x_1+y_1\sqrt{D})\approx R$. Большой регулятор → большой $x_1$ → сложнее вычисление.
- Класс‑число $h(D)$ и поведение простых (разложение в поле) косвенно влияют на период цепной дроби и размер единиц. Часто небольшие класс‑числа коррелируют с «небольшими» решениями, но строгой простой связи нет — поведение нерегулярно.
- Некоторые арифметические семейства $D$ (специальные формы, произвольные квадратичные вычеты) дают обычно короткие периоды и малые решения; другие дают длинные периоды и экспоненциально большие решения. Нет простого критерия через факторизацию $D$, который бы гарантировал малую/большую сложность во всех случаях.
6) Практические рекомендации.
- Для умеренных $D$ (до тысяч/десятков тысяч бит) начать с алгоритма цепных дробей или Чакравалы.
- Для очень больших $D$ использовать алгоритмы регулятора/единиц (Buchmann и др.), реализованные в компьютерных алгебраических системах.
- Если нужен только факт существования решений/проверка малых решений, можно комбинировать локальные критерии (решаемость по модулю малых простых) и ограничение поиска.
Короткое резюме: фундаментальное решение находится через периодическую цепную дробь $\sqrt{D}$ (или альтернативно через Chakravala/алг. теории чисел). Алгоритмическая сложность сильно зависит от размера фундаментальной единицы (регулятора); он может быть экспоненциально большим по входному размеру, поэтому в худшем случае задача требует экспоненциальных ресурсов, но для многих $D$ стандартные методы работают эффективно.