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

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

Алгоритм

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

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

Пример

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