An explicit equation for an elliptic curve with CM?

Here is the way I do small examples when they come up. Let $\mathcal{O}$ be the ring of integers in $\mathbb{Q}(\sqrt{-d})$. Let $I_1$, $I_2$, ..., $I_h$ ideals in $\mathcal{O}$ representing the elements of the class group of $\mathcal{O}$. Then the elliptic curves with CM by $\mathcal{O}$ are $\mathbb{C}/I_j$.

If we write $I_j$ in the form $\mathrm{Span}_{\mathbb{Z}}(a_j, b_j+c_j \sqrt{-d})$, for $a_j$, $b_j$, $c_j \in \mathbb{Z}$, then the $j$-invariant of $\mathbb{C}/I_j$ is $j\left( \tfrac{b_j+c_j \sqrt{-d}}{a_j} \right)$. For example, for $d=5$, the two ideal classes are $\mathrm{Span}_{\mathbb{Z}}(1, \sqrt{-5})$ and $\mathrm{Span}_{\mathbb{Z}}(2, 1+\sqrt{-5})$, with $j$-invariants $$j \left( \sqrt{5} i \right) \approx 1264538.9094751405093 $$ and $$j \left( \tfrac{1+\sqrt{5} i}{2} \right) \approx -538.90947514050932023.$$

These numeric computations can be done with your favorite computer algebra system. Important warning if you use Mathematica: The KleinInvariantJ function is off by a factor of 1728 from the normalization everyone else uses, so $j(z)$ is 1728 KleinInvariantJ[z].

Now, here are the two key facts: The values $j \left( \tfrac{b_j + c_j \sqrt{-d}}{a_j} \right)$ are algebraic integers and, as $j$ ranges from $1$ to $h$, are a system of Galois conjugates. In other words, the coefficients of $\prod_{j=1}^j \left(z - j \left( \tfrac{b_j + c_j \sqrt{-d}}{a_j} \right) \right)$ are integers!

Now, we saw above that the value of $j$ are easy to compute. So we can compute the coefficients of this polynomial. In our example: $${\Big(} z - j(\sqrt{5} i) {\Big)} {\Big(} z - j\left(\tfrac{1+\sqrt{5} i}{2} \right) {\Big)} = z^2 - 1264000 z -681472000.$$ Since we know that the answers are integers, we only need to compute them to enough accuracy to round them off to the nearest integer.

We can then compute the $j$-values as the roots of this polynomial: They are $632000 \pm 282880 \sqrt{5}$. Of course, we can only find exact formulas to the degree that we can write down solutions of solvable polynomials in radicals.