Алгоритм Корначчи (Glikjnmb Tkjugccn)

Алгоритм Корначчи — это алгоритм решения диофантова уравнения $x^{2}+dy^{2}=m$, где $1\leq d<m$, а d и m взаимно просты. Алгоритм описал в 1908 Джузеппе Корначчи.

Алгоритм

Сначала находим любое решение $r_{0}^{2}\equiv -d{\pmod {m}}$. Если такого $r_{0}$ не существует, исходное уравнение не имеет примитивных решений. Без потери общности можно считать, что $r_{0}\leq {\tfrac {m}{2}}$ (если это не так, заменим r₀ на m - r₀, которое остаётся корнем из -d). Теперь используем алгоритм Евклида для поиска $r_{1}\equiv m{\pmod {r_{0}}}$, $r_{2}\equiv r_{0}{\pmod {r_{1}}}$ и так далее. Останавливаемся, когда $r_{k}<{\sqrt {m}}$. Если $s={\sqrt {\tfrac {m-r_{k}^{2}}{d}}}$ является целым числом, то решением будет $x=r_{k},y=s$. В противном случае примитивного решения нет.

Для поиска непримитивных решений (x, y), где НОД(x, y) = g ≠ 1, заметим, из существования такого решения следует, что g² делит m (и, эквивалентно, что если m является свободным от квадратов, то все решения примитивны). Тогда вышеприведённый алгоритм можно использовать для поиска примитивного решения (u, v) уравнения $u^{2}+dv^{2}={\tfrac {m}{g^{2}}}$. Если такое решение найдено, то (gu, gv) будет решением исходного уравнения.

Пример

Решаем уравнение $x^{2}+6y^{2}=103$. Квадратный корень из −6 (mod 103) равен 32 и 103 ≡ 7 (mod 32). Поскольку $7^{2}<103$ и ${\sqrt {\tfrac {103-7^{2}}{6}}}=3$, существует решение x = 7, y = 3.

Ссылки

Basilla, Julius Magalona On Cornacchia's algorithm for solving the diophantine equation $u^{2}+dv^{2}=m$  (неопр.) (PDF) (12 мая 2004).