Specific algorithms to compute cardinality of elliptic curves over a finite field¶

Since point counting now uses PARI/GP, this code is only used when a specific algorithm was specified or when the j-invariant lies in a subfield.

AUTHORS:

John Cremona (2008-2009): Original point counting code
Jeroen Demeyer (2017-2018): Refactored and moved to cardinality.py.

sage.schemes.elliptic_curves.cardinality.cardinality_bsgs(self, verbose=False)[source]¶

Return the cardinality of self over the base field.

ALGORITHM: A variant of “Mestre’s trick” extended to all finite fields by Cremona and Sutherland, 2008.

Note

The Mestre-Schoof-Cremona-Sutherland algorithm may fail for a small finite number of curves over $F_{q}$ for $q$ at most 49, so for $q < 50$ we use an exhaustive count.
Quadratic twists are not implemented in characteristic 2 when $j = 0 (= 1728)$ ; but this case is treated separately.

EXAMPLES:

sage: p = next_prime(10^3)
sage: E = EllipticCurve(GF(p), [3,4])
sage: E.cardinality_bsgs()
1020
sage: E = EllipticCurve(GF(3^4,'a'), [1,1])
sage: E.cardinality_bsgs()
64
sage: F.<a> = GF(101^3,'a')
sage: E = EllipticCurve([2*a^2 + 48*a + 27, 89*a^2 + 76*a + 24])
sage: E.cardinality_bsgs()
1031352

sage.schemes.elliptic_curves.cardinality.cardinality_exhaustive(self)[source]¶

Return the cardinality of self over the base field.

This simply adds up the number of points with each x-coordinate: only used for small field sizes!

EXAMPLES:

sage: p = next_prime(10^3)
sage: E = EllipticCurve(GF(p), [3,4])
sage: E.cardinality_exhaustive()
1020
sage: E = EllipticCurve(GF(3^4,'a'), [1,1])
sage: E.cardinality_exhaustive()
64