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

The algorithm

First, find any solution to (perhaps by using an algorithm listed here); if no such r_0 exist, there can be no primitive solution to the original equation. Without loss of generality, we can assume that r0 ≤ m⁄2 (if not, then replace r0 with m - r0 , which will still be a root of -d ). Then use the Euclidean algorithm to find, and so on; stop when r_k<\sqrt m. If is an integer, then the solution is 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 g2 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 u2 + dv2 = m⁄g2 . If such a solution is found, then (gu, gv) will be a solution to the original equation.

Example

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