Cornacchia's algorithm


In computational number theory, Cornacchia's algorithm is an algorithm for solving the Diophantine equation, where and d and m are coprime. The algorithm was described in 1908 by Giuseppe Cornacchia.

The algorithm

First, find any solution to ; if no such exist, there can be no primitive solution to the original equation. Without loss of generality, we can assume that . Then use the Euclidean algorithm to find, and so on; stop when. If is an integer, then the solution is ; otherwise try another root of 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 where, note that the existence of such a solution implies that divides . Thus the above algorithm can be used to search for a primitive solution to. If such a solution is found, then will be a solution to the original equation.

Example

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