# Counting points on an elliptic curve

Apparently the Riemann Hypothesis part of the Weil conjectures (which are now theorems) imply, in the case of elliptic curves, that if we have an elliptic curve defined over $$\mathbb{F}_p$$, and $$q = p^n$$, then the number of $$\mathbb{F}_q$$-points of this curve equals

$$q + 1 - \alpha^n - \beta^n$$

where $$\alpha, \beta \in \mathbb{C}$$ have $$|\alpha| = |\beta| = q^{1/2}$$. Is this correct? And if so, can someone show me some simple examples of elliptic curves and primes $$p$$ for which $$\alpha$$ and $$\beta$$ are known?

• It should read $$q+1-\alpha^n-\beta^n.$$ We also know that $\alpha$ and $\beta$ are roots of a quadratic with integer coefficients. This is because $\alpha\beta=p$ and $p+1-(\alpha+\beta)$ is the number of $\Bbb{F}_p$-points. I have jotted down several examples as answers on this site. The most recent one is this, but there the purpose was different. – Jyrki Lahtonen Sep 7 at 4:08
• So if you know the number of $\Bbb{F}_p$-points you are basically done. For large $p$ that is still somewhat taxing. I think that the Schoof-Elkies-Atkin algorithm is the best tool for that job. The idea is to find enough many small primes $\ell$ such that we can calculate $N=N(E(\Bbb{F}_p))$ modulo $\ell$, so that Hasse-Weil bound determines $N$ uniquely. – Jyrki Lahtonen Sep 7 at 4:17
• A simple case, where finding $\alpha,\beta$ is easy, are the elliptic curves of the form $$y^2=x^3+A$$ over $\Bbb{F}_p$, $p\equiv2\pmod3$. See here. We see that $N=p+1$ implying that $\alpha,\beta=\pm i\sqrt{p}$. I hate to make it look like I'm blowing my own trumpet. We have people on the site who know elliptic curves much better than I do. I'm relatively conversant with the finite field side, and have answered a lot of related questions, so those were simply quick to find. – Jyrki Lahtonen Sep 7 at 4:25

Yes, for $$E$$ an elliptic curve defined over the finite field $$\Bbb F_p$$, $$p$$ prime, the shape of the number of $$\Bbb F_{p^n}$$-rational points is $$|E(\Bbb F_{p^n})| = (p^n+1)- \alpha^n-\beta^n\ ,$$ where $$\alpha,\beta$$ depend (only) on $$E$$, are complex numbers, are conjugated, and $$\alpha\beta=p$$.

This answer uses computer aid, here sage, to produce some examples in some small characteristic. The "do it yourself" code was written to be easily changed, and experiment with other similar situations. Since i need some $$\pm 2\sqrt p$$ marge, i will use a decent prime, $$p=7$$.

If this is not wanted, please ignore the answer.

Sage comes with a lot of algorithms related to elliptic curves over finite fields. A brute force loop collects the elliptic curves in a dictionary, the keys being their orders. The following orders can be realized:

sage: dic = {}
sage: p = 7
sage: F = GF(p)
sage: for a, b in cartesian_product( [F, F] ):
....:     try:
....:         E = EllipticCurve( F, [a, b] )
....:         ord = E.order()
....:         if ord in dic:
....:             dic[ord].append(E)
....:         else:
....:             dic[ord] = [ E, ]
....:     except:
....:         # singular curve
....:         pass
....:
sage: dic.keys()
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]


So as expected, all integers in the range between $$(7+1)\pm 2\sqrt 7$$, i.e. in the range delimited by $$8\pm 5$$, can be realized. For each such possible order $$N$$ we list the equation of one elliptic curve realizing $$N$$, and compute the corresponding $$\alpha$$ and $$\beta$$, and check the formula. To have a first detailed situation, let us consider $$N=10$$ with more lines of code. We initialize in E the first found elliptic curve with order ten. We ask for the minimal polynomial of the Frobenius morphism. Its roots are the needed values for $$\alpha,\beta$$. It turns out that the polynomial is $$x^2 + 2x + 7$$, its roots live in $$K=\Bbb Q(\sqrt{-6})$$, it is handy to use a notation for $$\sqrt{-6}$$, we will use $$a$$ for it. Sage offers than the values \begin{aligned} \alpha &= -1+a=-1+\sqrt{-6}\ ,\\ \beta &= -1-a=-1-\sqrt{-6}\ . \end{aligned}

