The paper "Counting points on elliptic curves over finite fields" by René Schoof presents an algorithm for factoring a prime $p$ on a lattice in $\mathbb{C}$. The problem is, I don't get the details, so I want to go over my doubts along with the theorem.
The paper cites as its source for this result "Su di un metodo per la risoluzione in numeri interi dell’equazione $\sum_{h=0}^n C_h x^{n-h} y^h = P$", a very old paper in italian. Another source is a letter from Lenstra to H. Cohen from 1990, which I couldn't find. Searching for Cornacchia's algorithm on Google just leads me to other algorithm for solving a diophantine equation, so I couldn't find another source. If you know a better source that goes over the details, just reply with it. The result is this:
Theorem. Let $O$ be a complex quadratic order of discriminant $\Delta$ and let $p$ be an odd prime number for which $\Delta$ is a non-zero square modulo $p$. Let $x$ be an integer with $x^2 \equiv \Delta (\mod p)$, $x \equiv \Delta (\mod 2)$ and $0 < x < 2p$. Define the finite sequence of non-negative integer $x_0, x_1, \dots, x_t = 0$ as follows $$\begin{align*} x_0 &= 2p,\\ x_1 &= x,\\ x_{i+1} &= \text{the remainder of }x_{i-1}\text{ after the division by }x_i,\end{align*}$$ Let $i$ be the smallest index for which $x_i < 2 \sqrt{p}$. If $\Delta$ divides $x_i^2 - 4p$ and the quotient is a square $v^2$, then $$\frac{x_i + v \sqrt{\Delta}}{2}$$ is a generator of a prime ideal $\mathfrak{p}$ of $O$ dividing $p$. If not, then the prime ideals $\mathfrak{p}$ of $O$ that divide $p$ are not principal.
Proof. The ideal $\mathfrak{p} = ((x - \sqrt{\Delta})/2, p)$ of $O$ is a prime divisor of $p$. We view $\mathfrak{p}$ as a lattice $L$ in $\mathbb{C}$. We define a finite sequence of elements $z_0,z_1, \dots, z_t \in L$ by $z_0 = p,\, z_1 = (x - \sqrt{\Delta})/2$ and $$z_{i+1} = z_i - q z_{i+1} \quad \text{for } i \ge 1$$ where $q \in \mathbb{Z}_{>0}$ is the integral part of $\mbox{Re} z_i / \mbox{Re} z_{i-1}$. Since the sequence $\mbox{Re} z_i$ is strictly decreasing, the last $z_t$ has real part equal to $0$. The traces $z_i + \overline{z_i}$ are precisely the $x_i$ in Cornacchia's algorithm. The imaginary parts of the $z_i$ form an alternating sequence and $(-1)^{i} \mbox{Im} z_i$ is increasing. Any two consecutive $z_i$ form a basis for $L$ over $\mathbb{Z}$.
The first doubt here is in the definition $z_{i+1} = z_i - q z_{i+1}$. Obviously he didn't mean to define $z_{i+1}$ using itself, so I assumed he meant $z_{i+1} = z_i - q z_{i-1}$, but it could as well be $z_{i+1} = z_{i-1} - q z_{i}$. With this assumption $z_i + \overline{z_i} = x_i$, and the other statements follow. No problem until now, but keep in mind that maybe the choice of index I went with is wrong.
A minimal element of the lattice $L$ is a non-zero vector $z \in L$ with the property that the rectangular box with center $0$ and corner $z$, contains no lattice points except on its corners. In other words, every $w \in L$ with $|\mbox{Re} w | \le |\mbox{Re} z|$ and $|\mbox{Im} w | \le |\mbox{Im} z|$ satisfies $|\mbox{Re} w | = |\mbox{Re} z|$ and $|\mbox{Im} w | = |\mbox{Im} z|$. It is easy to see that all the vector $z_i$ are minimal. There is only one small exception to this: when the real part of $z_1$ exceeds $\mbox{Re} z_0/2 = p/2$, then $\mbox{Im}z_2 = - \mbox{Im}z_1$, but $|\mbox{Re}z_1| \ne |\mbox{Re} z_2|$, so $z_1$ is not minimal in this case.
Besides $z_0 = p$, that casts no box, I don't get why the $z_i$ are minimal. The example he gives for the non-minimal case for $z_1$ just proves $z_2$ is in the box cast by $z_2$ but not in the corner, so I don't know if we could do something similar to prove a $z_i$ is in fact minimal. Any ideas?
There is an argument proving that the vectors $z_i$ are the only minimal vector of the lattice $L$, but I actually understand it provided I assume the vectors $z_i$ are minimal, so I will skip it and resume where were this ties in with the algorithm.
If $\mathfrak{p}$ is principal, every generator is evidently minimal. Therefore one of the $z_i$ is a generator of $\mathfrak{p}$. Considder the one with maximal real part. Since $|z_i| = \sqrt{p}$, its trace $x_i = z_i + \overline{z_i}$ is less than $2 \sqrt{p}$. We must show that $\mbox{Re} z_{i-1} > \sqrt{p}$. Since $z_{i-1}$ is in $\mathfrak{p} = (z_i)$ and since the real part of $z_i$ is maximal, $z_{i-1}$ is not a generator of $\mathfrak{p}$ and we have that $|z_{i-1}|^2 \ge 2 |z_i|^2$. Therefore $$(\mbox{Re} z_{i-1})^2 = |z_{i-1}|^2 - (\mbox{Im} z_{i-1})^2 \ge 2 |z_i|^2 - (\mbox{Im} z_i)^2 \ge |z_i|^2 = p$$ which shows that $\mbox{Re} z_{i-1} > \sqrt{p}$. This completes the proof.
Here he says one of the vectors $z_i$ is the generator we are looking for $\mathfrak{p}$. It then says to consider the $z_i$ with maximal real part. Here I'm confused, isn't the $z_i$ with maximal real part $z_0 = p$, which has $|z_0| = p$? How can he assume $|z_i| = \sqrt{p}$? And how does proving $\mbox{Re} z_{i-1} > \sqrt{p}$ prove that $z_i$ is the generator?