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

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

Алгоритм


 Сначала находим любое решение r02d(modm). Если такого r0не существует, исходное уравнение не имеет примитивных решений. Безпотери общности можно считать, что r0m2 (если это нетак, заменим r\textsubscript0 на m -r\textsubscript0, которое остаётся корнем из -d). Теперьиспользуем алгоритм Евклида для поиска r1m(modr0),r2r0(modr1) и так далее. Останавливаемся, когдаrk<m. Если s=mrk2d является целым числом,то решением будет x=rk,y=s. В противном случае примитивного решениянет.
 Для поиска непримитивных решений (x, y), где НОД(x,y) = g ≠ 1, заметим, из существования такого решенияследует, что g\textsuperscript2 делит 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.