# 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.

• Did you see thngs like $\# E(\Bbb{F}_{7^n})=N(\phi^{7^n}-1) = (\phi^{7^n}-1) ^*(\phi^{7^n}-1)$ already? (Frobenius endomorphism and dual endomorphism) This is detailed in Silverman's AEC. Dec 4, 2021 at 18:49
• @reuns thanks, do you know if we can solve it without strong results? If possible I would like to solve it directlly with elementary methods Dec 4, 2021 at 20:00
• I don't think there is any alternative method. Dec 4, 2021 at 20:33
• Related. I have gotten used to doing it that way because it generalizes to higher genus curves. Knowing the answer for the fields $\Bbb{F}_{p^\ell}$, $\ell=1,2,\ldots,g$, gives you everything. In the case of elliptic curves $\ell=1$ suffices. It is equivalent to using the zeta function as in reuns's comment and WhatsUp's answer. Dec 5, 2021 at 5:20
• Anyway, the theory of zeta functions gives the recipe $$\#E(\Bbb{F}_{p^n})=p^n+1-\omega_1^n-\omega_2^n$$ for a pair of complex conjugate numbers $\omega_1,\omega_2$ satisfying $|\omega_{1,2}|=\sqrt p$. Counting also the point at infinity we have $\#E(\Bbb{F}_7)=12$, so $\omega_1\omega_2=7$ and $\omega_1+\omega_2=-4$. This yields $\omega_{1,2}=-2\pm i\sqrt{3}$. And gives the answer $$\#E(\Bbb{F}_{7^{100}})=7^{100}+1-\omega_1^{100}-\omega_2^{100}=3234476509624757991344647769100216810857205479048020383989725994314227 883581889277376.$$ Dec 5, 2021 at 5:47

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

• One question, is It posible to solve this particular exercise without this general result? Because if It is possible I want to avoid to study all this theory for just one exercise Dec 4, 2021 at 19:55
• I can't see an easier way to do it. I think the number $7^{100}$ is chosen in purpose. For some other choices, there are easier methods. E.g. if it were $p^r$ with $p^r \not\equiv 1\pmod 3$, then we could use the fact that $x \mapsto x^3$ is a bijection from $\Bbb F_{p^r}$ to itself. But this doesn't work for $7^{100}$. Dec 4, 2021 at 20:05
• Ok, thanks for your help :) Dec 4, 2021 at 20:09

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

• That was exactly what I was looking for, many thanks Dec 4, 2021 at 22:46
• I haven't gone through the argument, but this answer cannot be correct. In the book of Silverman, Arithmetic of Elliptic Curves, Chapter V, Theorem 1.1 (Page 131), it is proved that $|\#E(\Bbb F_q) - q - 1| \leq 2\sqrt q$ (this is in accordance with Weil's conjecture, now a theorem of Deligne). Thus for large $q$, the number of points of $E(\Bbb F_q)$ should be close to $q$. It is impossible that $a_n = 2(7^n - 1)$ for all $n > 0$. Dec 4, 2021 at 23:35
• @WhatsUp I agree with you, but where is the error? Dec 4, 2021 at 23:41
• Your formula produces $a_2 = 2(7^2 - 1) = 98$. The value of $a_2$ should be $48$ (including infinity point). Dec 4, 2021 at 23:53
• @WhatsUp Of course, Again, Thanks for your correction. Dec 4, 2021 at 23:54