As you probably know, you are also asking for a particular Gaussian prime ideal $(\pi )$ with norm $p$. Which is to say that such a choice of square root of $-1$ is the same as giving a homomorphism from the Gaussian integers to the field with $p$ elements, which is the same as giving its kernel. This accounts for the formulae in $a$ and $b$. The theory of complex multiplication gives a little bit more, namely by identifying the Frobenius automorphism which is subject to some congruence conditions depending on choice of curve with complex multiplication by the Gaussian integers. The formulae with binomial coefficients come out of formulae for the Hasse invariant.
Edit: To clarify somewhat, given an elliptic curve $C$ over the rational numbers with complex multiplication by the Gaussian integers, it makes good sense to consider its reduction $C$ mod $p$ (away from primes of bad reduction). But it does not make naive sense to ask for the endomorphism ring to reduce mod $p$. In fact this looks like the same issue: the complex square root $i$ of $-1$ acts on C, and if we have a candidate square root $i$ of $-1$ mod $p$, we can then see how to reduce any endomorphism. The natural endomorphism mod $p$ is the Frobenius endomorphism. What I was trying to say amounts to two or three things, about looking at this question:
- there is a family of such curves C, not just one;
- making the change of field to C over $Q(i)$ makes the choice required to be one of the two prime ideals above $p$;
- if you lift the Frobenius back to the complex endomorphisms, you get the ways of expressing $i$ mod $p$ via the $a$ and $b$.