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

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

Алгоритм

Сначала находим любое решение [math]\displaystyle{ r_0^2\equiv-d\pmod m }[/math]. Если такого [math]\displaystyle{ r_0 }[/math] не существует, исходное уравнение не имеет примитивных решений. Без потери общности можно считать, что [math]\displaystyle{ r_0 \le \tfrac{m}{2} }[/math] (если это не так, заменим r₀ на m - r₀, которое остаётся корнем из -d). Теперь используем алгоритм Евклида для поиска [math]\displaystyle{ r_1\equiv m\pmod{r_0} }[/math], [math]\displaystyle{ r_2\equiv r_0\pmod{r_1} }[/math] и так далее. Останавливаемся, когда [math]\displaystyle{ r_k\lt \sqrt m }[/math]. Если [math]\displaystyle{ s=\sqrt{\tfrac{m-r_k^2}d} }[/math] является целым числом, то решением будет [math]\displaystyle{ x=r_k,y=s }[/math]. В противном случае примитивного решения нет.

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

Пример

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

Ссылки

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