Cornacchia's algorithm

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

The algorithm

First, find any solution to $r_{0}^{2}\equiv -d{\pmod {m}}$; if no such $r_{0}$ exist, there can be no solution to the original equation. Then use the Euclidean algorithm to find $r_{1}\equiv m{\pmod {r_{0}}}$, $r_{2}\equiv r_{0}{\pmod {r_{1}}}$ and so on; stop when $r_{k}<{\sqrt {m}}$. If $s={\sqrt {\tfrac {m-r_{k}^{2}}{d}}}$ is an integer, then the solution is $x=r_{k},y=s$; otherwise there is no solution.

Example

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

External links

Basilla, Julius Magalona (12 May 2004). "On Cornacchia's algorithm for solving the diophantine equation $u^{2}+dv^{2}=m$" (PDF).