Number of points of an elliptic curve

Question

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.

Answer 1

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})|$.

Answer 2

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 (using a constant $\,t_p$) is

$$ \sum_{n=1}^\infty \frac{a_n}n T^n = \log{Z(T)}\quad \text{ where } \quad Z(T) = \frac{1 + t_pT + p\,T^2}{(1 - T)(1 - p\,T)} $$

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{11 T + 14 T^2 - 49 T^3} {(1 - 7 T) (1 + 4 T + 7 T^2)}. $$

The result (in general) is that

$$ B(T) = \frac{(p+t_p) T + 2pT^2 -p^2T^3} {(1 - pT)(1 + t_pT +pT^2)}. $$

And also

$$ 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}.$