Cornacchia's algorithm

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.^[1]

The algorithm

First, find any solution to $r_0^2\equiv-d\pmod m$ (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 r₀ ≤ m/2 (if not, then replace r₀ with m - r₀, which will still be a root of -d). Then use the Euclidean algorithm to find $r_1\equiv m\pmod{r_0}$, $r_2\equiv r_0\pmod{r_1}$ and so on; stop when $r_k<\sqrt m$. If $s=\sqrt{\tfrac{m-r_k^2}d}$ is an integer, then the solution is $x=r_k,y=s$; otherwise 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 g² 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 u² + dv² = m/g². If such a solution is found, then (gu, gv) will be a solution to the original equation.

Example

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

References

1. Cornacchia, G. (1908). "Su di un metodo per la risoluzione in numeri interi dell' equazione $\sum_{h=0}^nC_hx^{n-h}y^h=P$.". Giornale di Matematiche di Battaglini 46: 33–90.

External links

Basilla, Julius Magalona (12 May 2004). $u^2+dv^2=m$ (PDF).