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

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

АлгоритмПравить

Сначала находим любое решение $r_0^2\equiv <!--\; \equiv \; -->-<!--\; -\; -->d(\mathrm{mod}m)$$r_{0}^{2}\equiv -d{\pmod {m}}$ . Если такого $r_0$$r_{0}$  не существует, исходное уравнение не имеет примитивных решений. Без потери общности можно считать, что $r_0\le <!--\; \le \; -->\frac{m}{2}$$r_{0}\leq {\tfrac {m}{2}}$  (если это не так, заменим r₀ на m - r₀, которое остаётся корнем из -d). Теперь используем алгоритм Евклида для поиска $r_1\equiv <!--\; \equiv \; -->m(\mathrm{mod}{r}_0)$$r_{1}\equiv m{\pmod {r_{0}}}$ , $r_2\equiv <!--\; \equiv \; -->r_0(\mathrm{mod}{r}_1)$$r_{2}\equiv r_{0}{\pmod {r_{1}}}$  и так далее. Останавливаемся, когда $r_{k}<{\sqrt {m}}$ . Если $s=\sqrt{\frac{m-<!--\; -\; -->r_k^2}{d}}$$s={\sqrt {\tfrac {m-r_{k}^{2}}{d}}}$  является целым числом, то решением будет $x=r_k,y=s$$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}$$u^{2}+dv^{2}={\tfrac {m}{g^{2}}}$ . Если такое решение найдено, то (gu, gv) будет решением исходного уравнения.

ПримерПравить

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

СсылкиПравить

Basilla, Julius Magalona On Cornacchia's algorithm for solving the diophantine equation $u^2+d{v}^2=m$$u^{2}+dv^{2}=m$   (неопр.) (PDF) (12 мая 2004).