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.
First, find any solution to (perhaps by using an algorithm listed here); if no such exist, there can be no primitive solution to the original equation. Without loss of generality, we can assume that (if not, then replace with , which will still be a root of ). 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 (and equivalently, that if is square-free, then all solutions are primitive). 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.
Solve the equation . A square root of −6 (mod 103) is 32, and 103 â¡ 7 (mod 32); since and , there is a solution x = 7, y = 3.