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

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

Алгоритм

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

Чтобы найти непримитивные решения ( x , y ) , где gcd( x , y ) = g ≠ 1 , обратите внимание, что существование такого решения подразумевает, что g ² делит m (и, что эквивалентно, если m не содержит квадратов , то все решения примитивны). Таким образом, приведенный выше алгоритм можно использовать для поиска примитивного решения ( u , v ) задачи u ² + дв ² = ⁠ м / г ² ⁠ . Если такое решение найдено, то ( gu , gv ) будет решением исходного уравнения.

Пример

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

Внешние ссылки

• Базилла, Дж. М. (2004). «О решениях $x^{2}+dy^{2}=m$( PDF ) . Proc. Japan Acad . 80(A): 40–41.