I'm trying to understand the Atkin-Morain Elliptic Curve Primality test, partly using this master's thesis. At one point there is a lemma stating:
Let $D$ be an imaginary quadratic disciminant $n\in\mathbb{Z}$. There exists $\pi\in O_D$ with $n=\pi\overline{\pi}$ if and only $4n=t^2+Dy^2$ has a solution $(t,y)\in\mathbb{Z}^2$.
In this notation, $O_D$ is the set of all algebraic integers in $\mathbb{Q}(\sqrt{D})$. So as far as I can tell, an arbitrary element $\pi\in O_D$ will have the form $\pi = \frac{p}{q}+\sqrt{D}\frac{r}{s}$, with $gcd(p,q)=gcd(r,s)=1$. Thus if $n=\pi\overline{\pi}$ then $n=\frac{p^2}{q^2}+D\frac{r^2}{s^2}$. So one direction is easy: If $4n=t^2+Dy^2$, then set $\pi=\frac{t}{2}+\sqrt{D}\frac{y}{2}$. In the other direction, I don't know where to go.
It seems like I'm including too much with the form of $\pi$, since there is the extra requirement that $\pi$ be algebraic over $\mathbb{Z}$, but I don't know how ot use that for the required equivalence.
Suppose there is $\pi\in O_D$ with $n=\pi\overline{\pi}$. Consider 2 cases depending on whether $D\equiv 0$ or $1\bmod 4$. First $D\equiv 1\bmod 4$ then $\pi = \frac{t+y\sqrt{D}}{2}$, so that $n=N(\pi)= \frac{t^2+Dy^2}{4}$ and hence $4n =t^2+Dy^2$ as desired. If $D\equiv 0\bmod 4$ then $\pi=t+y\sqrt{D/4}$ and $n = N(\pi)= t^2+D/4y^2$, so that we can take $4n = 4t^2+Dy^2$.
For the other direction suppose $4n = t^2+Dy^2$, then $\alpha = \frac{t+y\sqrt{D}}{2}$ is an algebraic integer in the case of $D\equiv 1\bmod 4$ and has $N(\alpha)=n$. If $D\equiv 0\bmod 4$, we see that $t$ must be even, so that $n=(t/2)^2+Dy^2$, and we can take $\alpha = t/2+y\sqrt{D}$ with $N(\alpha)=n$.