How does one find the number of distinct solutions $(x, y)$ of $Y^2=X^3+1$ over a $\mathrm{GF}(p)$? Given the equation $Y^2=X^3+1$ over the finite field $\mathrm{GF}(p)$, how does one find the number of solution pairs $(x, y)$ that satisfy the equation?
For example, in $\mathrm{GF}(2)$ and $\mathrm{GF}(3)$, there are 2 solutions and 3 solutions respectively: $(0, 1), (1, 0)$ for the former and $(0, -1), (1, 0), (-1, 0)$ for the latter. 
In the other primes, those of the form $p \equiv 2 \pmod{3}$, cubing is a multiplicative automorphism and therefore one can easily show that there is exactly $p$ distinct pairs $(x, y)$ with $x, y$ in $\mathrm{GF}(p)$.
What about for other primes? What kind of techniques/methods/theorems can be used to find the number of solutions without brute forcing it for a given $p \equiv 1 \pmod{3}$?
 A: The equation describes the elliptic curve "36a1". The modular form coefficients of it is the OEIS sequence A000727. The number of solutions is $p-2x$ using the unique solution to $p=x^2+3y^2$ where $x\equiv 1 \pmod {3}$ and $y>0$ if $p\equiv 1\pmod{3}$ else $p$. More details are in the sequence entry including a reference to Exercise 47.2 in Silverman's A Friendly Introduction to Number Theory.
A: Let $g$ a generator of $\mathbb{F}_p^\times$. Define the cubic character $\chi_3(g^a) = \zeta_3^a,\chi_3(0)=0$ and the trivial character $\chi_0(x) = 1_{x \in \mathbb{F}_p^\times}$. Then $$\frac{1}{3}(\chi_3(x)+\overline{\chi_3(x)}+\chi_0(x)) = 1_{x \in (\mathbb{F}_p^\times)^3}$$
Define the Jacobi sum
$$J(\chi,\chi) =\sum_{x\in \mathbb{F}_p} \chi(x)\chi(1-x)=\sum_{x\in \mathbb{F}_p} \chi(ax)\chi(1-ax)=\chi(a)^2\sum_{x\in \mathbb{F}_p} \chi(x)\chi(a^{-1}-x), \quad a \in \mathbb{F}_p^\times$$
Thus 
$$\sum_{y \in \mathbb{F}_p} 1_{y^2-1 \in (\mathbb{F}_p^\times)^3} = \frac{1}{3} \sum_{y \in \mathbb{F}_p} (\chi_3(y^2-1)+\overline{\chi_3(y^2-1)}+\chi_0(y^2-1))$$
$$ =\frac{1}{3}( \chi_3(2^{-1})J(\chi_3,\chi_3)+\overline{ \chi_3(2^{-1})J(\chi_3,\chi_3)}+J(\chi_0,\chi_0))$$
If $p \equiv 1 \bmod 3$ then $\mathbb{F}_p$ contains a 3rd root of unity so $x^3 = c$ has $0$ or $3$ solutions.
Therefore, together with $J(\chi_0,\chi_0))=\sum_{y \in \mathbb{F}_p^\times} 1_{1-y \in \mathbb{F}_p^\times} = p-2$,
the point at $\infty$ and the 2 solutions $y^2-1= 0$ we find
$$\# E(\mathbb{F}_p) = 1+2+3 \sum_{y \in \mathbb{F}_p^\times} 1_{y^2-1 \in (\mathbb{F}_p^\times)^3} = p+1+\chi_3(2^{-1})J(\chi_3,\chi_3)+\overline{ \chi_3(2^{-1})J(\chi_3,\chi_3)}$$
A: In this case for $p\equiv1\pmod 3$, there is a formula in terms of Jacobi
sums. This can be found in the book of Ireland and Rosen. It is
$$p+J(\rho,\chi)+\overline{J(\rho,\chi)}$$
where $\rho$ and $\chi$ are quadratic and cubic characters of $\Bbb F^\times$. This Jacobi sum can be expressed in terms of the representations
of $p$ in the form $a^2+ab+b^2$.