sage: E = dic
sage: E
Elliptic Curve defined by y^2 = x^3 + x + 4 over Finite Field of size 7
sage: E.frobenius_polynomial()
x^2 + 2*x + 7
sage: K.<a> = QuadraticField(1-7)
sage: K
Number Field in a with defining polynomial x^2 + 6 with a = 2.449489742783178?*I

sage: alpha, beta = E.frobenius_polynomial().roots(ring=K, multiplicities=False)
sage: alpha, beta
(a - 1, -a - 1)

sage: for n in [1..10]:    print p^n + 1 - alpha^n - beta^n
10
60
310
2400
17050
117180
822790
5769600
40349290
282450300

sage: for n in [1..10]:    print E.base_extend( GF(p^n) ).order()
10
60
310
2400
17050
117180
822790
5769600
40349290
282450300

sage: E.points()
[(0 : 1 : 0), (0 : 2 : 1), (0 : 5 : 1), (2 : 0 : 1), (4 : 3 : 1), (4 : 4 : 1), (5 : 1 : 1), (5 : 6 : 1), (6 : 3 : 1), (6 : 4 : 1)]


We asked explicitly for the numbers $$p^n -\alpha^n -\beta^n + 1^n$$ for some first small values of $$n$$, and obtained some natural numbers after computations in the imaginary quadratic field $$K$$, then we asked for the orders of $$E$$ after a base change to $$\Bbb F_{p^n}$$, i.e. for the number of $$\Bbb F_{p^n}$$-rational points on $$E$$. Well, the orders came immediately, so no computation of some $$282450300$$ was performed in the last case. So to have a small check, the ten points over $$\Bbb F_p$$ were printed.

We can also ask for the action of the Frobenius morphism, defined first on $$\Bbb F_{p^n}$$, then on (the components of) a point in $$E(\Bbb F_{p^n})$$ in a particular example. To have a non-trivial action, let us work over the field with $$7^4=2401$$ elements.

sage: F2401.<z> = GF(7^4)
sage: F2401
Finite Field in z of size 7^4
sage: z.minpoly()
x^4 + 5*x^2 + 4*x + 3
sage: F2401.cardinality()
2401
sage: E2401 = E.base_extend(F2401)

sage: import random
sage: P = random.choice(E2401.points())    # chose a point over GF(7^4)
sage: xP, yP = P.xy()
sage: fP  = E2401( [xP^7 , yP^7 ] )    # Frobenius(P)
sage: ffP = E2401( [xP^49, yP^49] )    # Frobenius^2(P)
sage: ffP + 2*fP + 7*P
(0 : 1 : 0)

sage: P, fP, ffP
((2*z^2 + 4*z + 4 : z^3 + 4*z^2 + z + 3 : 1),
(4*z^3 + 2*z^2 + 2 : 6*z^3 + 2*z^2 + 6 : 1),
(6*z^3 + 2*z^2 + 2*z + 1 : 2*z^3 + 5*z^2 + 2*z + 5 : 1))


So after the random choice of a point in $$E(\Bbb F_{2401})$$, and the point was complicated enough, we have checked the relation $$f^2(P) + 2f(P) + 7P=0$$. Here, $$f:E(\Bbb F_{2401})\to E(\Bbb F_{2401})$$ is the morphism $$(x,y)\to(x^7,y^7)$$, and the operation of addition and multiplication in the above relation are the algebraic ones, coming from the group structure of the elliptic curve. It is clear that the trace of the Frobenius morphism on $$E$$,

sage: E.frobenius().trace()
-2


determines the orders. The norm is of course

sage: E.frobenius().norm()
7


Let us give some messy information for some other elliptic curves realizing the orders in $$[3,4,\dots,14,15]$$. This time i've got:

