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

Алгоритм

Сначала находим любое решение ${\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 (неопр.) (PDF) (12 мая 2004).