Cornacchia's algorithm

Cornacchia's algorithm searches for primitive integer solutions of $x^2+d{y}^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.