Number of points of an elliptic curve In my cryptography course I found the following problem:
Find $|E(\mathbb{F}_{7^{100}})|$ where $E$  is given by $y^2=x^3+1$.
I know how to do it for small numbers, using quadratic residues, but this doesn't work with $7^{100}$. My question is if there is a general method or algorithm that works in general and can be done by hand (no computer) or if there is a clever solution in this particular case.
Many thanks.
 A: The zeta function for $E/\Bbb F_p$ is, by definition, the formal power series $$Z(T) = \exp\left(\sum_{r = 1}^\infty \frac{|E(\Bbb F_{p^r})|}rT^r\right).$$
It turns out that $Z(T)$ is a rational function: there exists $a \in \Bbb Z$ such that $$Z(T) = \frac{1 - aT + pT^2}{(1 - T)(1 - pT)}.$$ This result appears e.g. in the book of Silverman, Arithmetic of Elliptic Curves, Chapter V, Theorem 2.4 (Page 136).
By calculating $|E(\Bbb F_p)|$, you can determine the value of $a$, which then gives you all the values of $|E(\Bbb F_{p^r})|$.
A: Let $\,a_n\,$ be the number of solutions to
$\, y^2 \equiv x^3 + 1 \,$ in $\,\mathbb{F}_{7^n}\,$
and also the point at infinity.
A search for $\,n=1\,$ yields the $11$ solutions for $\,(x,y)\,$
$$ (0,\pm1),\, (1,\pm3),\, (2,\pm3),\, (3,0),\,
   (4,\pm3),\, (5,0),\, (6,0) $$
in $\,\mathbb{F}_{7}\,$ and thus $\,a_1=12.\,$
The general result is
$$ \sum_{n=1}^\infty \frac{a_n}n T^n = \log{Z(T)}\quad \text{ where }
\quad Z(T) = \frac{1 + t_pT + pT^2}{(1 - T)(1 - pT)} $$
as mentioned in another answer. Here $\,t_7=4\,$ and the power series is
$$ Z(T) = 1 + 12T + 96T^2 + 684T^3 + 4800T^4 + 33612T^5 + \cdots. $$
The generating function for $\,a_n\,$ is
$$ A(T) := \sum_{n=1}^\infty a_nT^n = 1 + 12T + 48T^2 + 324T^3 + 
2496T^4 + \cdots. $$
Let $\,b_n := a_n -1\,$ be the number of solutions not including
the point at infinity. Then
$$ B(T) := \sum_{n=1}^\infty b_nT^n = 11T + 47T^2 + 323T^3 + 
2495T^4 + \cdots.$$
Note that $\,b_n\,$ satisfies a linear recursion and has a rational
generating function which is
$$ B(T) = \frac{T (11 + 14 T - 49 T^2)}{(1 - 7 T) (1 + 4 T + 7 T^2)}. $$
The general results are that
$$ B(T) = \frac{T ((p+t_p) + 2pT -p^2T^2)}{(1 - pT)(1 + t_pT +pT^2)} $$
and
$$ b_n = p^n - (\alpha^n + \beta^n) \quad \text{ where } \quad
\alpha\beta = p \text{ and } \alpha+\beta = -t_p. $$
For $\,p=7\,$ the conjugate root constants are
$\,\alpha = -2+i\sqrt{3},\; \beta = -2-i\sqrt{3}.$
