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.