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

  1. 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.

  2. 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

>>> from sage.all import *
>>> p = next_prime(Integer(10)**Integer(3))
>>> E = EllipticCurve(GF(p), [Integer(3),Integer(4)])
>>> E.cardinality_bsgs()
1020
>>> E = EllipticCurve(GF(Integer(3)**Integer(4),'a'), [Integer(1),Integer(1)])
>>> E.cardinality_bsgs()
64
>>> F = GF(Integer(101)**Integer(3),'a', names=('a',)); (a,) = F._first_ngens(1)
>>> E = EllipticCurve([Integer(2)*a**Integer(2) + Integer(48)*a + Integer(27), Integer(89)*a**Integer(2) + Integer(76)*a + Integer(24)])
>>> 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

>>> from sage.all import *
>>> p = next_prime(Integer(10)**Integer(3))
>>> E = EllipticCurve(GF(p), [Integer(3),Integer(4)])
>>> E.cardinality_exhaustive()
1020
>>> E = EllipticCurve(GF(Integer(3)**Integer(4),'a'), [Integer(1),Integer(1)])
>>> E.cardinality_exhaustive()
64