Elliptic curves over finite fields

AUTHORS:

  • William Stein (2005): Initial version
  • Robert Bradshaw et al....
  • John Cremona (2008-02): Point counting and group structure for non-prime fields, Frobenius endomorphism and order, elliptic logs
class sage.schemes.elliptic_curves.ell_finite_field.EllipticCurve_finite_field(x, y=None)

Elliptic curve over a finite field.

__getitem__(n)

Return the n’th point in self’s __points list. This enables users to iterate over the curve’s point set.

EXAMPLE:

sage: E=EllipticCurve(GF(97),[2,3])
sage: S=E.points()
sage: E[10]
(10 : 76 : 1)
sage: E[15]
(17 : 10 : 1)
sage: for P in E: print P.order()
1
50
50
50
50
5
5
50
...
__init__(x, y=None)

Special constructor for elliptic curves over a finite field

EXAMPLES:

sage: EllipticCurve(GF(101),[2,3])
Elliptic Curve defined by y^2  = x^3 + 2*x + 3 over Finite Field of size 101
sage: F=GF(101^2, 'a')
sage: EllipticCurve([F(2),F(3)])
Elliptic Curve defined by y^2  = x^3 + 2*x + 3 over Finite Field in a of size 101^2

Elliptic curves over \ZZ/N\ZZ with N prime are of type “elliptic curve over a finite field”:

sage: F = Zmod(101) sage: EllipticCurve(F, [2, 3]) Elliptic Curve defined by y^2 = x^3 + 2*x + 3 over Ring of integers modulo 101 sage: E = EllipticCurve([F(2), F(3)]) sage: type(E) <class ‘sage.schemes.elliptic_curves.ell_finite_field.EllipticCurve_finite_field’>

Elliptic curves over \ZZ/N\ZZ with N composite are of type “generic elliptic curve”:

sage: F = Zmod(95)
sage: EllipticCurve(F, [2, 3])
Elliptic Curve defined by y^2 = x^3 + 2*x + 3 over Ring of integers modulo 95
sage: E = EllipticCurve([F(2), F(3)])
sage: type(E)
<class 'sage.schemes.elliptic_curves.ell_generic.EllipticCurve_generic'>
_cardinality_with_j_invariant_0()

Special function to compute cardinality when j=0.

EXAMPLES: An example with q=p=1 (mod 6)

sage: F=GF(1009)
sage: [EllipticCurve(F,[0,0,0,0,11^i])._cardinality_with_j_invariant_0() for i in range(6)]
[948, 967, 1029, 1072, 1053, 991]

An example with q=p=5 (mod 6)

sage: F=GF(1013)
sage: [EllipticCurve(F,[0,0,0,0,3^i])._cardinality_with_j_invariant_0() for i in range(6)]
[1014, 1014, 1014, 1014, 1014, 1014]

An example with q=p^2, p=5 (mod 6)

sage: F.<a>=GF(1013^2,'a')
sage: [EllipticCurve(F,[0,0,0,0,a^i])._cardinality_with_j_invariant_0() for i in range(6)]
[1028196, 1027183, 1025157, 1024144, 1025157, 1027183]

For examples in characteristic 2 and 3, see the function _cardinality_with_j_invariant_1728()

_cardinality_with_j_invariant_1728()

Special function to compute cardinality when j=1728.

EXAMPLES: An example with q=p=1 (mod 4)

sage: F=GF(10009)
sage: [EllipticCurve(F,[0,0,0,11^i,0])._cardinality_with_j_invariant_1728() for i in range(4)]
[10016, 10210, 10004, 9810]

An example with q=p=3 (mod 4)

sage: F=GF(10007)
sage: [EllipticCurve(F,[0,0,0,5^i,0])._cardinality_with_j_invariant_1728() for i in range(4)]
[10008, 10008, 10008, 10008]

An example with q=p^2, p=3 (mod 4)

