# Cornacchia's algorithm

Jump to navigation Jump to search

In computational number theory, Cornacchia's algorithm is an algorithm for solving the Diophantine equation $x^{2}+dy^{2}=m$ , where $1\leq d and d and m are coprime. The algorithm was described in 1908 by Giuseppe Cornacchia.

## 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 r0m/2 (if not, then replace r0 with m - r0, 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 g2 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 u2 + dv2 = m/g2. 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.