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

Алгоритм Корначчи — это алгоритм решения диофантова уравнения x2+dy2=m, где $1\le dd и m взаимно просты. Алгоритм описал в 1908 Джузеппе Корначчи.

Алгоритм


 Сначала находим любое решение r02d(modm). Если такого r0 не существует, исходное уравнение не имеет примитивных решений. Без потери общности можно считать, что r0m2 (если это не так, заменим r0 на m - r0, которое остаётся корнем из -d). Теперь используем алгоритм Евклида для поиска r1m(modr0), r2r0(modr1) и так далее. Останавливаемся, когда rk<m. Если s=mrk2d является целым числом, то решением будет x=rk,y=s. В противном случае примитивного решения нет.
 Для поиска непримитивных решений (x, y), где НОД(x, y) = g ≠ 1, заметим, из существования такого решения следует, что g2 делит m (и, эквивалентно, что если m является свободным от квадратов, то все решения примитивны). Тогда вышеприведённый алгоритм можно использовать для поиска примитивного решения (u, v) уравнения u2+dv2=mg2. Если такое решение найдено, то (gu, gv) будет решением исходного уравнения.

Пример


 Решаем уравнение x2+6y2=103. Квадратный корень из −6 (mod 103) равен 32 и 103 ≡ 7 (mod 32). Поскольку 72<103 и 103726=3, существует решение x = 7, y = 3.