sage: F.<a>=GF(10007^2,'a')
sage: [EllipticCurve(F,[0,0,0,a^i,0])._cardinality_with_j_invariant_1728() for i in range(4)]
[100160064, 100140050, 100120036, 100140050]

Examples with q=2^d, d odd (3 isomorphism classes):

sage: F.<a> = GF(2**15,'a')
sage: ais = [[0,0,1,0,0],[0,0,1,1,0],[0,0,1,1,1]]
sage: curves=[EllipticCurve(F,ai) for ai in ais]
sage: all([all([e1==e2 or not e1.is_isomorphic(e2) for e1 in curves]) for e2 in curves])
True
sage: [e._cardinality_with_j_invariant_1728() for e in curves]
[32769, 33025, 32513]

Examples with q=2^d, d even (7 isomorphism classes):

sage: F.<a> = GF(2**16,'a')
sage: b = a^11 # trace 1
sage: ais = [[0,0,1,0,0],[0,0,1,0,b],[0,0,1,b,0],[0,0,a,0,0],[0,0,a,0,a^2*b],[0,0,a^2,0,0],[0,0,a^2,0,a^4*b]]
sage: curves=[EllipticCurve(F,ai) for ai in ais]
sage: all([all([e1==e2 or not e1.is_isomorphic(e2) for e1 in curves]) for e2 in curves])
True
sage: [e._cardinality_with_j_invariant_1728() for e in curves]
[65025, 66049, 65537, 65793, 65281, 65793, 65281]

Examples with q=3^d, d odd (4 isomorphism classes):

sage: F.<a> = GF(3**15,'a')
sage: b=a^7  # has trace 1
sage: ais=[[0,0,0,1,0],[0,0,0,-1,0],[0,0,0,-1,b],[0,0,0,-1,-b]]
sage: curves=[EllipticCurve(F,ai) for ai in ais]
sage: all([all([e1==e2 or not e1.is_isomorphic(e2) for e1 in curves]) for e2 in curves])
True
sage: [e._cardinality_with_j_invariant_1728() for e in curves]
[14348908, 14348908, 14342347, 14355469]

Examples with q=3^d, d even (6 isomorphism classes):

sage: F.<g>=GF(3^18,'g')
sage: i=F(-1).sqrt()
sage: a=g^8  # has trace 1
sage: ais= [[0,0,0,1,0],[0,0,0,1,i*a],[0,0,0,g,0],[0,0,0,g^3,0],[0,0,0,g^2,0], [0,0,0,g^2,i*a*g^3]]
sage: curves=[EllipticCurve(F,ai) for ai in ais]
sage: all([all([e1==e2 or not e1.is_isomorphic(e2) for e1 in curves]) for e2 in curves])
True
sage: [E._cardinality_with_j_invariant_1728() for E in curves]
[387459856, 387400807, 387420490, 387420490, 387381124, 387440173]
_gp()

Return an elliptic curve in a GP/PARI interpreter with all Cremona’s code for finite fields preloaded. This includes generators, which will vary from run to run.

The base field must have prime order.

EXAMPLES:

sage: EllipticCurve(GF(41),[2,5])._gp()
[Mod(0, 41), Mod(0, 41), Mod(0, 41), Mod(2, 41), Mod(5, 41), Mod(0, 41), Mod(4, 41), Mod(20, 41), Mod(37, 41), Mod(27, 41), Mod(26, 41), Mod(4, 41), Mod(11, 41), 44, [2, 2; 11, 1], [22, 2], ...
_pari_()

Return a GP/PARI elliptic curve

EXAMPLES:

sage: EllipticCurve(GF(41),[2,5])._pari_()
[Mod(0, 41), Mod(0, 41), Mod(0, 41), Mod(2, 41), Mod(5, 41), Mod(0, 41), Mod(4, 41), Mod(20, 41), Mod(37, 41), Mod(27, 41), Mod(26, 41), Mod(4, 41), Mod(11, 41), 0, 0, 0, 0, 0, 0]
_points_via_group_structure()

Return a list of all the points on the curve, for prime fields only (see points() for the general case)

EXAMPLES:

sage: S=EllipticCurve(GF(97),[2,3])._points_via_group_structure()
sage: len(S)
100

See trac #4687, where the following example did not work:

sage: E=EllipticCurve(GF(2),[0, 0, 1, 1, 1])
sage: E.points()
[(0 : 1 : 0)]
sage: E=EllipticCurve(GF(2),[0, 0, 1, 0, 1])
sage: E.points()
[(0 : 1 : 0), (1 : 0 : 1), (1 : 1 : 1)]
sage: E=EllipticCurve(GF(4,'a'),[0, 0, 1, 0, 1])
sage: E.points()
[(0 : 1 : 0), (0 : a : 1), (0 : a + 1 : 1), (1 : 0 : 1), (1 : 1 : 1), (a : 0 : 1), (a : 1 : 1), (a + 1 : 0 : 1), (a + 1 : 1 : 1)]
abelian_group(debug=False)

Returns the abelian group structure of the group of points on this elliptic curve.

Warning

The algorithm is definitely not intended for use with large finite fields! The factorization of the orders of elements must be feasible. Also, baby-step-giant-step methods are used which have space and time requirements which are O(\sqrt{q}).

Also, the algorithm uses random points on the curve and hence the generators are likely to differ from one run to another; but the group is cached so the generators will not change in any one run of Sage.

Note

This function applies to elliptic curves over arbitrary finite fields. The related function abelian_group_prime_field() uses the pari script, for prime fields only; it is now obsolete

INPUT:

  • debug - (default: False): if True, print debugging messages

OUTPUT:

  • an abelian group
  • tuple of images of each of the generators of the abelian group as points on this curve

AUTHORS:

  • John Cremona

EXAMPLES:

sage: E=EllipticCurve(GF(11),[2,5])
sage: E.abelian_group()                           
(Multiplicative Abelian Group isomorphic to C10, ...
sage: E=EllipticCurve(GF(41),[2,5])
sage: E.abelian_group()
(Multiplicative Abelian Group isomorphic to C22 x C2, ...
sage: F.<a>=GF(3^6,'a')
sage: E=EllipticCurve([a^4 + a^3 + 2*a^2 + 2*a, 2*a^5 + 2*a^3 + 2*a^2 + 1])
sage: E.abelian_group()
(Multiplicative Abelian Group isomorphic to C26 x C26, ...
sage: F.<a>=GF(101^3,'a')
sage: E=EllipticCurve([2*a^2 + 48*a + 27, 89*a^2 + 76*a + 24])
sage: E.abelian_group()
(Multiplicative Abelian Group isomorphic to C1031352, ...

The group can be trivial:

sage: E=EllipticCurve(GF(2),[0,0,1,1,1])
sage: E.abelian_group()
(Trivial Abelian Group, ())

Of course, there are plenty of points if we extend the field:

sage: E.cardinality(extension_degree=100)
1267650600228231653296516890625

This tests the patch for trac #3111, using 10 primes randomly selected:

sage: E = EllipticCurve('389a')
sage: for p in [5927, 2297, 1571, 1709, 3851, 127, 3253, 5783, 3499, 4817]:
...       G = E.change_ring(GF(p)).abelian_group()       
sage: for p in prime_range(10000):           #long time (~20s)
...       if p != 389:
...           G=E.change_ring(GF(p)).abelian_group()

This tests that the bug reported in trac #3926 has been fixed:

sage: K.<i> = QuadraticField(-1)
sage: OK = K.ring_of_integers()   
sage: P=K.factor(10007)[0][0]
sage: OKmodP = OK.residue_field(P)
sage: E = EllipticCurve([0,0,0,i,i+3])
sage: Emod = E.change_ring(OKmodP); Emod
Elliptic Curve defined by y^2  = x^3 + ibar*x + (ibar+3) over Residue field in ibar of Fractional ideal (10007)              
sage: Emod.abelian_group() #random generators
(Multiplicative Abelian Group isomorphic to C50067594 x C2,
((3152*ibar + 7679 : 7330*ibar + 7913 : 1), (8466*ibar + 1770 : 0 : 1)))
cardinality(algorithm='heuristic', extension_degree=1)

Return the number of points on this elliptic curve over an extension field (default: the base field).

INPUT:

  • algorithm - string (default: ‘heuristic’), used only for point counting over prime fields

    • 'heuristic' - use a heuristic to choose between pari, bsgs and sea.
    • 'pari' - use the baby step giant step method as implemented in PARI via the C-library function ellap.
    • 'sea' - use sea.gp as implemented in PARI by Christophe Doche and Sylvain Duquesne. (‘sea’ stands for ‘Schoof-Elkies-Atkin’.)
    • bsgs - use the baby step giant step method as implemented in Sage, with the Cremona - Sutherland version of Mestre’s trick.
    • all - (over prime fields only) compute cardinality with all of pari, sea and bsgs; return result if they agree or raise a RuntimeError if they do not.
  • early_abort - bool (default: False); this is used only by sea. if True, stop early if a small factor of the order is found.

  • extension_degree - int (default: 1); if the base field is k=GF(p^n) and extension_degree=d, returns the cardinality of E(GF(p^{n d})).

OUTPUT: an integer

The cardinality is cached.

Over prime fields, one of the above algorithms is used. Over non-prime fields, the serious point counting is done on a standard curve with the same j-invariant over the field GF(p)(j), then lifted to the base_field, and finally account is taken of twists.

For j=0 and j=1728 special formulas are used instead.

EXAMPLES:

sage: EllipticCurve(GF(4,'a'),[1,2,3,4,5]).cardinality()
8
sage: k.<a> = GF(3^3)
sage: l = [a^2 + 1, 2*a^2 + 2*a + 1, a^2 + a + 1, 2, 2*a]
sage: EllipticCurve(k,l).cardinality()
29
sage: l = [1, 1, 0, 2, 0]
sage: EllipticCurve(k,l).cardinality()
38

An even bigger extension (which we check against Magma):

sage: EllipticCurve(GF(3^100,'a'),[1,2,3,4,5]).cardinality()
515377520732011331036459693969645888996929981504
sage: magma.eval("Order(EllipticCurve([GF(3^100)|1,2,3,4,5]))")    # optional - magma
'515377520732011331036459693969645888996929981504'
sage: EllipticCurve(GF(10007),[1,2,3,4,5]).cardinality()
10076
sage: EllipticCurve(GF(10007),[1,2,3,4,5]).cardinality(algorithm='sea')
10076
sage: EllipticCurve(GF(10007),[1,2,3,4,5]).cardinality(algorithm='pari')
10076
sage: EllipticCurve(GF(next_prime(10**20)),[1,2,3,4,5]).cardinality(algorithm='sea')
100000000011093199520

The cardinality is cached:

sage: E = EllipticCurve(GF(3^100,'a'),[1,2,3,4,5])
sage: E.cardinality() is E.cardinality()
True        
sage: E=EllipticCurve(GF(11^2,'a'),[3,3])
sage: E.cardinality()
128
sage: EllipticCurve(GF(11^100,'a'),[3,3]).cardinality()
137806123398222701841183371720896367762643312000384671846835266941791510341065565176497846502742959856128
cardinality_bsgs(verbose=False)

Return the cardinality of self over the base field. Will be called by user function cardinality only when necessary, i.e. when the j_invariant is not in the prime 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
cardinality_exhaustive()

Return the cardinality of self over the base field. 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
cardinality_pari()

Return the cardinality of self over the (prime) base field using pari.

The result is not cached.

EXAMPLES:

sage: p=next_prime(10^3)
sage: E=EllipticCurve(GF(p),[3,4])
sage: E.cardinality_pari()
1020
sage: K=GF(next_prime(10^6))
sage: E=EllipticCurve(K,[1,0,0,1,1])
sage: E.cardinality_pari()
999945

TESTS:

sage: K.<a>=GF(3^20)
sage: E=EllipticCurve(K,[1,0,0,1,a])
sage: E.cardinality_pari()
...
ValueError: cardinality_pari() only works over prime fields.
sage: E.cardinality()
3486794310
cardinality_sea(early_abort=False)

Return the cardinality of self over the (prime) base field using sea.

INPUT:

  • early_abort - bool (default: False). if True, an early abort technique is used and the computation is interrupted as soon as a small divisor of the order is detected. The function then returns 0. This is useful for ruling out curves whose cardinality is divisible by a small prime.

The result is not cached.

EXAMPLES:

sage: p=next_prime(10^3)
sage: E=EllipticCurve(GF(p),[3,4])
sage: E.cardinality_sea()
1020
sage: K=GF(next_prime(10^6))
sage: E=EllipticCurve(K,[1,0,0,1,1])
sage: E.cardinality_sea()
999945

TESTS:

sage: K.<a>=GF(3^20)
sage: E=EllipticCurve(K,[1,0,0,1,a])
sage: E.cardinality_sea()
...
ValueError: cardinality_sea() only works over prime fields.
sage: E.cardinality()
3486794310
frobenius()

Return the frobenius of self as an element of a quadratic order

Note

This computes the curve cardinality, which may be time-consuming.

Frobenius is only determined up to conjugacy.

EXAMPLES:

sage: E=EllipticCurve(GF(11),[3,3])
sage: E.frobenius()
phi
sage: E.frobenius().minpoly()
x^2 - 4*x + 11

For some supersingular curves, Frobenius is in Z:

sage: E=EllipticCurve(GF(25,'a'),[0,0,0,0,1])
sage: E.frobenius()
-5
frobenius_order()

Return the quadratic order Z[phi] where phi is the Frobenius endomorphism of the elliptic curve

Note

This computes the curve cardinality, which may be time-consuming.

EXAMPLES:

sage: E=EllipticCurve(GF(11),[3,3])
sage: E.frobenius_order()
Order in Number Field in phi with defining polynomial x^2 - 4*x + 11

For some supersingular curves, Frobenius is in Z and the Frobenius order is Z:

sage: E=EllipticCurve(GF(25,'a'),[0,0,0,0,1])
sage: R=E.frobenius_order()
sage: R
Order in Number Field in phi with defining polynomial x + 5
sage: R.degree()
1
frobenius_polynomial()

Return the characteristic polynomial of Frobenius.

The Frobenius endomorphism of the elliptic curve has quadratic characteristic polynomial. In most cases this is irreducible and defines an imaginary quadratic order; for some supersingular curves, Frobenius is an integer a and the polynomial is (x-a)^2.

Note

This computes the curve cardinality, which may be time-consuming.

EXAMPLES:

sage: E=EllipticCurve(GF(11),[3,3])
sage: E.frobenius_polynomial()
x^2 - 4*x + 11

For some supersingular curves, Frobenius is in Z and the polynomial is a square:

sage: E=EllipticCurve(GF(25,'a'),[0,0,0,0,1]) 
sage: E.frobenius_polynomial().factor() 
(x + 5)^2
gens()

Returns a tuple of length up to 2 of points which generate the abelian group of points on this elliptic curve. See abelian_group() for limitations.

The algorithm uses random points on the curve, and hence the generators are likely to differ from one run to another; but they are cached so will be consistent in any one run of Sage.

AUTHORS:

  • John Cremona

EXAMPLES:

sage: E=EllipticCurve(GF(11),[2,5]) # random output
sage: E.gens()
((0 : 4 : 1),)
sage: EllipticCurve(GF(41),[2,5]).gens() # random output
((21 : 1 : 1), (8 : 0 : 1))
sage: F.<a>=GF(3^6,'a')
sage: E=EllipticCurve([a,a+1])
sage: pts=E.gens()
sage: len(pts)
1
sage: pts[0].order()==E.cardinality()
True
order(algorithm='heuristic', extension_degree=1)

Return the number of points on this elliptic curve over an extension field (default: the base field).

INPUT:

  • algorithm - string (default: ‘heuristic’), used only for point counting over prime fields

    • 'heuristic' - use a heuristic to choose between pari, bsgs and sea.
    • 'pari' - use the baby step giant step method as implemented in PARI via the C-library function ellap.
    • 'sea' - use sea.gp as implemented in PARI by Christophe Doche and Sylvain Duquesne. (‘sea’ stands for ‘Schoof-Elkies-Atkin’.)
    • bsgs - use the baby step giant step method as implemented in Sage, with the Cremona - Sutherland version of Mestre’s trick.
    • all - (over prime fields only) compute cardinality with all of pari, sea and bsgs; return result if they agree or raise a RuntimeError if they do not.
  • early_abort - bool (default: False); this is used only by sea. if True, stop early if a small factor of the order is found.

  • extension_degree - int (default: 1); if the base field is k=GF(p^n) and extension_degree=d, returns the cardinality of E(GF(p^{n d})).

OUTPUT: an integer

The cardinality is cached.

Over prime fields, one of the above algorithms is used. Over non-prime fields, the serious point counting is done on a standard curve with the same j-invariant over the field GF(p)(j), then lifted to the base_field, and finally account is taken of twists.

For j=0 and j=1728 special formulas are used instead.

EXAMPLES:

sage: EllipticCurve(GF(4,'a'),[1,2,3,4,5]).cardinality()
8
sage: k.<a> = GF(3^3)
sage: l = [a^2 + 1, 2*a^2 + 2*a + 1, a^2 + a + 1, 2, 2*a]
sage: EllipticCurve(k,l).cardinality()
29
sage: l = [1, 1, 0, 2, 0]
sage: EllipticCurve(k,l).cardinality()
38

An even bigger extension (which we check against Magma):

sage: EllipticCurve(GF(3^100,'a'),[1,2,3,4,5]).cardinality()
515377520732011331036459693969645888996929981504
sage: magma.eval("Order(EllipticCurve([GF(3^100)|1,2,3,4,5]))")    # optional - magma
'515377520732011331036459693969645888996929981504'
sage: EllipticCurve(GF(10007),[1,2,3,4,5]).cardinality()
10076
sage: EllipticCurve(GF(10007),[1,2,3,4,5]).cardinality(algorithm='sea')
10076
sage: EllipticCurve(GF(10007),[1,2,3,4,5]).cardinality(algorithm='pari')
10076
sage: EllipticCurve(GF(next_prime(10**20)),[1,2,3,4,5]).cardinality(algorithm='sea')
100000000011093199520

The cardinality is cached:

sage: E = EllipticCurve(GF(3^100,'a'),[1,2,3,4,5])
sage: E.cardinality() is E.cardinality()
True        
sage: E=EllipticCurve(GF(11^2,'a'),[3,3])
sage: E.cardinality()
128
sage: EllipticCurve(GF(11^100,'a'),[3,3]).cardinality()
137806123398222701841183371720896367762643312000384671846835266941791510341065565176497846502742959856128
plot(*args, **kwds)

Draw a graph of this elliptic curve over a prime finite field.

INPUT:

  • *args, **kwds - all other options are passed to the circle graphing primitive.

EXAMPLES:

sage: E = EllipticCurve(FiniteField(17), [0,1])
sage: P = plot(E, rgbcolor=(0,0,1))
points()

All the points on this elliptic curve. The list of points is cached so subsequent calls are free.

EXAMPLES:

sage: p = 5
sage: F = GF(p)
sage: E = EllipticCurve(F, [1, 3])
sage: a_sub_p = E.change_ring(QQ).ap(p); a_sub_p
2
sage: len(E.points())
4
sage: p + 1 - a_sub_p
4
sage: E.points()
[(0 : 1 : 0), (1 : 0 : 1), (4 : 1 : 1), (4 : 4 : 1)]
sage: K = GF(p**2,'a')
sage: E = E.change_ring(K)
sage: len(E.points())
32
sage: (p + 1)**2 - a_sub_p**2
32
sage: w = E.points(); w
[(0 : 1 : 0), (0 : 2*a + 4 : 1), (0 : 3*a + 1 : 1), (1 : 0 : 1), (2 : 2*a + 4 : 1), (2 : 3*a + 1 : 1), (3 : 2*a + 4 : 1), (3 : 3*a + 1 : 1), (4 : 1 : 1), (4 : 4 : 1), (a : 1 : 1), (a : 4 : 1), (a + 2 : a + 1 : 1), (a + 2 : 4*a + 4 : 1), (a + 3 : a : 1), (a + 3 : 4*a : 1), (a + 4 : 0 : 1), (2*a : 2*a : 1), (2*a : 3*a : 1), (2*a + 4 : a + 1 : 1), (2*a + 4 : 4*a + 4 : 1), (3*a + 1 : a + 3 : 1), (3*a + 1 : 4*a + 2 : 1), (3*a + 2 : 2*a + 3 : 1), (3*a + 2 : 3*a + 2 : 1), (4*a : 0 : 1), (4*a + 1 : 1 : 1), (4*a + 1 : 4 : 1), (4*a + 3 : a + 3 : 1), (4*a + 3 : 4*a + 2 : 1), (4*a + 4 : a + 4 : 1), (4*a + 4 : 4*a + 1 : 1)]

Note that the returned list is an immutable sorted Sequence:

sage: w[0] = 9
...
ValueError: object is immutable; please change a copy instead.
random_element()

Returns a random point on this elliptic curve.

Returns the point at infinity with probability 1/(q+1) where the base field has cardinality q.

EXAMPLES:

sage: k = GF(next_prime(7^5))
sage: E = EllipticCurve(k,[2,4])
sage: P = E.random_element(); P
(751 : 6230 : 1)
sage: type(P)
<class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
sage: P in E
True
sage: k.<a> = GF(7^5)
sage: E = EllipticCurve(k,[2,4])
sage: P = E.random_element(); P
(a^4 + a + 5 : 6*a^4 + 3*a^3 + 2*a^2 + 4 : 1)
sage: type(P)
<class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
sage: P in E
True
sage: k.<a> = GF(2^5)
sage: E = EllipticCurve(k,[a^2,a,1,a+1,1])
sage: P = E.random_element(); P
(a^4 : 0 : 1)
sage: type(P)
<class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
sage: P in E
True
random_point()

Returns a random point on this elliptic curve.

Returns the point at infinity with probability 1/(q+1) where the base field has cardinality q.

EXAMPLES:

sage: k = GF(next_prime(7^5))
sage: E = EllipticCurve(k,[2,4])
sage: P = E.random_element(); P
(751 : 6230 : 1)
sage: type(P)
<class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
sage: P in E
True
sage: k.<a> = GF(7^5)
sage: E = EllipticCurve(k,[2,4])
sage: P = E.random_element(); P
(a^4 + a + 5 : 6*a^4 + 3*a^3 + 2*a^2 + 4 : 1)
sage: type(P)
<class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
sage: P in E
True
sage: k.<a> = GF(2^5)
sage: E = EllipticCurve(k,[a^2,a,1,a+1,1])
sage: P = E.random_element(); P
(a^4 : 0 : 1)
sage: type(P)
<class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
sage: P in E
True
trace_of_frobenius()

Return the trace of Frobenius acting on this elliptic curve.

Note

This computes the curve cardinality, which may be time-consuming.

EXAMPLES:

sage: E=EllipticCurve(GF(101),[2,3])
sage: E.trace_of_frobenius()
6
sage: E=EllipticCurve(GF(11^5,'a'),[2,5])
sage: E.trace_of_frobenius()
802

The following shows that the issue from trac #2849 is fixed:

sage: E=EllipticCurve(GF(3^5,'a'),[-1,-1])
sage: E.trace_of_frobenius()
-27

Previous topic

Elliptic curves over number fields.

Next topic

Points on elliptic curves

This Page