= Cornacchia's algorithm
{c}
= Cornacchia algorithm
{c}
{synonym}
<Cornacchia's algorithm> searches for primitive <integer> solutions of $x^2+dy^2=m$ by combining a <modular square root> of $-d$ modulo $m$ with the <Euclidean algorithm>. In the standard odd-prime case $m=p$, choose a root $r$ with $0<r<p/2$, run the <Euclidean algorithm> on $(p,r)$ until a remainder $x<\sqrt p$ occurs, and test whether $(p-x^2)/d$ is a nonnegative <integer> square. Both roots can be tried.
For $p=13,d=1$, the root $r=5$ of $-1$ gives the remainder $3$, and $13-3^2=4$, yielding $(x,y)=(3,2)$. The final exact square test is essential: a modular root is only a candidate-producing input. For general composite moduli, additional hypotheses and choices are required to enumerate primitive solutions.
Back to article page
