Алгоритм Корначчи

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

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

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

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

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