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 ; if no such exist, there can be no primitive solution to the original equation. Then use the Euclidean algorithm to find , and so on; stop when . If is an integer, then the solution is ; otherwise there is no solution.
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.
- Cornacchia, G. (1908). "Su di un metodo per la risoluzione in numeri interi dell' equazione .". Giornale di Matematiche di Battaglini 46: 33–90.
Basilla, Julius Magalona (12 May 2004). "On Cornacchia's algorithm for solving the diophantine equation " (PDF).