15.1 Point counting on curves

How do you count points on an elliptic curve over a finite field in Sage?

Over prime finite fields, Sage includes both the the baby step giant step method, as implemented in PARI's ellap, and the SEA (Schoof-Elkies-Atkin) algorithm as implemented in PARI by Christophe Doche and Sylvain Duquesne. An example taken form the Sage Reference manual:

sage: E = EllipticCurve(GF(10007),[1,2,3,4,5])
sage: E.cardinality(algorithm='sea')
10076
sage: E.cardinality(algorithm='bsgs')
10076

The command E.points() will return the actual list of rational points.

How do you count points on a plane curve over a finite field? The rational_points command produces points by a simple enumeration algorithm. Here is an example of the syntax:

sage: x,y,z = PolynomialRing(GF(5), 3, 'xyz').gens()
sage: C = Curve(y^2*z^7 - x^9 - x*z^8); C
Projective Curve over Finite Field of size 5 defined by -x^9 + y^2*z^7 - x*z^8
sage: C.rational_points()
[(0 : 0 : 1), (0 : 1 : 0), (2 : 2 : 1), (2 : 3 : 1), (3 : 1 : 1), (3 : 4 : 1)]
sage: C.rational_points(algorithm="bn")
[(0 : 0 : 1), (0 : 1 : 0), (2 : 2 : 1), (2 : 3 : 1), (3 : 1 : 1), (3 : 4 : 1)]

The option algorithm="bn" uses Sage's Singular interface and calls the brnoeth package.

Here is another example using Sage's rational_points applied to Klein's quartic over $ GF(8)$ .

sage: x, y, z = PolynomialRing(GF(8,'a'), 3, 'xyz').gens()
sage: f = x^3*y+y^3*z+x*z^3
sage: C = Curve(f); C
Projective Curve over Finite Field in a of size 2^3 defined by x^3*y + y^3*z + x*z^3
sage: C.rational_points()
[(0 : 0 : 1), 
 (0 : 1 : 0), 
 (1 : 0 : 0), 
 (1 : a : 1), 
 (1 : a^2 : 1), 
 (1 : a^2 + a : 1), 
 (a : 1 : 1), 
 (a : a^2 : 1), 
 (a : a^2 + 1 : 1), 
 (a + 1 : a + 1 : 1), 
 (a + 1 : a^2 : 1), 
 (a + 1 : a^2 + a + 1 : 1), 
 (a^2 : 1 : 1), 
 (a^2 : a^2 + a : 1), 
 (a^2 : a^2 + a + 1 : 1), 
 (a^2 + 1 : a + 1 : 1), 
 (a^2 + 1 : a^2 + 1 : 1), 
 (a^2 + 1 : a^2 + a : 1), 
 (a^2 + a : 1 : 1), 
 (a^2 + a : a : 1), 
 (a^2 + a : a + 1 : 1), 
 (a^2 + a + 1 : a : 1), 
 (a^2 + a + 1 : a^2 + 1 : 1), 
 (a^2 + a + 1 : a^2 + a + 1 : 1)]



Subsections
See About this document... for information on suggesting changes.