5
$\begingroup$

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.

$\endgroup$
7
  • 2
    $\begingroup$ 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. $\endgroup$
    – reuns
    Dec 4 '21 at 18:49
  • $\begingroup$ @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 $\endgroup$
    – Marcos
    Dec 4 '21 at 20:00
  • $\begingroup$ I don't think there is any alternative method. $\endgroup$
    – reuns
    Dec 4 '21 at 20:33
  • $\begingroup$ 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. $\endgroup$ Dec 5 '21 at 5:20
  • $\begingroup$ 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.$$ $\endgroup$ Dec 5 '21 at 5:47
8
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – Marcos
    Dec 4 '21 at 19:55
  • 2
    $\begingroup$ 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}$. $\endgroup$
    – WhatsUp
    Dec 4 '21 at 20:05
  • $\begingroup$ Ok, thanks for your help :) $\endgroup$
    – Marcos
    Dec 4 '21 at 20:09
3
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ That was exactly what I was looking for, many thanks $\endgroup$
    – Marcos
    Dec 4 '21 at 22:46
  • 4
    $\begingroup$ 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$. $\endgroup$
    – WhatsUp
    Dec 4 '21 at 23:35
  • $\begingroup$ @WhatsUp I agree with you, but where is the error? $\endgroup$
    – Somos
    Dec 4 '21 at 23:41
  • 2
    $\begingroup$ Your formula produces $a_2 = 2(7^2 - 1) = 98$. The value of $a_2$ should be $48$ (including infinity point). $\endgroup$
    – WhatsUp
    Dec 4 '21 at 23:53
  • 1
    $\begingroup$ @WhatsUp Of course, Again, Thanks for your correction. $\endgroup$
    – Somos
    Dec 4 '21 at 23:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.