Русская Википедия:Алгоритм Корначчи

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

Алгоритм

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

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

Пример

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

Литература

• Шаблон:Статья