Cornacchia's algorithm

In computational number theory, Cornacchia's algorithm is an algorithm for solving the Diophantine equation ${\displaystyle x^{2}+dy^{2}=m}${\displaystyle x^{2}+dy^{2}=m}, where ${\displaystyle 1\leq d<m}${\displaystyle 1\leq d<m} and d and m are coprime. The algorithm was described in 1908 by Giuseppe Cornacchia.^[1]

First, find any solution to ${\displaystyle r_{0}^{2}\equiv -d{\pmod {m}}}${\displaystyle r_{0}^{2}\equiv -d{\pmod {m}}} (perhaps by using an algorithm listed here); if no such ${\displaystyle r_{0}}${\displaystyle r_{0}} exist, there can be no primitive solution to the original equation. Without loss of generality, we can assume that r₀ ≤ ⁠m/2⁠ (if not, then replace r₀ with m - r₀, which will still be a root of -d). Then use the Euclidean algorithm to find ${\displaystyle r_{1}\equiv m{\pmod {r_{0}}}}${\displaystyle r_{1}\equiv m{\pmod {r_{0}}}}, ${\displaystyle r_{2}\equiv r_{0}{\pmod {r_{1}}}}${\displaystyle r_{2}\equiv r_{0}{\pmod {r_{1}}}} and so on; stop when ${\displaystyle r_{k}<{\sqrt {m}}}${\displaystyle r_{k}<{\sqrt {m}}}. If ${\displaystyle s={\sqrt {\tfrac {m-r_{k}^{2}}{d}}}}${\displaystyle s={\sqrt {\tfrac {m-r_{k}^{2}}{d}}}} is an integer, then the solution is ${\displaystyle x=r_{k},y=s}${\displaystyle x=r_{k},y=s}; otherwise try another root of -d until either a solution is found or all roots have been exhausted. In this case there is no primitive solution.

To find non-primitive solutions (x, y) where gcd(x, y) = g ≠ 1, note that the existence of such a solution implies that g² divides m (and equivalently, that if m is square-free, then all solutions are primitive). Thus the above algorithm can be used to search for a primitive solution (u, v) to u² + dv² = ⁠m/g²⁠. If such a solution is found, then (gu, gv) will be a solution to the original equation.

Solve the equation ${\displaystyle x^{2}+6y^{2}=103}${\displaystyle x^{2}+6y^{2}=103}. A square root of −6 (mod 103) is 32, and 103 ≡ 7 (mod 32); since ${\displaystyle 7^{2}<103}${\displaystyle 7^{2}<103} and ${\displaystyle {\sqrt {\tfrac {103-7^{2}}{6}}}=3}${\displaystyle {\sqrt {\tfrac {103-7^{2}}{6}}}=3}, there is a solution x = 7, y = 3.

• Basilla, J. M. (2004). "On the solutions of ${\displaystyle x^{2}+dy^{2}=m}${\displaystyle x^{2}+dy^{2}=m}" (PDF). Proc. Japan Acad. 80(A): 40–41. doi:10.3792/pjaa.80.40 .

• Number theoretic algorithms

• Articles with short description
• Short description is different from Wikidata
• CS1: long volume value