sage: for ord in dic:
....:     E = random.choice(dic[ord])    # pick a random curve of order <ord>
....:     print "Order %s :: E = %s" % (ord, E)
....:     print "    Trace of Frobenius = %s" % E.frobenius().trace()
....:     print "    alpha, beta are roots of %s" % E.frobenius_polynomial()
....:     print "    Orders of E(GF(q)) for q in %s are:" % [ p^n for n in [1..5] ]
....:     print "        %s" % [ E.base_extend(GF(p^n)).order()   for n in [1..5] ]
....:
Order 3 :: E = Elliptic Curve defined by y^2 = x^3 + 4 over Finite Field of size 7
Trace of Frobenius = 5
alpha, beta are roots of x^2 - 5*x + 7
Orders of E(GF(q)) for q in [7, 49, 343, 2401, 16807] are:
[3, 39, 324, 2379, 16833]
Order 4 :: E = Elliptic Curve defined by y^2 = x^3 + 6 over Finite Field of size 7
Trace of Frobenius = 4
alpha, beta are roots of x^2 - 4*x + 7
Orders of E(GF(q)) for q in [7, 49, 343, 2401, 16807] are:
[4, 48, 364, 2496, 17044]
Order 5 :: E = Elliptic Curve defined by y^2 = x^3 + 4*x + 1 over Finite Field of size 7
Trace of Frobenius = 3
alpha, beta are roots of x^2 - 3*x + 7
Orders of E(GF(q)) for q in [7, 49, 343, 2401, 16807] are:
[5, 55, 380, 2475, 16775]
Order 6 :: E = Elliptic Curve defined by y^2 = x^3 + 3*x + 3 over Finite Field of size 7
Trace of Frobenius = 2
alpha, beta are roots of x^2 - 2*x + 7
Orders of E(GF(q)) for q in [7, 49, 343, 2401, 16807] are:
[6, 60, 378, 2400, 16566]
Order 7 :: E = Elliptic Curve defined by y^2 = x^3 + 6*x + 5 over Finite Field of size 7
Trace of Frobenius = 1
alpha, beta are roots of x^2 - x + 7
Orders of E(GF(q)) for q in [7, 49, 343, 2401, 16807] are:
[7, 63, 364, 2331, 16597]
Order 8 :: E = Elliptic Curve defined by y^2 = x^3 + 4*x over Finite Field of size 7
Trace of Frobenius = 0
alpha, beta are roots of x^2 + 7
Orders of E(GF(q)) for q in [7, 49, 343, 2401, 16807] are:
[8, 64, 344, 2304, 16808]
Order 9 :: E = Elliptic Curve defined by y^2 = x^3 + 6*x + 2 over Finite Field of size 7
Trace of Frobenius = -1
alpha, beta are roots of x^2 + x + 7
Orders of E(GF(q)) for q in [7, 49, 343, 2401, 16807] are:
[9, 63, 324, 2331, 17019]
Order 10 :: E = Elliptic Curve defined by y^2 = x^3 + x + 4 over Finite Field of size 7
Trace of Frobenius = -2
alpha, beta are roots of x^2 + 2*x + 7
Orders of E(GF(q)) for q in [7, 49, 343, 2401, 16807] are:
[10, 60, 310, 2400, 17050]
Order 11 :: E = Elliptic Curve defined by y^2 = x^3 + x + 6 over Finite Field of size 7
Trace of Frobenius = -3
alpha, beta are roots of x^2 + 3*x + 7
Orders of E(GF(q)) for q in [7, 49, 343, 2401, 16807] are:
[11, 55, 308, 2475, 16841]
Order 12 :: E = Elliptic Curve defined by y^2 = x^3 + 3*x + 1 over Finite Field of size 7
Trace of Frobenius = -4
alpha, beta are roots of x^2 + 4*x + 7
Orders of E(GF(q)) for q in [7, 49, 343, 2401, 16807] are:
[12, 48, 324, 2496, 16572]
Order 13 :: E = Elliptic Curve defined by y^2 = x^3 + 3 over Finite Field of size 7
Trace of Frobenius = -5
alpha, beta are roots of x^2 + 5*x + 7
Orders of E(GF(q)) for q in [7, 49, 343, 2401, 16807] are:
[13, 39, 364, 2379, 16783]