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
.
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)]