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
Mariah Lenox (2011-03): Added set_order method
Lorenz Panny, John Cremona (2023-02): .twists()
Lorenz Panny (2023): special_supersingular_curve()
Martin Grenouilloux, Gareth Ma (2024-09): EllipticCurve_with_prime_order()

class sage.schemes.elliptic_curves.ell_finite_field.EllipticCurve_finite_field(R, data, category=None)[source]¶

Bases: EllipticCurve_field

Elliptic curve over a finite field.

EXAMPLES:

Sage

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

sage: # needs sage.rings.finite_rings
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

Python

>>> from sage.all import *
>>> EllipticCurve(GF(Integer(101)),[Integer(2),Integer(3)])
Elliptic Curve defined by y^2  = x^3 + 2*x + 3 over Finite Field of size 101

>>> # needs sage.rings.finite_rings
>>> F = GF(Integer(101)**Integer(2), 'a')
>>> EllipticCurve([F(Integer(2)),F(Integer(3))])
Elliptic Curve defined by y^2  = x^3 + 2*x + 3 over Finite Field in a of size 101^2

Sage Live

EllipticCurve(GF(101),[2,3])
# needs sage.rings.finite_rings
F = GF(101^2, 'a')
EllipticCurve([F(2),F(3)])

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

Sage

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_with_category'>
sage: E.category()
Category of abelian varieties over Ring of integers modulo 101

Python

>>> from sage.all import *
>>> F = Zmod(Integer(101))
>>> EllipticCurve(F, [Integer(2), Integer(3)])
Elliptic Curve defined by y^2 = x^3 + 2*x + 3 over Ring of integers modulo 101
>>> E = EllipticCurve([F(Integer(2)), F(Integer(3))])
>>> type(E)
<class 'sage.schemes.elliptic_curves.ell_finite_field.EllipticCurve_finite_field_with_category'>
>>> E.category()
Category of abelian varieties over Ring of integers modulo 101

Sage Live

F = Zmod(101)
EllipticCurve(F, [2, 3])
E = EllipticCurve([F(2), F(3)])
type(E)
E.category()

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

Sage

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_with_category'>
sage: E.category()
Category of schemes over Ring of integers modulo 95
sage: TestSuite(E).run(skip=["_test_elements"])

Python

>>> from sage.all import *
>>> F = Zmod(Integer(95))
>>> EllipticCurve(F, [Integer(2), Integer(3)])
Elliptic Curve defined by y^2 = x^3 + 2*x + 3 over Ring of integers modulo 95
>>> E = EllipticCurve([F(Integer(2)), F(Integer(3))])
>>> type(E)
<class 'sage.schemes.elliptic_curves.ell_generic.EllipticCurve_generic_with_category'>
>>> E.category()
Category of schemes over Ring of integers modulo 95
>>> TestSuite(E).run(skip=["_test_elements"])

Sage Live

F = Zmod(95)
EllipticCurve(F, [2, 3])
E = EllipticCurve([F(2), F(3)])
type(E)
E.category()
TestSuite(E).run(skip=["_test_elements"])

abelian_group()[source]¶

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

See also

If you do not need the complete abelian group structure but only generators of the group, use gens() which can be much faster in some cases.

This method relies on gens(), which uses random points on the curve and hence the generators are likely to differ from one run to another. However, the group is cached, so the generators will not change in any one run of Sage.

OUTPUT:

an AdditiveAbelianGroupWrapper object encapsulating the abelian group of rational points on this elliptic curve

ALGORITHM:

We first call gens() to obtain a generating set \((P,Q)\). Letting \(P\) denote the point of larger order \(n_1\), we extend \(P\) to a basis \((P,Q')\) by computing a scalar \(x\) such that \(Q'=Q-[x]P\) has order \(n_2=\#E/n_1\). Finding \(x\) involves a (typically easy) discrete-logarithm computation.

The complexity of the algorithm is the cost of factoring the group order, plus \(\Theta(\sqrt{\ell})\) for each prime \(\ell\) such that the rational \(\ell^\infty\)-torsion of self is isomorphic to \(\ZZ/\ell^r\times\ZZ/\ell^s\) with \(r>s>0\), times a polynomial in the logarithm of the base-field size.

AUTHORS:

John Cremona: original implementation
Lorenz Panny (2021): current implementation

EXAMPLES:

Sage

sage: E = EllipticCurve(GF(11),[2,5])
sage: E.abelian_group()
Additive abelian group isomorphic to Z/10 embedded in
 Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 2*x + 5
  over Finite Field of size 11

Python

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(11)),[Integer(2),Integer(5)])
>>> E.abelian_group()
Additive abelian group isomorphic to Z/10 embedded in
 Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 2*x + 5
  over Finite Field of size 11

Sage Live

E = EllipticCurve(GF(11),[2,5])
E.abelian_group()

Sage

sage: E = EllipticCurve(GF(41),[2,5])
sage: E.abelian_group()
Additive abelian group isomorphic to Z/22 + Z/2 ...

Python

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(41)),[Integer(2),Integer(5)])
>>> E.abelian_group()
Additive abelian group isomorphic to Z/22 + Z/2 ...

Sage Live

E = EllipticCurve(GF(41),[2,5])
E.abelian_group()

Python

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(41)),[Integer(2),Integer(5)])
>>> E.abelian_group()
Additive abelian group isomorphic to Z/22 + Z/2 ...

Sage Live

E = EllipticCurve(GF(41),[2,5])
E.abelian_group()

Sage

sage: # needs sage.rings.finite_rings
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()
Additive abelian group isomorphic to Z/26 + Z/26 ...

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> F = GF(Integer(3)**Integer(6),'a', names=('a',)); (a,) = F._first_ngens(1)
>>> E = EllipticCurve([a**Integer(4) + a**Integer(3) + Integer(2)*a**Integer(2) + Integer(2)*a, Integer(2)*a**Integer(5) + Integer(2)*a**Integer(3) + Integer(2)*a**Integer(2) + Integer(1)])
>>> E.abelian_group()
Additive abelian group isomorphic to Z/26 + Z/26 ...

Sage Live

# needs sage.rings.finite_rings
F.<a> = GF(3^6,'a')
E = EllipticCurve([a^4 + a^3 + 2*a^2 + 2*a, 2*a^5 + 2*a^3 + 2*a^2 + 1])
E.abelian_group()

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> F = GF(Integer(3)**Integer(6),'a', names=('a',)); (a,) = F._first_ngens(1)
>>> E = EllipticCurve([a**Integer(4) + a**Integer(3) + Integer(2)*a**Integer(2) + Integer(2)*a, Integer(2)*a**Integer(5) + Integer(2)*a**Integer(3) + Integer(2)*a**Integer(2) + Integer(1)])
>>> E.abelian_group()
Additive abelian group isomorphic to Z/26 + Z/26 ...

Sage Live

# needs sage.rings.finite_rings
F.<a> = GF(3^6,'a')
E = EllipticCurve([a^4 + a^3 + 2*a^2 + 2*a, 2*a^5 + 2*a^3 + 2*a^2 + 1])
E.abelian_group()

Sage

sage: # needs sage.rings.finite_rings
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()
Additive abelian group isomorphic to Z/1031352 ...

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> 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.abelian_group()
Additive abelian group isomorphic to Z/1031352 ...

Sage Live

# needs sage.rings.finite_rings
F.<a> = GF(101^3,'a')
E = EllipticCurve([2*a^2 + 48*a + 27, 89*a^2 + 76*a + 24])
E.abelian_group()

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> 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.abelian_group()
Additive abelian group isomorphic to Z/1031352 ...

Sage Live

# needs sage.rings.finite_rings
F.<a> = GF(101^3,'a')
E = EllipticCurve([2*a^2 + 48*a + 27, 89*a^2 + 76*a + 24])
E.abelian_group()

The group can be trivial:

Sage

sage: E = EllipticCurve(GF(2), [0,0,1,1,1])
sage: E.abelian_group()
Trivial group embedded in Abelian group of points on
 Elliptic Curve defined by y^2 + y = x^3 + x + 1 over Finite Field of size 2

Python

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(2)), [Integer(0),Integer(0),Integer(1),Integer(1),Integer(1)])
>>> E.abelian_group()
Trivial group embedded in Abelian group of points on
 Elliptic Curve defined by y^2 + y = x^3 + x + 1 over Finite Field of size 2

Sage Live

E = EllipticCurve(GF(2), [0,0,1,1,1])
E.abelian_group()

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

Sage

sage: E.cardinality(extension_degree=100)
1267650600228231653296516890625

Python

>>> from sage.all import *
>>> E.cardinality(extension_degree=Integer(100))
1267650600228231653296516890625

Sage Live

E.cardinality(extension_degree=100)

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

Sage

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 (19s on sage.math, 2011)
....:     if p != 389:
....:         G = E.change_ring(GF(p)).abelian_group()

Python

>>> from sage.all import *
>>> E = EllipticCurve('389a')
>>> for p in [Integer(5927), Integer(2297), Integer(1571), Integer(1709), Integer(3851), Integer(127), Integer(3253), Integer(5783), Integer(3499), Integer(4817)]:
...     G = E.change_ring(GF(p)).abelian_group()
>>> for p in prime_range(Integer(10000)):  # long time (19s on sage.math, 2011)
...     if p != Integer(389):
...         G = E.change_ring(GF(p)).abelian_group()

Sage Live

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

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

Sage

sage: # needs sage.rings.number_field
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)))

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> K = QuadraticField(-Integer(1), names=('i',)); (i,) = K._first_ngens(1)
>>> OK = K.ring_of_integers()
>>> P = K.factor(Integer(10007))[Integer(0)][Integer(0)]
>>> OKmodP = OK.residue_field(P)
>>> E = EllipticCurve([Integer(0), Integer(0), Integer(0), i, i + Integer(3)])
>>> 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)
>>> 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)))

Sage Live

# needs sage.rings.number_field
K.<i> = QuadraticField(-1)
OK = K.ring_of_integers()
P = K.factor(10007)[0][0]
OKmodP = OK.residue_field(P)
E = EllipticCurve([0, 0, 0, i, i + 3])
Emod = E.change_ring(OKmodP); Emod
Emod.abelian_group() #random generators

cardinality(algorithm=None, extension_degree=1)[source]¶

Return the number of points on this elliptic curve.

INPUT:

algorithm – (optional) string:
- 'pari' – use the PARI C-library function ellcard
- 'bsgs' – use the baby-step giant-step method as
  implemented in Sage, with the Cremona-Sutherland version of Mestre’s trick
- 'exhaustive' – naive point counting
- 'subfield' – reduce to a smaller field, provided that the j-invariant lies in a subfield
- 'all' – compute cardinality with both 'pari' and 'bsgs'; return result if they agree or raise a AssertionError if they do not
extension_degree – integer \(d\) (default: 1); if the base field is \(\GF{q}\), return the cardinality of self over the extension \(\GF{q^d}\) of degree \(d\)

OUTPUT:

The order of the group of rational points of self over its base field, or over an extension field of degree \(d\) as above. The result is cached.

EXAMPLES:

Sage

sage: # needs sage.rings.finite_rings
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

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> EllipticCurve(GF(Integer(4), 'a'), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]).cardinality()
8
>>> k = GF(Integer(3)**Integer(3), names=('a',)); (a,) = k._first_ngens(1)
>>> l = [a**Integer(2) + Integer(1), Integer(2)*a**Integer(2) + Integer(2)*a + Integer(1), a**Integer(2) + a + Integer(1), Integer(2), Integer(2)*a]
>>> EllipticCurve(k,l).cardinality()
29

Sage Live

# needs sage.rings.finite_rings
EllipticCurve(GF(4, 'a'), [1,2,3,4,5]).cardinality()
k.<a> = GF(3^3)
l = [a^2 + 1, 2*a^2 + 2*a + 1, a^2 + a + 1, 2, 2*a]
EllipticCurve(k,l).cardinality()

Sage

sage: # needs sage.rings.finite_rings
sage: l = [1, 1, 0, 2, 0]
sage: EllipticCurve(k, l).cardinality()
38

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> l = [Integer(1), Integer(1), Integer(0), Integer(2), Integer(0)]
>>> EllipticCurve(k, l).cardinality()
38

Sage Live

# needs sage.rings.finite_rings
l = [1, 1, 0, 2, 0]
EllipticCurve(k, l).cardinality()

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> l = [Integer(1), Integer(1), Integer(0), Integer(2), Integer(0)]
>>> EllipticCurve(k, l).cardinality()
38

Sage Live

# needs sage.rings.finite_rings
l = [1, 1, 0, 2, 0]
EllipticCurve(k, l).cardinality()

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

Sage

sage: # needs sage.rings.finite_rings
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'

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> EllipticCurve(GF(Integer(3)**Integer(100), 'a'), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]).cardinality()
515377520732011331036459693969645888996929981504
>>> magma.eval("Order(EllipticCurve([GF(3^100)|1,2,3,4,5]))")    # optional - magma
'515377520732011331036459693969645888996929981504'

Sage Live

# needs sage.rings.finite_rings
EllipticCurve(GF(3^100, 'a'), [1,2,3,4,5]).cardinality()
magma.eval("Order(EllipticCurve([GF(3^100)|1,2,3,4,5]))")    # optional - magma

Sage

sage: EllipticCurve(GF(10007), [1,2,3,4,5]).cardinality()
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()
100000000011093199520

Python

>>> from sage.all import *
>>> EllipticCurve(GF(Integer(10007)), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]).cardinality()
10076
>>> EllipticCurve(GF(Integer(10007)), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]).cardinality(algorithm='pari')
10076
>>> EllipticCurve(GF(next_prime(Integer(10)**Integer(20))), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]).cardinality()
100000000011093199520

Sage Live

EllipticCurve(GF(10007), [1,2,3,4,5]).cardinality()
EllipticCurve(GF(10007), [1,2,3,4,5]).cardinality(algorithm='pari')
EllipticCurve(GF(next_prime(10**20)), [1,2,3,4,5]).cardinality()

Python

>>> from sage.all import *
>>> EllipticCurve(GF(Integer(10007)), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]).cardinality()
10076
>>> EllipticCurve(GF(Integer(10007)), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]).cardinality(algorithm='pari')
10076
>>> EllipticCurve(GF(next_prime(Integer(10)**Integer(20))), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]).cardinality()
100000000011093199520

Sage Live

EllipticCurve(GF(10007), [1,2,3,4,5]).cardinality()
EllipticCurve(GF(10007), [1,2,3,4,5]).cardinality(algorithm='pari')
EllipticCurve(GF(next_prime(10**20)), [1,2,3,4,5]).cardinality()

The cardinality is cached:

Sage

sage: # needs sage.rings.finite_rings
sage: E = EllipticCurve(GF(3^100, 'a'), [1,2,3,4,5])
sage: E.cardinality() is E.cardinality()
True

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> E = EllipticCurve(GF(Integer(3)**Integer(100), 'a'), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)])
>>> E.cardinality() is E.cardinality()
True

Sage Live

# needs sage.rings.finite_rings
E = EllipticCurve(GF(3^100, 'a'), [1,2,3,4,5])
E.cardinality() is E.cardinality()

The following is very fast since the curve is actually defined over the prime field:

Sage

sage: # needs sage.rings.finite_rings
sage: k.<a> = GF(11^100)
sage: E1 = EllipticCurve(k, [3,3])
sage: N1 = E1.cardinality(algorithm='subfield'); N1
137806123398222701841183371720896367762643312000384671846835266941791510341065565176497846502742959856128
sage: E1.cardinality_pari() == N1
True
sage: E2 = E1.quadratic_twist()
sage: N2 = E2.cardinality(algorithm='subfield'); N2
137806123398222701841183371720896367762643312000384656816094284101308193849980588362304472492174093035876
sage: E2.cardinality_pari() == N2
True
sage: N1 + N2 == 2*(k.cardinality() + 1)
True

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(11)**Integer(100), names=('a',)); (a,) = k._first_ngens(1)
>>> E1 = EllipticCurve(k, [Integer(3),Integer(3)])
>>> N1 = E1.cardinality(algorithm='subfield'); N1
137806123398222701841183371720896367762643312000384671846835266941791510341065565176497846502742959856128
>>> E1.cardinality_pari() == N1
True
>>> E2 = E1.quadratic_twist()
>>> N2 = E2.cardinality(algorithm='subfield'); N2
137806123398222701841183371720896367762643312000384656816094284101308193849980588362304472492174093035876
>>> E2.cardinality_pari() == N2
True
>>> N1 + N2 == Integer(2)*(k.cardinality() + Integer(1))
True

Sage Live

# needs sage.rings.finite_rings
k.<a> = GF(11^100)
E1 = EllipticCurve(k, [3,3])
N1 = E1.cardinality(algorithm='subfield'); N1
E1.cardinality_pari() == N1
E2 = E1.quadratic_twist()
N2 = E2.cardinality(algorithm='subfield'); N2
E2.cardinality_pari() == N2
N1 + N2 == 2*(k.cardinality() + 1)

We can count points over curves defined as a reduction:

Sage

sage: # needs sage.rings.number_field
sage: x = polygen(QQ)
sage: K.<w> = NumberField(x^2 + x + 1)
sage: EK = EllipticCurve(K, [0, 0, w, 2, 1])
sage: E = EK.base_extend(K.residue_field(2))
sage: E
Elliptic Curve defined by y^2 + wbar*y = x^3 + 1
 over Residue field in wbar of Fractional ideal (2)
sage: E.cardinality()
7
sage: E = EK.base_extend(K.residue_field(w - 1))
sage: E.abelian_group()
Trivial group embedded in Abelian group of points on Elliptic Curve defined
 by y^2 + y = x^3 + 2*x + 1 over Residue field of Fractional ideal (w - 1)

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> x = polygen(QQ)
>>> K = NumberField(x**Integer(2) + x + Integer(1), names=('w',)); (w,) = K._first_ngens(1)
>>> EK = EllipticCurve(K, [Integer(0), Integer(0), w, Integer(2), Integer(1)])
>>> E = EK.base_extend(K.residue_field(Integer(2)))
>>> E
Elliptic Curve defined by y^2 + wbar*y = x^3 + 1
 over Residue field in wbar of Fractional ideal (2)
>>> E.cardinality()
7
>>> E = EK.base_extend(K.residue_field(w - Integer(1)))
>>> E.abelian_group()
Trivial group embedded in Abelian group of points on Elliptic Curve defined
 by y^2 + y = x^3 + 2*x + 1 over Residue field of Fractional ideal (w - 1)

Sage Live

# needs sage.rings.number_field
x = polygen(QQ)
K.<w> = NumberField(x^2 + x + 1)
EK = EllipticCurve(K, [0, 0, w, 2, 1])
E = EK.base_extend(K.residue_field(2))
E
E.cardinality()
E = EK.base_extend(K.residue_field(w - 1))
E.abelian_group()

Sage

sage: R.<x> = GF(17)[]
sage: pol = R.irreducible_element(5)
sage: k.<a> = R.residue_field(pol)
sage: E = EllipticCurve(R, [1, x]).base_extend(k)
sage: E
Elliptic Curve defined by y^2 = x^3 + x + a
 over Residue field in a of Principal ideal (x^5 + x + 14)
  of Univariate Polynomial Ring in x over Finite Field of size 17
sage: E.cardinality()
1421004

Python

>>> from sage.all import *
>>> R = GF(Integer(17))['x']; (x,) = R._first_ngens(1)
>>> pol = R.irreducible_element(Integer(5))
>>> k = R.residue_field(pol, names=('a',)); (a,) = k._first_ngens(1)
>>> E = EllipticCurve(R, [Integer(1), x]).base_extend(k)
>>> E
Elliptic Curve defined by y^2 = x^3 + x + a
 over Residue field in a of Principal ideal (x^5 + x + 14)
  of Univariate Polynomial Ring in x over Finite Field of size 17
>>> E.cardinality()
1421004

Sage Live

R.<x> = GF(17)[]
pol = R.irreducible_element(5)
k.<a> = R.residue_field(pol)
E = EllipticCurve(R, [1, x]).base_extend(k)
E
E.cardinality()

Python

>>> from sage.all import *
>>> R = GF(Integer(17))['x']; (x,) = R._first_ngens(1)
>>> pol = R.irreducible_element(Integer(5))
>>> k = R.residue_field(pol, names=('a',)); (a,) = k._first_ngens(1)
>>> E = EllipticCurve(R, [Integer(1), x]).base_extend(k)
>>> E
Elliptic Curve defined by y^2 = x^3 + x + a
 over Residue field in a of Principal ideal (x^5 + x + 14)
  of Univariate Polynomial Ring in x over Finite Field of size 17
>>> E.cardinality()
1421004

Sage Live

R.<x> = GF(17)[]
pol = R.irreducible_element(5)
k.<a> = R.residue_field(pol)
E = EllipticCurve(R, [1, x]).base_extend(k)
E
E.cardinality()

cardinality_bsgs(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

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

Python

>>> 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 Live

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

cardinality_exhaustive()[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

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

Python

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

Sage Live

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

cardinality_pari()[source]¶

Return the cardinality of self using PARI.

This uses pari:ellcard.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> p = next_prime(Integer(10)**Integer(3))
>>> E = EllipticCurve(GF(p),[Integer(3),Integer(4)])
>>> E.cardinality_pari()
1020
>>> K = GF(next_prime(Integer(10)**Integer(6)))
>>> E = EllipticCurve(K,[Integer(1),Integer(0),Integer(0),Integer(1),Integer(1)])
>>> E.cardinality_pari()
999945

Sage Live

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

Since Issue #16931, this now works over finite fields which are not prime fields:

Sage

sage: # needs sage.rings.finite_rings
sage: k.<a> = GF(7^3)
sage: E = EllipticCurve_from_j(a)
sage: E.cardinality_pari()
318
sage: K.<a> = GF(3^20)
sage: E = EllipticCurve(K,[1,0,0,1,a])
sage: E.cardinality_pari()
3486794310

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(7)**Integer(3), names=('a',)); (a,) = k._first_ngens(1)
>>> E = EllipticCurve_from_j(a)
>>> E.cardinality_pari()
318
>>> K = GF(Integer(3)**Integer(20), names=('a',)); (a,) = K._first_ngens(1)
>>> E = EllipticCurve(K,[Integer(1),Integer(0),Integer(0),Integer(1),a])
>>> E.cardinality_pari()
3486794310

Sage Live

# needs sage.rings.finite_rings
k.<a> = GF(7^3)
E = EllipticCurve_from_j(a)
E.cardinality_pari()
K.<a> = GF(3^20)
E = EllipticCurve(K,[1,0,0,1,a])
E.cardinality_pari()

count_points(n=1)[source]¶

Return the cardinality of this elliptic curve over the base field or extensions.

INPUT:

n – positive integer

OUTPUT: if \(n=1\), returns the cardinality of the curve over its base field

If \(n>1\), returns a list \([c_1, c_2, ..., c_n]\) where \(c_d\) is the cardinality of the curve over the extension of degree \(d\) of its base field.

EXAMPLES:

Sage

sage: p = 101
sage: F = GF(p)
sage: E = EllipticCurve(F, [2,3])
sage: E.count_points(1)
96
sage: E.count_points(5)
[96, 10368, 1031904, 104053248, 10509895776]

Python

>>> from sage.all import *
>>> p = Integer(101)
>>> F = GF(p)
>>> E = EllipticCurve(F, [Integer(2),Integer(3)])
>>> E.count_points(Integer(1))
96
>>> E.count_points(Integer(5))
[96, 10368, 1031904, 104053248, 10509895776]

Sage Live

p = 101
F = GF(p)
E = EllipticCurve(F, [2,3])
E.count_points(1)
E.count_points(5)

Sage

sage: # needs sage.rings.finite_rings
sage: F.<a> = GF(p^2)
sage: E = EllipticCurve(F, [a,a])
sage: E.cardinality()
10295
sage: E.count_points()
10295
sage: E.count_points(1)
10295
sage: E.count_points(5)
[10295, 104072155, 1061518108880, 10828567126268595, 110462212555439192375]

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> F = GF(p**Integer(2), names=('a',)); (a,) = F._first_ngens(1)
>>> E = EllipticCurve(F, [a,a])
>>> E.cardinality()
10295
>>> E.count_points()
10295
>>> E.count_points(Integer(1))
10295
>>> E.count_points(Integer(5))
[10295, 104072155, 1061518108880, 10828567126268595, 110462212555439192375]

Sage Live

# needs sage.rings.finite_rings
F.<a> = GF(p^2)
E = EllipticCurve(F, [a,a])
E.cardinality()
E.count_points()
E.count_points(1)
E.count_points(5)

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> F = GF(p**Integer(2), names=('a',)); (a,) = F._first_ngens(1)
>>> E = EllipticCurve(F, [a,a])
>>> E.cardinality()
10295
>>> E.count_points()
10295
>>> E.count_points(Integer(1))
10295
>>> E.count_points(Integer(5))
[10295, 104072155, 1061518108880, 10828567126268595, 110462212555439192375]

Sage Live

# needs sage.rings.finite_rings
F.<a> = GF(p^2)
E = EllipticCurve(F, [a,a])
E.cardinality()
E.count_points()
E.count_points(1)
E.count_points(5)

endomorphism_discriminant_from_class_number(h)[source]¶

Return the endomorphism order discriminant of this ordinary elliptic curve, given its class number h.

INPUT:

h – positive integer

OUTPUT:

integer; the discriminant of the endomorphism ring \(\text{End}(E)\), if this has class number h. If \(\text{End}(E)\) does not have class number h, a ValueError is raised.

ALGORITHM:

Compute the trace of Frobenius and hence the discriminant \(D_0\) and class number \(h_0\) of the maximal order containing the endomorphism order. From the given value of \(h\), which must be a multiple of \(h_0\), compute the possible conductors, using height_above_floor() for each prime \(\ell\) dividing the quotient \(h/h_0\). If exactly one conductor \(f\) remains, return \(f^2D_0\), otherwise raise a ValueError; this can onlyhappen when the input value of \(h\) was incorrect.

Note

Adapted from [RouSuthZur2022]. The application for which one knows the class number in advance is in the recognition of Hilbert Class Polynomials: see sage.schemes.elliptic_curves.cm.is_HCP().

EXAMPLES:

Sage

sage: F = GF(312401)
sage: E = EllipticCurve(F,(0, 0, 0, 309381, 93465))
sage: E.endomorphism_discriminant_from_class_number(30)
-671

Python

>>> from sage.all import *
>>> F = GF(Integer(312401))
>>> E = EllipticCurve(F,(Integer(0), Integer(0), Integer(0), Integer(309381), Integer(93465)))
>>> E.endomorphism_discriminant_from_class_number(Integer(30))
-671

Sage Live

F = GF(312401)
E = EllipticCurve(F,(0, 0, 0, 309381, 93465))
E.endomorphism_discriminant_from_class_number(30)

We check that this is the correct discriminant, and the input value of \(h\) was correct:

Sage

sage: H = hilbert_class_polynomial(-671)
sage: H(E.j_invariant()) == 0 and H.degree()==30
True

Python

>>> from sage.all import *
>>> H = hilbert_class_polynomial(-Integer(671))
>>> H(E.j_invariant()) == Integer(0) and H.degree()==Integer(30)
True

Sage Live

H = hilbert_class_polynomial(-671)
H(E.j_invariant()) == 0 and H.degree()==30

frobenius()[source]¶

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

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

Python

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(11)),[Integer(3),Integer(3)])
>>> E.frobenius()
phi
>>> E.frobenius().minpoly()
x^2 - 4*x + 11

Sage Live

E = EllipticCurve(GF(11),[3,3])
E.frobenius()
E.frobenius().minpoly()

For some supersingular curves, Frobenius is in Z:

Sage

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

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> E = EllipticCurve(GF(Integer(25),'a'),[Integer(0),Integer(0),Integer(0),Integer(0),Integer(1)])
>>> E.frobenius()
-5

Sage Live

# needs sage.rings.finite_rings
E = EllipticCurve(GF(25,'a'),[0,0,0,0,1])
E.frobenius()

frobenius_discriminant()[source]¶

Return the discriminant of the ring \(\ZZ[\pi_E]\) where \(\pi_E\) is the Frobenius endomorphism.

EXAMPLES:

Sage

sage: # needs sage.rings.finite_rings
sage: F.<t> = GF(11^4)
sage: E = EllipticCurve([t,t])
sage: E.frobenius_discriminant()
-57339

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> F = GF(Integer(11)**Integer(4), names=('t',)); (t,) = F._first_ngens(1)
>>> E = EllipticCurve([t,t])
>>> E.frobenius_discriminant()
-57339

Sage Live

# needs sage.rings.finite_rings
F.<t> = GF(11^4)
E = EllipticCurve([t,t])
E.frobenius_discriminant()

frobenius_endomorphism()[source]¶

Return the \(q\)-power Frobenius endomorphism of this elliptic curve, where \(q\) is the cardinality of the (finite) base field.

EXAMPLES:

Sage

sage: # needs sage.rings.finite_rings
sage: F.<t> = GF(11^4)
sage: E = EllipticCurve([t,t])
sage: E.frobenius_endomorphism()
Frobenius endomorphism of degree 14641 = 11^4:
  From: Elliptic Curve defined by y^2 = x^3 + t*x + t over Finite Field in t of size 11^4
  To:   Elliptic Curve defined by y^2 = x^3 + t*x + t over Finite Field in t of size 11^4
sage: E.frobenius_endomorphism() == E.frobenius_isogeny(4)
True

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> F = GF(Integer(11)**Integer(4), names=('t',)); (t,) = F._first_ngens(1)
>>> E = EllipticCurve([t,t])
>>> E.frobenius_endomorphism()
Frobenius endomorphism of degree 14641 = 11^4:
  From: Elliptic Curve defined by y^2 = x^3 + t*x + t over Finite Field in t of size 11^4
  To:   Elliptic Curve defined by y^2 = x^3 + t*x + t over Finite Field in t of size 11^4
>>> E.frobenius_endomorphism() == E.frobenius_isogeny(Integer(4))
True

Sage Live

# needs sage.rings.finite_rings
F.<t> = GF(11^4)
E = EllipticCurve([t,t])
E.frobenius_endomorphism()
E.frobenius_endomorphism() == E.frobenius_isogeny(4)

See also

frobenius_isogeny()

frobenius_order()[source]¶

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

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

Python

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(11)),[Integer(3),Integer(3)])
>>> E.frobenius_order()
Order of conductor 2 generated by phi
 in Number Field in phi with defining polynomial x^2 - 4*x + 11

Sage Live

E = EllipticCurve(GF(11),[3,3])
E.frobenius_order()

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

Sage

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

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> E = EllipticCurve(GF(Integer(25),'a'),[Integer(0),Integer(0),Integer(0),Integer(0),Integer(1)])
>>> R = E.frobenius_order()
>>> R
Order generated by []
 in Number Field in phi with defining polynomial x + 5
>>> R.degree()
1

Sage Live

# needs sage.rings.finite_rings
E = EllipticCurve(GF(25,'a'),[0,0,0,0,1])
R = E.frobenius_order()
R
R.degree()

frobenius_polynomial()[source]¶

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

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

Python

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(11)),[Integer(3),Integer(3)])
>>> E.frobenius_polynomial()
x^2 - 4*x + 11

Sage Live

E = EllipticCurve(GF(11),[3,3])
E.frobenius_polynomial()

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

Sage

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

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> E = EllipticCurve(GF(Integer(25),'a'),[Integer(0),Integer(0),Integer(0),Integer(0),Integer(1)])
>>> E.frobenius_polynomial().factor()
(x + 5)^2

Sage Live

# needs sage.rings.finite_rings
E = EllipticCurve(GF(25,'a'),[0,0,0,0,1])
E.frobenius_polynomial().factor()

gens()[source]¶

Return points which generate the abelian group of points on this elliptic curve.

The algorithm involves factoring the group order of self, but is otherwise (randomized) polynomial-time.

(The points returned by this function are not guaranteed to be the same each time, although they should remain fixed within a single run of Sage unless abelian_group() is called.)

OUTPUT: a tuple of points on the curve

if the group is trivial: an empty tuple.
if the group is cyclic: a tuple with 1 point, a generator.
if the group is not cyclic: a tuple with 2 points, where the order of the first point equals the exponent of the group.

Warning

In the case of 2 generators \(P\) and \(Q\), it is not guaranteed that the group is the cartesian product of the 2 cyclic groups \(\langle P \rangle\) and \(\langle Q \rangle\). In other words, the order of \(Q\) is not as small as possible. If you really need a basis (rather than just a generating set) of the group, use abelian_group().

EXAMPLES:

Sage

sage: E = EllipticCurve(GF(11),[2,5])
sage: P = E.gens()[0]; P # random
(0 : 7 : 1)
sage: E.cardinality(), P.order()
(10, 10)
sage: E = EllipticCurve(GF(41),[2,5])
sage: E.gens()  # random
((20 : 38 : 1), (25 : 31 : 1))
sage: E.cardinality()
44

Python

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(11)),[Integer(2),Integer(5)])
>>> P = E.gens()[Integer(0)]; P # random
(0 : 7 : 1)
>>> E.cardinality(), P.order()
(10, 10)
>>> E = EllipticCurve(GF(Integer(41)),[Integer(2),Integer(5)])
>>> E.gens()  # random
((20 : 38 : 1), (25 : 31 : 1))
>>> E.cardinality()
44

Sage Live

E = EllipticCurve(GF(11),[2,5])
P = E.gens()[0]; P # random
E.cardinality(), P.order()
E = EllipticCurve(GF(41),[2,5])
E.gens()  # random
E.cardinality()

If the abelian group has been computed, return those generators instead:

Sage

sage: E.abelian_group()
Additive abelian group isomorphic to Z/22 + Z/2
 embedded in Abelian group of points on Elliptic Curve
 defined by y^2 = x^3 + 2*x + 5 over Finite Field of size 41
sage: ab_gens = E.abelian_group().gens()
sage: ab_gens == E.gens()
True
sage: E.gens()[0].order()
22
sage: E.gens()[1].order()
2

Python

>>> from sage.all import *
>>> E.abelian_group()
Additive abelian group isomorphic to Z/22 + Z/2
 embedded in Abelian group of points on Elliptic Curve
 defined by y^2 = x^3 + 2*x + 5 over Finite Field of size 41
>>> ab_gens = E.abelian_group().gens()
>>> ab_gens == E.gens()
True
>>> E.gens()[Integer(0)].order()
22
>>> E.gens()[Integer(1)].order()
2

Sage Live

E.abelian_group()
ab_gens = E.abelian_group().gens()
ab_gens == E.gens()
E.gens()[0].order()
E.gens()[1].order()

Examples with 1 and 0 generators:

Sage

sage: # needs sage.rings.finite_rings
sage: F.<a> = GF(3^6)
sage: E = EllipticCurve([a, a+1])
sage: pts = E.gens()
sage: len(pts)
1
sage: pts[0].order() == E.cardinality()
True

sage: E = EllipticCurve(GF(2), [0,0,1,1,1])
sage: E.gens()
()

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> F = GF(Integer(3)**Integer(6), names=('a',)); (a,) = F._first_ngens(1)
>>> E = EllipticCurve([a, a+Integer(1)])
>>> pts = E.gens()
>>> len(pts)
1
>>> pts[Integer(0)].order() == E.cardinality()
True

>>> E = EllipticCurve(GF(Integer(2)), [Integer(0),Integer(0),Integer(1),Integer(1),Integer(1)])
>>> E.gens()
()

Sage Live

# needs sage.rings.finite_rings
F.<a> = GF(3^6)
E = EllipticCurve([a, a+1])
pts = E.gens()
len(pts)
pts[0].order() == E.cardinality()
E = EllipticCurve(GF(2), [0,0,1,1,1])
E.gens()

This works over larger finite fields where abelian_group() may be too expensive:

Sage

sage: # needs sage.rings.finite_rings
sage: k.<a> = GF(5^60)
sage: E = EllipticCurve([a, a])
sage: len(E.gens())
2
sage: E.cardinality()
867361737988403547206134229616487867594472
sage: a = E.gens()[0].order(); a # random
433680868994201773603067114808243933797236
sage: b = E.gens()[1].order(); b # random
30977204928157269543076222486303138128374
sage: lcm(a,b)
433680868994201773603067114808243933797236

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(5)**Integer(60), names=('a',)); (a,) = k._first_ngens(1)
>>> E = EllipticCurve([a, a])
>>> len(E.gens())
2
>>> E.cardinality()
867361737988403547206134229616487867594472
>>> a = E.gens()[Integer(0)].order(); a # random
433680868994201773603067114808243933797236
>>> b = E.gens()[Integer(1)].order(); b # random
30977204928157269543076222486303138128374
>>> lcm(a,b)
433680868994201773603067114808243933797236

Sage Live

# needs sage.rings.finite_rings
k.<a> = GF(5^60)
E = EllipticCurve([a, a])
len(E.gens())
E.cardinality()
a = E.gens()[0].order(); a # random
b = E.gens()[1].order(); b # random
lcm(a,b)

has_order(value, num_checks=8)[source]¶

Return True if the curve has order value.

INPUT:

value – integer in the Hasse-Weil range for this curve
num_checks– integer (default: \(8\)); the number of times to check whether value times a random point on this curve equals the identity. If value is a prime and the curve is over a field of order at least \(5\), it is sufficient to pass in num_checks=1 - see the examples below.

Note

Since the method is probabilistic, there is a possibility for the method to yield false positives (i.e. returning True even when the result is False). Even worse, it is possible for this to happen even when num_checks is increased arbitrarily. See below for an example and Issue #38617 for an open discussion.

EXAMPLES:

For curves over small finite fields, the order is computed and compared directly:

Sage

sage: E = EllipticCurve(GF(7), [0, 1])
sage: E.order()
12
sage: E.has_order(12, num_checks=0)
True
sage: E.has_order(11, num_checks=0)
False
sage: E.has_order(13, num_checks=0)
False

Python

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(7)), [Integer(0), Integer(1)])
>>> E.order()
12
>>> E.has_order(Integer(12), num_checks=Integer(0))
True
>>> E.has_order(Integer(11), num_checks=Integer(0))
False
>>> E.has_order(Integer(13), num_checks=Integer(0))
False

Sage Live

E = EllipticCurve(GF(7), [0, 1])
E.order()
E.has_order(12, num_checks=0)
E.has_order(11, num_checks=0)
E.has_order(13, num_checks=0)

This tests the method on a random curve:

Sage

sage: # long time (10s)
sage: p = random_prime(2**128, lbound=2**127)
sage: K = GF((p, 2), name="a")
sage: E = EllipticCurve(K, [K.random_element() for _ in range(2)])
sage: N = E.order()
sage: E.has_order(N, num_checks=20)
True
sage: E.has_order(N + 1)
False

Python

>>> from sage.all import *
>>> # long time (10s)
>>> p = random_prime(Integer(2)**Integer(128), lbound=Integer(2)**Integer(127))
>>> K = GF((p, Integer(2)), name="a")
>>> E = EllipticCurve(K, [K.random_element() for _ in range(Integer(2))])
>>> N = E.order()
>>> E.has_order(N, num_checks=Integer(20))
True
>>> E.has_order(N + Integer(1))
False

Sage Live

# long time (10s)
p = random_prime(2**128, lbound=2**127)
K = GF((p, 2), name="a")
E = EllipticCurve(K, [K.random_element() for _ in range(2)])
N = E.order()
E.has_order(N, num_checks=20)
E.has_order(N + 1)

This demonstrates the bug mentioned in the NOTE above. The last return value should be False after Issue #38617 is fixed:

Sage

sage: E = EllipticCurve(GF(5443568676570036275321323), [0, 13])
sage: N = 2333145661241
sage: E.order() == N^2
True
sage: E.has_order(N^2)
True
sage: del E._order
sage: E.has_order(N^2 + N)
True

Python

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(5443568676570036275321323)), [Integer(0), Integer(13)])
>>> N = Integer(2333145661241)
>>> E.order() == N**Integer(2)
True
>>> E.has_order(N**Integer(2))
True
>>> del E._order
>>> E.has_order(N**Integer(2) + N)
True

Sage Live

E = EllipticCurve(GF(5443568676570036275321323), [0, 13])
N = 2333145661241
E.order() == N^2
E.has_order(N^2)
del E._order
E.has_order(N^2 + N)

Due to the nature of the algorithm (testing multiple of points) and the Hasse-Weil bound, we see that for testing prime orders, num_checks=1 is sufficient:

Sage

sage: p = random_prime(1000)
sage: E = EllipticCurve(GF(p), j=randrange(p))
sage: q = random_prime(p + 20, lbound=p - 20)
sage: E.has_order(q, num_checks=20) == E.has_order(q, num_checks=1)
True

Python

>>> from sage.all import *
>>> p = random_prime(Integer(1000))
>>> E = EllipticCurve(GF(p), j=randrange(p))
>>> q = random_prime(p + Integer(20), lbound=p - Integer(20))
>>> E.has_order(q, num_checks=Integer(20)) == E.has_order(q, num_checks=Integer(1))
True

Sage Live

p = random_prime(1000)
E = EllipticCurve(GF(p), j=randrange(p))
q = random_prime(p + 20, lbound=p - 20)
E.has_order(q, num_checks=20) == E.has_order(q, num_checks=1)

AUTHORS:

Mariah Lenox (2011-02-16): Initial implementation

Gareth Ma (2024-01-21): Fix bug for small curves

height_above_floor(ell, e)[source]¶

Return the height of the \(j\)-invariant of this ordinary elliptic curve on its \(\ell\)-volcano.

INPUT:

ell – a prime number
e – nonnegative integer, the \(\ell\)-adic valuation of the conductor the Frobenius order

Note

For an ordinary \(E/\GF{q}\), and a prime \(\ell\), the height \(e\) of the \(\ell\)-volcano containing \(j(E)\) is the \(\ell\)-adic valuation of the conductor of the order generated by the Frobenius \(\pi_E\); the height of \(j(E)\) on its ell-volcano is the \(\ell\)-adic valuation of the conductor of the order \(\text{End}(E)\).

ALGORITHM:

See [RouSuthZur2022].

EXAMPLES:

Sage

sage: F = GF(312401)
sage: E = EllipticCurve(F,(0, 0, 0, 309381, 93465))
sage: D = E.frobenius_discriminant(); D
-687104
sage: D.factor()
-1 * 2^10 * 11 * 61
sage: E.height_above_floor(2,8)
5

Python

>>> from sage.all import *
>>> F = GF(Integer(312401))
>>> E = EllipticCurve(F,(Integer(0), Integer(0), Integer(0), Integer(309381), Integer(93465)))
>>> D = E.frobenius_discriminant(); D
-687104
>>> D.factor()
-1 * 2^10 * 11 * 61
>>> E.height_above_floor(Integer(2),Integer(8))
5

Sage Live

F = GF(312401)
E = EllipticCurve(F,(0, 0, 0, 309381, 93465))
D = E.frobenius_discriminant(); D
D.factor()
E.height_above_floor(2,8)

is_isogenous(other, field=None, proof=True)[source]¶

Return whether or not self is isogenous to other.

INPUT:

other – another elliptic curve
field – (default: None) a field containing the base fields of the two elliptic curves into which the two curves may be extended to test if they are isogenous over this field. By default is_isogenous will not try to find this field unless one of the curves can be extended into the base field of the other, in which case it will test over the larger base field.
proof – boolean (default: True); this parameter is here only to be consistent with versions for other types of elliptic curves

OUTPUT:

boolean; True if there is an isogeny from curve self to curve other defined over field

EXAMPLES:

Sage

sage: # needs sage.rings.finite_rings
sage: E1 = EllipticCurve(GF(11^2,'a'),[2,7]); E1
Elliptic Curve defined by y^2 = x^3 + 2*x + 7 over Finite Field in a of size 11^2
sage: E1.is_isogenous(5)
Traceback (most recent call last):
...
ValueError: Second argument is not an Elliptic Curve.
sage: E1.is_isogenous(E1)
True

sage: # needs sage.rings.finite_rings
sage: E2 = EllipticCurve(GF(7^3,'b'),[3,1]); E2
Elliptic Curve defined by y^2 = x^3 + 3*x + 1 over Finite Field in b of size 7^3
sage: E1.is_isogenous(E2)
Traceback (most recent call last):
...
ValueError: The base fields must have the same characteristic.

sage: # needs sage.rings.finite_rings
sage: E3 = EllipticCurve(GF(11^2,'c'),[4,3]); E3
Elliptic Curve defined by y^2 = x^3 + 4*x + 3 over Finite Field in c of size 11^2
sage: E1.is_isogenous(E3)
False

sage: # needs sage.rings.finite_rings
sage: E4 = EllipticCurve(GF(11^6,'d'),[6,5]); E4
Elliptic Curve defined by y^2 = x^3 + 6*x + 5 over Finite Field in d of size 11^6
sage: E1.is_isogenous(E4)
True

sage: # needs sage.rings.finite_rings
sage: E5 = EllipticCurve(GF(11^7,'e'),[4,2]); E5
Elliptic Curve defined by y^2 = x^3 + 4*x + 2 over Finite Field in e of size 11^7
sage: E1.is_isogenous(E5)
Traceback (most recent call last):
...
ValueError: Curves have different base fields: use the field parameter.

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> E1 = EllipticCurve(GF(Integer(11)**Integer(2),'a'),[Integer(2),Integer(7)]); E1
Elliptic Curve defined by y^2 = x^3 + 2*x + 7 over Finite Field in a of size 11^2
>>> E1.is_isogenous(Integer(5))
Traceback (most recent call last):
...
ValueError: Second argument is not an Elliptic Curve.
>>> E1.is_isogenous(E1)
True

>>> # needs sage.rings.finite_rings
>>> E2 = EllipticCurve(GF(Integer(7)**Integer(3),'b'),[Integer(3),Integer(1)]); E2
Elliptic Curve defined by y^2 = x^3 + 3*x + 1 over Finite Field in b of size 7^3
>>> E1.is_isogenous(E2)
Traceback (most recent call last):
...
ValueError: The base fields must have the same characteristic.

>>> # needs sage.rings.finite_rings
>>> E3 = EllipticCurve(GF(Integer(11)**Integer(2),'c'),[Integer(4),Integer(3)]); E3
Elliptic Curve defined by y^2 = x^3 + 4*x + 3 over Finite Field in c of size 11^2
>>> E1.is_isogenous(E3)
False

>>> # needs sage.rings.finite_rings
>>> E4 = EllipticCurve(GF(Integer(11)**Integer(6),'d'),[Integer(6),Integer(5)]); E4
Elliptic Curve defined by y^2 = x^3 + 6*x + 5 over Finite Field in d of size 11^6
>>> E1.is_isogenous(E4)
True

>>> # needs sage.rings.finite_rings
>>> E5 = EllipticCurve(GF(Integer(11)**Integer(7),'e'),[Integer(4),Integer(2)]); E5
Elliptic Curve defined by y^2 = x^3 + 4*x + 2 over Finite Field in e of size 11^7
>>> E1.is_isogenous(E5)
Traceback (most recent call last):
...
ValueError: Curves have different base fields: use the field parameter.

Sage Live

# needs sage.rings.finite_rings
E1 = EllipticCurve(GF(11^2,'a'),[2,7]); E1
E1.is_isogenous(5)
E1.is_isogenous(E1)
# needs sage.rings.finite_rings
E2 = EllipticCurve(GF(7^3,'b'),[3,1]); E2
E1.is_isogenous(E2)
# needs sage.rings.finite_rings
E3 = EllipticCurve(GF(11^2,'c'),[4,3]); E3
E1.is_isogenous(E3)
# needs sage.rings.finite_rings
E4 = EllipticCurve(GF(11^6,'d'),[6,5]); E4
E1.is_isogenous(E4)
# needs sage.rings.finite_rings
E5 = EllipticCurve(GF(11^7,'e'),[4,2]); E5
E1.is_isogenous(E5)

When the field is given:

Sage

sage: # needs sage.rings.finite_rings
sage: E1 = EllipticCurve(GF(13^2,'a'),[2,7]); E1
Elliptic Curve defined by y^2 = x^3 + 2*x + 7 over Finite Field in a of size 13^2
sage: E1.is_isogenous(5,GF(13^6,'f'))
Traceback (most recent call last):
...
ValueError: Second argument is not an Elliptic Curve.
sage: E6 = EllipticCurve(GF(11^3,'g'),[9,3]); E6
Elliptic Curve defined by y^2 = x^3 + 9*x + 3 over Finite Field in g of size 11^3
sage: E1.is_isogenous(E6,QQ)
Traceback (most recent call last):
...
ValueError: The base fields must have the same characteristic.
sage: E7 = EllipticCurve(GF(13^5,'h'),[2,9]); E7
Elliptic Curve defined by y^2 = x^3 + 2*x + 9 over Finite Field in h of size 13^5
sage: E1.is_isogenous(E7,GF(13^4,'i'))
Traceback (most recent call last):
...
ValueError: Field must be an extension of the base fields of both curves
sage: E1.is_isogenous(E7,GF(13^10,'j'))
False
sage: E1.is_isogenous(E7,GF(13^30,'j'))
False

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> E1 = EllipticCurve(GF(Integer(13)**Integer(2),'a'),[Integer(2),Integer(7)]); E1
Elliptic Curve defined by y^2 = x^3 + 2*x + 7 over Finite Field in a of size 13^2
>>> E1.is_isogenous(Integer(5),GF(Integer(13)**Integer(6),'f'))
Traceback (most recent call last):
...
ValueError: Second argument is not an Elliptic Curve.
>>> E6 = EllipticCurve(GF(Integer(11)**Integer(3),'g'),[Integer(9),Integer(3)]); E6
Elliptic Curve defined by y^2 = x^3 + 9*x + 3 over Finite Field in g of size 11^3
>>> E1.is_isogenous(E6,QQ)
Traceback (most recent call last):
...
ValueError: The base fields must have the same characteristic.
>>> E7 = EllipticCurve(GF(Integer(13)**Integer(5),'h'),[Integer(2),Integer(9)]); E7
Elliptic Curve defined by y^2 = x^3 + 2*x + 9 over Finite Field in h of size 13^5
>>> E1.is_isogenous(E7,GF(Integer(13)**Integer(4),'i'))
Traceback (most recent call last):
...
ValueError: Field must be an extension of the base fields of both curves
>>> E1.is_isogenous(E7,GF(Integer(13)**Integer(10),'j'))
False
>>> E1.is_isogenous(E7,GF(Integer(13)**Integer(30),'j'))
False

Sage Live

# needs sage.rings.finite_rings
E1 = EllipticCurve(GF(13^2,'a'),[2,7]); E1
E1.is_isogenous(5,GF(13^6,'f'))
E6 = EllipticCurve(GF(11^3,'g'),[9,3]); E6
E1.is_isogenous(E6,QQ)
E7 = EllipticCurve(GF(13^5,'h'),[2,9]); E7
E1.is_isogenous(E7,GF(13^4,'i'))
E1.is_isogenous(E7,GF(13^10,'j'))
E1.is_isogenous(E7,GF(13^30,'j'))

is_ordinary(proof=True)[source]¶

Return True if this elliptic curve is ordinary, else False.

INPUT:

proof– boolean (default: True); if True, returns a proved result. If False, then a return value of True is certain but a return value of False may be based on a probabilistic test. See the documentation of the function is_j_supersingular() for more details.

EXAMPLES:

Sage

sage: F = GF(101)
sage: EllipticCurve(j=F(0)).is_ordinary()
False
sage: EllipticCurve(j=F(1728)).is_ordinary()
True
sage: EllipticCurve(j=F(66)).is_ordinary()
False
sage: EllipticCurve(j=F(99)).is_ordinary()
True

Python

>>> from sage.all import *
>>> F = GF(Integer(101))
>>> EllipticCurve(j=F(Integer(0))).is_ordinary()
False
>>> EllipticCurve(j=F(Integer(1728))).is_ordinary()
True
>>> EllipticCurve(j=F(Integer(66))).is_ordinary()
False
>>> EllipticCurve(j=F(Integer(99))).is_ordinary()
True

Sage Live

F = GF(101)
EllipticCurve(j=F(0)).is_ordinary()
EllipticCurve(j=F(1728)).is_ordinary()
EllipticCurve(j=F(66)).is_ordinary()
EllipticCurve(j=F(99)).is_ordinary()

is_supersingular(proof=True)[source]¶

Return True if this elliptic curve is supersingular, else False.

INPUT:

proof– boolean (default: True); if True, returns a proved result. If False, then a return value of False is certain but a return value of True may be based on a probabilistic test. See the documentation of the function is_j_supersingular() for more details.

EXAMPLES:

Sage

sage: F = GF(101)
sage: EllipticCurve(j=F(0)).is_supersingular()
True
sage: EllipticCurve(j=F(1728)).is_supersingular()
False
sage: EllipticCurve(j=F(66)).is_supersingular()
True
sage: EllipticCurve(j=F(99)).is_supersingular()
False

Python

>>> from sage.all import *
>>> F = GF(Integer(101))
>>> EllipticCurve(j=F(Integer(0))).is_supersingular()
True
>>> EllipticCurve(j=F(Integer(1728))).is_supersingular()
False
>>> EllipticCurve(j=F(Integer(66))).is_supersingular()
True
>>> EllipticCurve(j=F(Integer(99))).is_supersingular()
False

Sage Live

F = GF(101)
EllipticCurve(j=F(0)).is_supersingular()
EllipticCurve(j=F(1728)).is_supersingular()
EllipticCurve(j=F(66)).is_supersingular()
EllipticCurve(j=F(99)).is_supersingular()

multiplication_by_p_isogeny()[source]¶

Return the multiplication-by-\(p\) isogeny.

EXAMPLES:

Sage

sage: p = 23
sage: K.<a> = GF(p^3)
sage: E = EllipticCurve(j=K.random_element())
sage: phi = E.multiplication_by_p_isogeny()
sage: assert phi.degree() == p**2
sage: P = E.random_element()
sage: assert phi(P) == P * p

Python

>>> from sage.all import *
>>> p = Integer(23)
>>> K = GF(p**Integer(3), names=('a',)); (a,) = K._first_ngens(1)
>>> E = EllipticCurve(j=K.random_element())
>>> phi = E.multiplication_by_p_isogeny()
>>> assert phi.degree() == p**Integer(2)
>>> P = E.random_element()
>>> assert phi(P) == P * p

Sage Live

p = 23
K.<a> = GF(p^3)
E = EllipticCurve(j=K.random_element())
phi = E.multiplication_by_p_isogeny()
assert phi.degree() == p**2
P = E.random_element()
assert phi(P) == P * p

order(algorithm=None, extension_degree=1)[source]¶

Return the number of points on this elliptic curve.

INPUT:

algorithm – (optional) string:
- 'pari' – use the PARI C-library function ellcard
- 'bsgs' – use the baby-step giant-step method as
  implemented in Sage, with the Cremona-Sutherland version of Mestre’s trick
- 'exhaustive' – naive point counting
- 'subfield' – reduce to a smaller field, provided that the j-invariant lies in a subfield
- 'all' – compute cardinality with both 'pari' and 'bsgs'; return result if they agree or raise a AssertionError if they do not
extension_degree – integer \(d\) (default: 1); if the base field is \(\GF{q}\), return the cardinality of self over the extension \(\GF{q^d}\) of degree \(d\)

OUTPUT:

The order of the group of rational points of self over its base field, or over an extension field of degree \(d\) as above. The result is cached.

EXAMPLES:

Sage

sage: # needs sage.rings.finite_rings
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

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> EllipticCurve(GF(Integer(4), 'a'), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]).cardinality()
8
>>> k = GF(Integer(3)**Integer(3), names=('a',)); (a,) = k._first_ngens(1)
>>> l = [a**Integer(2) + Integer(1), Integer(2)*a**Integer(2) + Integer(2)*a + Integer(1), a**Integer(2) + a + Integer(1), Integer(2), Integer(2)*a]
>>> EllipticCurve(k,l).cardinality()
29

Sage Live

# needs sage.rings.finite_rings
EllipticCurve(GF(4, 'a'), [1,2,3,4,5]).cardinality()
k.<a> = GF(3^3)
l = [a^2 + 1, 2*a^2 + 2*a + 1, a^2 + a + 1, 2, 2*a]
EllipticCurve(k,l).cardinality()

Sage

sage: # needs sage.rings.finite_rings
sage: l = [1, 1, 0, 2, 0]
sage: EllipticCurve(k, l).cardinality()
38

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> l = [Integer(1), Integer(1), Integer(0), Integer(2), Integer(0)]
>>> EllipticCurve(k, l).cardinality()
38

Sage Live

# needs sage.rings.finite_rings
l = [1, 1, 0, 2, 0]
EllipticCurve(k, l).cardinality()

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> l = [Integer(1), Integer(1), Integer(0), Integer(2), Integer(0)]
>>> EllipticCurve(k, l).cardinality()
38

Sage Live

# needs sage.rings.finite_rings
l = [1, 1, 0, 2, 0]
EllipticCurve(k, l).cardinality()

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

Sage

sage: # needs sage.rings.finite_rings
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'

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> EllipticCurve(GF(Integer(3)**Integer(100), 'a'), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]).cardinality()
515377520732011331036459693969645888996929981504
>>> magma.eval("Order(EllipticCurve([GF(3^100)|1,2,3,4,5]))")    # optional - magma
'515377520732011331036459693969645888996929981504'

Sage Live

# needs sage.rings.finite_rings
EllipticCurve(GF(3^100, 'a'), [1,2,3,4,5]).cardinality()
magma.eval("Order(EllipticCurve([GF(3^100)|1,2,3,4,5]))")    # optional - magma

Sage

sage: EllipticCurve(GF(10007), [1,2,3,4,5]).cardinality()
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()
100000000011093199520

Python

>>> from sage.all import *
>>> EllipticCurve(GF(Integer(10007)), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]).cardinality()
10076
>>> EllipticCurve(GF(Integer(10007)), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]).cardinality(algorithm='pari')
10076
>>> EllipticCurve(GF(next_prime(Integer(10)**Integer(20))), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]).cardinality()
100000000011093199520

Sage Live

EllipticCurve(GF(10007), [1,2,3,4,5]).cardinality()
EllipticCurve(GF(10007), [1,2,3,4,5]).cardinality(algorithm='pari')
EllipticCurve(GF(next_prime(10**20)), [1,2,3,4,5]).cardinality()

Python

>>> from sage.all import *
>>> EllipticCurve(GF(Integer(10007)), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]).cardinality()
10076
>>> EllipticCurve(GF(Integer(10007)), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]).cardinality(algorithm='pari')
10076
>>> EllipticCurve(GF(next_prime(Integer(10)**Integer(20))), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]).cardinality()
100000000011093199520

Sage Live

EllipticCurve(GF(10007), [1,2,3,4,5]).cardinality()
EllipticCurve(GF(10007), [1,2,3,4,5]).cardinality(algorithm='pari')
EllipticCurve(GF(next_prime(10**20)), [1,2,3,4,5]).cardinality()

The cardinality is cached:

Sage

sage: # needs sage.rings.finite_rings
sage: E = EllipticCurve(GF(3^100, 'a'), [1,2,3,4,5])
sage: E.cardinality() is E.cardinality()
True

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> E = EllipticCurve(GF(Integer(3)**Integer(100), 'a'), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)])
>>> E.cardinality() is E.cardinality()
True

Sage Live

# needs sage.rings.finite_rings
E = EllipticCurve(GF(3^100, 'a'), [1,2,3,4,5])
E.cardinality() is E.cardinality()

The following is very fast since the curve is actually defined over the prime field:

Sage

sage: # needs sage.rings.finite_rings
sage: k.<a> = GF(11^100)
sage: E1 = EllipticCurve(k, [3,3])
sage: N1 = E1.cardinality(algorithm='subfield'); N1
137806123398222701841183371720896367762643312000384671846835266941791510341065565176497846502742959856128
sage: E1.cardinality_pari() == N1
True
sage: E2 = E1.quadratic_twist()
sage: N2 = E2.cardinality(algorithm='subfield'); N2
137806123398222701841183371720896367762643312000384656816094284101308193849980588362304472492174093035876
sage: E2.cardinality_pari() == N2
True
sage: N1 + N2 == 2*(k.cardinality() + 1)
True

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(11)**Integer(100), names=('a',)); (a,) = k._first_ngens(1)
>>> E1 = EllipticCurve(k, [Integer(3),Integer(3)])
>>> N1 = E1.cardinality(algorithm='subfield'); N1
137806123398222701841183371720896367762643312000384671846835266941791510341065565176497846502742959856128
>>> E1.cardinality_pari() == N1
True
>>> E2 = E1.quadratic_twist()
>>> N2 = E2.cardinality(algorithm='subfield'); N2
137806123398222701841183371720896367762643312000384656816094284101308193849980588362304472492174093035876
>>> E2.cardinality_pari() == N2
True
>>> N1 + N2 == Integer(2)*(k.cardinality() + Integer(1))
True

Sage Live

# needs sage.rings.finite_rings
k.<a> = GF(11^100)
E1 = EllipticCurve(k, [3,3])
N1 = E1.cardinality(algorithm='subfield'); N1
E1.cardinality_pari() == N1
E2 = E1.quadratic_twist()
N2 = E2.cardinality(algorithm='subfield'); N2
E2.cardinality_pari() == N2
N1 + N2 == 2*(k.cardinality() + 1)

We can count points over curves defined as a reduction:

Sage

sage: # needs sage.rings.number_field
sage: x = polygen(QQ)
sage: K.<w> = NumberField(x^2 + x + 1)
sage: EK = EllipticCurve(K, [0, 0, w, 2, 1])
sage: E = EK.base_extend(K.residue_field(2))
sage: E
Elliptic Curve defined by y^2 + wbar*y = x^3 + 1
 over Residue field in wbar of Fractional ideal (2)
sage: E.cardinality()
7
sage: E = EK.base_extend(K.residue_field(w - 1))
sage: E.abelian_group()
Trivial group embedded in Abelian group of points on Elliptic Curve defined
 by y^2 + y = x^3 + 2*x + 1 over Residue field of Fractional ideal (w - 1)

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> x = polygen(QQ)
>>> K = NumberField(x**Integer(2) + x + Integer(1), names=('w',)); (w,) = K._first_ngens(1)
>>> EK = EllipticCurve(K, [Integer(0), Integer(0), w, Integer(2), Integer(1)])
>>> E = EK.base_extend(K.residue_field(Integer(2)))
>>> E
Elliptic Curve defined by y^2 + wbar*y = x^3 + 1
 over Residue field in wbar of Fractional ideal (2)
>>> E.cardinality()
7
>>> E = EK.base_extend(K.residue_field(w - Integer(1)))
>>> E.abelian_group()
Trivial group embedded in Abelian group of points on Elliptic Curve defined
 by y^2 + y = x^3 + 2*x + 1 over Residue field of Fractional ideal (w - 1)

Sage Live

# needs sage.rings.number_field
x = polygen(QQ)
K.<w> = NumberField(x^2 + x + 1)
EK = EllipticCurve(K, [0, 0, w, 2, 1])
E = EK.base_extend(K.residue_field(2))
E
E.cardinality()
E = EK.base_extend(K.residue_field(w - 1))
E.abelian_group()

Sage

sage: R.<x> = GF(17)[]
sage: pol = R.irreducible_element(5)
sage: k.<a> = R.residue_field(pol)
sage: E = EllipticCurve(R, [1, x]).base_extend(k)
sage: E
Elliptic Curve defined by y^2 = x^3 + x + a
 over Residue field in a of Principal ideal (x^5 + x + 14)
  of Univariate Polynomial Ring in x over Finite Field of size 17
sage: E.cardinality()
1421004

Python

>>> from sage.all import *
>>> R = GF(Integer(17))['x']; (x,) = R._first_ngens(1)
>>> pol = R.irreducible_element(Integer(5))
>>> k = R.residue_field(pol, names=('a',)); (a,) = k._first_ngens(1)
>>> E = EllipticCurve(R, [Integer(1), x]).base_extend(k)
>>> E
Elliptic Curve defined by y^2 = x^3 + x + a
 over Residue field in a of Principal ideal (x^5 + x + 14)
  of Univariate Polynomial Ring in x over Finite Field of size 17
>>> E.cardinality()
1421004

Sage Live

R.<x> = GF(17)[]
pol = R.irreducible_element(5)
k.<a> = R.residue_field(pol)
E = EllipticCurve(R, [1, x]).base_extend(k)
E
E.cardinality()

Python

>>> from sage.all import *
>>> R = GF(Integer(17))['x']; (x,) = R._first_ngens(1)
>>> pol = R.irreducible_element(Integer(5))
>>> k = R.residue_field(pol, names=('a',)); (a,) = k._first_ngens(1)
>>> E = EllipticCurve(R, [Integer(1), x]).base_extend(k)
>>> E
Elliptic Curve defined by y^2 = x^3 + x + a
 over Residue field in a of Principal ideal (x^5 + x + 14)
  of Univariate Polynomial Ring in x over Finite Field of size 17
>>> E.cardinality()
1421004

Sage Live

R.<x> = GF(17)[]
pol = R.irreducible_element(5)
k.<a> = R.residue_field(pol)
E = EllipticCurve(R, [1, x]).base_extend(k)
E
E.cardinality()

plot(*args, **kwds)[source]¶

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

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

Python

>>> from sage.all import *
>>> E = EllipticCurve(FiniteField(Integer(17)), [Integer(0),Integer(1)])
>>> P = plot(E, rgbcolor=(Integer(0),Integer(0),Integer(1)))                                         # needs sage.plot

Sage Live

E = EllipticCurve(FiniteField(17), [0,1])
P = plot(E, rgbcolor=(0,0,1))                                         # needs sage.plot

points()[source]¶

Return all rational points on this elliptic curve. The list of points is cached so subsequent calls are free.

EXAMPLES:

Sage

sage: p = 5
sage: F = GF(p)
sage: E = EllipticCurve(F, [1, 3])
sage: len(E.points())
4
sage: E.order()
4
sage: E.points()
[(0 : 1 : 0), (1 : 0 : 1), (4 : 1 : 1), (4 : 4 : 1)]

Python

>>> from sage.all import *
>>> p = Integer(5)
>>> F = GF(p)
>>> E = EllipticCurve(F, [Integer(1), Integer(3)])
>>> len(E.points())
4
>>> E.order()
4
>>> E.points()
[(0 : 1 : 0), (1 : 0 : 1), (4 : 1 : 1), (4 : 4 : 1)]

Sage Live

p = 5
F = GF(p)
E = EllipticCurve(F, [1, 3])
len(E.points())
E.order()
E.points()

Sage

sage: K = GF((p, 2), 'a')
sage: E = E.change_ring(K)
sage: len(E.points())
32
sage: E.order()
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)]

Python

>>> from sage.all import *
>>> K = GF((p, Integer(2)), 'a')
>>> E = E.change_ring(K)
>>> len(E.points())
32
>>> E.order()
32
>>> 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)]

Sage Live

K = GF((p, 2), 'a')
E = E.change_ring(K)
len(E.points())
E.order()
w = E.points(); w

Python

>>> from sage.all import *
>>> K = GF((p, Integer(2)), 'a')
>>> E = E.change_ring(K)
>>> len(E.points())
32
>>> E.order()
32
>>> 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)]

Sage Live

K = GF((p, 2), 'a')
E = E.change_ring(K)
len(E.points())
E.order()
w = E.points(); w

Note that the returned list is an immutable sorted Sequence:

Sage

sage: w[0] = 9
Traceback (most recent call last):
...
ValueError: object is immutable; please change a copy instead.

Python

>>> from sage.all import *
>>> w[Integer(0)] = Integer(9)
Traceback (most recent call last):
...
ValueError: object is immutable; please change a copy instead.

Sage Live

w[0] = 9

random_element()[source]¶

Return a random point on this elliptic curve, uniformly chosen among all rational points.

ALGORITHM:

Choose the point at infinity with probability \(1/(2q + 1)\). Otherwise, take a random element from the field as x-coordinate and compute the possible y-coordinates. Return the i-th possible y-coordinate, where i is randomly chosen to be 0 or 1. If the i-th y-coordinate does not exist (either there is no point with the given x-coordinate or we hit a 2-torsion point with i == 1), try again.

This gives a uniform distribution because you can imagine \(2q + 1\) buckets, one for the point at infinity and 2 for each element of the field (representing the x-coordinates). This gives a 1-to-1 map of elliptic curve points into buckets. At every iteration, we simply choose a random bucket until we find a bucket containing a point.

AUTHORS:

Jeroen Demeyer (2014-09-09): choose points uniformly random, see Issue #16951.

EXAMPLES:

Sage

sage: k = GF(next_prime(7^5))
sage: E = EllipticCurve(k,[2,4])
sage: P = E.random_element(); P  # random
(16740 : 12486 : 1)
sage: type(P)
<class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
sage: P in E
True

Python

>>> from sage.all import *
>>> k = GF(next_prime(Integer(7)**Integer(5)))
>>> E = EllipticCurve(k,[Integer(2),Integer(4)])
>>> P = E.random_element(); P  # random
(16740 : 12486 : 1)
>>> type(P)
<class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
>>> P in E
True

Sage Live

k = GF(next_prime(7^5))
E = EllipticCurve(k,[2,4])
P = E.random_element(); P  # random
type(P)
P in E

Sage

sage: # needs sage.rings.finite_rings
sage: k.<a> = GF(7^5)
sage: E = EllipticCurve(k,[2,4])
sage: P = E.random_element(); P  # random
(5*a^4 + 3*a^3 + 2*a^2 + a + 4 : 2*a^4 + 3*a^3 + 4*a^2 + a + 5 : 1)
sage: type(P)
<class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
sage: P in E
True

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(7)**Integer(5), names=('a',)); (a,) = k._first_ngens(1)
>>> E = EllipticCurve(k,[Integer(2),Integer(4)])
>>> P = E.random_element(); P  # random
(5*a^4 + 3*a^3 + 2*a^2 + a + 4 : 2*a^4 + 3*a^3 + 4*a^2 + a + 5 : 1)
>>> type(P)
<class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
>>> P in E
True

Sage Live

# needs sage.rings.finite_rings
k.<a> = GF(7^5)
E = EllipticCurve(k,[2,4])
P = E.random_element(); P  # random
type(P)
P in E

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(7)**Integer(5), names=('a',)); (a,) = k._first_ngens(1)
>>> E = EllipticCurve(k,[Integer(2),Integer(4)])
>>> P = E.random_element(); P  # random
(5*a^4 + 3*a^3 + 2*a^2 + a + 4 : 2*a^4 + 3*a^3 + 4*a^2 + a + 5 : 1)
>>> type(P)
<class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
>>> P in E
True

Sage Live

# needs sage.rings.finite_rings
k.<a> = GF(7^5)
E = EllipticCurve(k,[2,4])
P = E.random_element(); P  # random
type(P)
P in E

Sage

sage: # needs sage.rings.finite_rings
sage: k.<a> = GF(2^5)
sage: E = EllipticCurve(k,[a^2,a,1,a+1,1])
sage: P = E.random_element(); P  # random
(a^4 + a : a^4 + a^3 + a^2 : 1)
sage: type(P)
<class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
sage: P in E
True

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(2)**Integer(5), names=('a',)); (a,) = k._first_ngens(1)
>>> E = EllipticCurve(k,[a**Integer(2),a,Integer(1),a+Integer(1),Integer(1)])
>>> P = E.random_element(); P  # random
(a^4 + a : a^4 + a^3 + a^2 : 1)
>>> type(P)
<class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
>>> P in E
True

Sage Live

# needs sage.rings.finite_rings
k.<a> = GF(2^5)
E = EllipticCurve(k,[a^2,a,1,a+1,1])
P = E.random_element(); P  # random
type(P)
P in E

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(2)**Integer(5), names=('a',)); (a,) = k._first_ngens(1)
>>> E = EllipticCurve(k,[a**Integer(2),a,Integer(1),a+Integer(1),Integer(1)])
>>> P = E.random_element(); P  # random
(a^4 + a : a^4 + a^3 + a^2 : 1)
>>> type(P)
<class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
>>> P in E
True

Sage Live

# needs sage.rings.finite_rings
k.<a> = GF(2^5)
E = EllipticCurve(k,[a^2,a,1,a+1,1])
P = E.random_element(); P  # random
type(P)
P in E

Ensure that the entire point set is reachable:

Sage

sage: E = EllipticCurve(GF(11), [2,1])
sage: S = set()
sage: while len(S) < E.cardinality():
....:     S.add(E.random_element())

Python

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(11)), [Integer(2),Integer(1)])
>>> S = set()
>>> while len(S) < E.cardinality():
...     S.add(E.random_element())

Sage Live

E = EllipticCurve(GF(11), [2,1])
S = set()
while len(S) < E.cardinality():
    S.add(E.random_element())

random_point()[source]¶

Return a random point on this elliptic curve, uniformly chosen among all rational points.

ALGORITHM:

AUTHORS:

Jeroen Demeyer (2014-09-09): choose points uniformly random, see Issue #16951.

EXAMPLES:

Sage

sage: k = GF(next_prime(7^5))
sage: E = EllipticCurve(k,[2,4])
sage: P = E.random_element(); P  # random
(16740 : 12486 : 1)
sage: type(P)
<class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
sage: P in E
True

Python

>>> from sage.all import *
>>> k = GF(next_prime(Integer(7)**Integer(5)))
>>> E = EllipticCurve(k,[Integer(2),Integer(4)])
>>> P = E.random_element(); P  # random
(16740 : 12486 : 1)
>>> type(P)
<class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
>>> P in E
True

Sage Live

k = GF(next_prime(7^5))
E = EllipticCurve(k,[2,4])
P = E.random_element(); P  # random
type(P)
P in E

Sage

sage: # needs sage.rings.finite_rings
sage: k.<a> = GF(7^5)
sage: E = EllipticCurve(k,[2,4])
sage: P = E.random_element(); P  # random
(5*a^4 + 3*a^3 + 2*a^2 + a + 4 : 2*a^4 + 3*a^3 + 4*a^2 + a + 5 : 1)
sage: type(P)
<class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
sage: P in E
True

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(7)**Integer(5), names=('a',)); (a,) = k._first_ngens(1)
>>> E = EllipticCurve(k,[Integer(2),Integer(4)])
>>> P = E.random_element(); P  # random
(5*a^4 + 3*a^3 + 2*a^2 + a + 4 : 2*a^4 + 3*a^3 + 4*a^2 + a + 5 : 1)
>>> type(P)
<class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
>>> P in E
True

Sage Live

# needs sage.rings.finite_rings
k.<a> = GF(7^5)
E = EllipticCurve(k,[2,4])
P = E.random_element(); P  # random
type(P)
P in E

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(7)**Integer(5), names=('a',)); (a,) = k._first_ngens(1)
>>> E = EllipticCurve(k,[Integer(2),Integer(4)])
>>> P = E.random_element(); P  # random
(5*a^4 + 3*a^3 + 2*a^2 + a + 4 : 2*a^4 + 3*a^3 + 4*a^2 + a + 5 : 1)
>>> type(P)
<class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
>>> P in E
True

Sage Live

# needs sage.rings.finite_rings
k.<a> = GF(7^5)
E = EllipticCurve(k,[2,4])
P = E.random_element(); P  # random
type(P)
P in E

Sage

sage: # needs sage.rings.finite_rings
sage: k.<a> = GF(2^5)
sage: E = EllipticCurve(k,[a^2,a,1,a+1,1])
sage: P = E.random_element(); P  # random
(a^4 + a : a^4 + a^3 + a^2 : 1)
sage: type(P)
<class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
sage: P in E
True

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(2)**Integer(5), names=('a',)); (a,) = k._first_ngens(1)
>>> E = EllipticCurve(k,[a**Integer(2),a,Integer(1),a+Integer(1),Integer(1)])
>>> P = E.random_element(); P  # random
(a^4 + a : a^4 + a^3 + a^2 : 1)
>>> type(P)
<class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
>>> P in E
True

Sage Live

# needs sage.rings.finite_rings
k.<a> = GF(2^5)
E = EllipticCurve(k,[a^2,a,1,a+1,1])
P = E.random_element(); P  # random
type(P)
P in E

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(2)**Integer(5), names=('a',)); (a,) = k._first_ngens(1)
>>> E = EllipticCurve(k,[a**Integer(2),a,Integer(1),a+Integer(1),Integer(1)])
>>> P = E.random_element(); P  # random
(a^4 + a : a^4 + a^3 + a^2 : 1)
>>> type(P)
<class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
>>> P in E
True

Sage Live

# needs sage.rings.finite_rings
k.<a> = GF(2^5)
E = EllipticCurve(k,[a^2,a,1,a+1,1])
P = E.random_element(); P  # random
type(P)
P in E

Ensure that the entire point set is reachable:

Sage

sage: E = EllipticCurve(GF(11), [2,1])
sage: S = set()
sage: while len(S) < E.cardinality():
....:     S.add(E.random_element())

Python

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(11)), [Integer(2),Integer(1)])
>>> S = set()
>>> while len(S) < E.cardinality():
...     S.add(E.random_element())

Sage Live

E = EllipticCurve(GF(11), [2,1])
S = set()
while len(S) < E.cardinality():
    S.add(E.random_element())

rational_points()[source]¶

Return all rational points on this elliptic curve. The list of points is cached so subsequent calls are free.

EXAMPLES:

Sage

sage: p = 5
sage: F = GF(p)
sage: E = EllipticCurve(F, [1, 3])
sage: len(E.points())
4
sage: E.order()
4
sage: E.points()
[(0 : 1 : 0), (1 : 0 : 1), (4 : 1 : 1), (4 : 4 : 1)]

Python

>>> from sage.all import *
>>> p = Integer(5)
>>> F = GF(p)
>>> E = EllipticCurve(F, [Integer(1), Integer(3)])
>>> len(E.points())
4
>>> E.order()
4
>>> E.points()
[(0 : 1 : 0), (1 : 0 : 1), (4 : 1 : 1), (4 : 4 : 1)]

Sage Live

p = 5
F = GF(p)
E = EllipticCurve(F, [1, 3])
len(E.points())
E.order()
E.points()

Sage

sage: K = GF((p, 2), 'a')
sage: E = E.change_ring(K)
sage: len(E.points())
32
sage: E.order()
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)]

Python

>>> from sage.all import *
>>> K = GF((p, Integer(2)), 'a')
>>> E = E.change_ring(K)
>>> len(E.points())
32
>>> E.order()
32
>>> 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)]

Sage Live

K = GF((p, 2), 'a')
E = E.change_ring(K)
len(E.points())
E.order()
w = E.points(); w

Python

>>> from sage.all import *
>>> K = GF((p, Integer(2)), 'a')
>>> E = E.change_ring(K)
>>> len(E.points())
32
>>> E.order()
32
>>> 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)]

Sage Live

K = GF((p, 2), 'a')
E = E.change_ring(K)
len(E.points())
E.order()
w = E.points(); w

Note that the returned list is an immutable sorted Sequence:

Sage

sage: w[0] = 9
Traceback (most recent call last):
...
ValueError: object is immutable; please change a copy instead.

Python

>>> from sage.all import *
>>> w[Integer(0)] = Integer(9)
Traceback (most recent call last):
...
ValueError: object is immutable; please change a copy instead.

Sage Live

w[0] = 9

set_order(value, check, num_checks)[source]¶

Set the value of self._order to value.

Use this when you know a priori the order of the curve to avoid a potentially expensive order calculation.

INPUT:

value – integer in the Hasse-Weil range for this curve
check– boolean (default: True); whether or not to run sanity checks on the input
num_checks– integer (default: \(8\)); if check is True, the number of times to check whether value times a random point on this curve equals the identity

OUTPUT: none

EXAMPLES:

This example illustrates basic usage:

Sage

sage: E = EllipticCurve(GF(7), [0, 1]) # This curve has order 12
sage: E.set_order(12)
sage: E.order()
12
sage: E.order() * E.random_point()
(0 : 1 : 0)

Python

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(7)), [Integer(0), Integer(1)]) # This curve has order 12
>>> E.set_order(Integer(12))
>>> E.order()
12
>>> E.order() * E.random_point()
(0 : 1 : 0)

Sage Live

E = EllipticCurve(GF(7), [0, 1]) # This curve has order 12
E.set_order(12)
E.order()
E.order() * E.random_point()

We now give a more interesting case, the NIST-P521 curve. Its order is too big to calculate with Sage, and takes a long time using other packages, so it is very useful here:

Sage

sage: p = 2^521 - 1
sage: prev_proof_state = proof.arithmetic()
sage: proof.arithmetic(False) # turn off primality checking
sage: F = GF(p)
sage: A = p - 3
sage: B = 1093849038073734274511112390766805569936207598951683748994586394495953116150735016013708737573759623248592132296706313309438452531591012912142327488478985984
sage: q = 6864797660130609714981900799081393217269435300143305409394463459185543183397655394245057746333217197532963996371363321113864768612440380340372808892707005449
sage: E = EllipticCurve([F(A), F(B)])
sage: E.set_order(q)
sage: G = E.random_point()
sage: G.order() * G  # This takes practically no time.
(0 : 1 : 0)
sage: proof.arithmetic(prev_proof_state) # restore state

Python

>>> from sage.all import *
>>> p = Integer(2)**Integer(521) - Integer(1)
>>> prev_proof_state = proof.arithmetic()
>>> proof.arithmetic(False) # turn off primality checking
>>> F = GF(p)
>>> A = p - Integer(3)
>>> B = Integer(1093849038073734274511112390766805569936207598951683748994586394495953116150735016013708737573759623248592132296706313309438452531591012912142327488478985984)
>>> q = Integer(6864797660130609714981900799081393217269435300143305409394463459185543183397655394245057746333217197532963996371363321113864768612440380340372808892707005449)
>>> E = EllipticCurve([F(A), F(B)])
>>> E.set_order(q)
>>> G = E.random_point()
>>> G.order() * G  # This takes practically no time.
(0 : 1 : 0)
>>> proof.arithmetic(prev_proof_state) # restore state

Sage Live

p = 2^521 - 1
prev_proof_state = proof.arithmetic()
proof.arithmetic(False) # turn off primality checking
F = GF(p)
A = p - 3
B = 1093849038073734274511112390766805569936207598951683748994586394495953116150735016013708737573759623248592132296706313309438452531591012912142327488478985984
q = 6864797660130609714981900799081393217269435300143305409394463459185543183397655394245057746333217197532963996371363321113864768612440380340372808892707005449
E = EllipticCurve([F(A), F(B)])
E.set_order(q)
G = E.random_point()
G.order() * G  # This takes practically no time.
proof.arithmetic(prev_proof_state) # restore state

It is an error to pass a value which is not an integer in the Hasse-Weil range:

Sage

sage: E = EllipticCurve(GF(7), [0, 1]) # This curve has order 12
sage: E.set_order("hi")
Traceback (most recent call last):
...
TypeError: unable to convert 'hi' to an integer
sage: E.set_order(0)
Traceback (most recent call last):
...
ValueError: Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 7 does not have order 0
sage: E.set_order(1000)
Traceback (most recent call last):
...
ValueError: Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 7 does not have order 1000

Python

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(7)), [Integer(0), Integer(1)]) # This curve has order 12
>>> E.set_order("hi")
Traceback (most recent call last):
...
TypeError: unable to convert 'hi' to an integer
>>> E.set_order(Integer(0))
Traceback (most recent call last):
...
ValueError: Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 7 does not have order 0
>>> E.set_order(Integer(1000))
Traceback (most recent call last):
...
ValueError: Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 7 does not have order 1000

Sage Live

E = EllipticCurve(GF(7), [0, 1]) # This curve has order 12
E.set_order("hi")
E.set_order(0)
E.set_order(1000)

It is also very likely an error to pass a value which is not the actual order of this curve. How unlikely is determined by num_checks, the factorization of the actual order, and the actual group structure:

Sage

sage: E = EllipticCurve(GF(1009), [0, 1]) # This curve has order 948
sage: E.set_order(947)
Traceback (most recent call last):
...
ValueError: Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 1009 does not have order 947

Python

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(1009)), [Integer(0), Integer(1)]) # This curve has order 948
>>> E.set_order(Integer(947))
Traceback (most recent call last):
...
ValueError: Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 1009 does not have order 947

Sage Live

E = EllipticCurve(GF(1009), [0, 1]) # This curve has order 948
E.set_order(947)

For curves over small finite fields, the order is cheap to compute, so it is computed directly and compared:

Sage

sage: E = EllipticCurve(GF(7), [0, 1]) # This curve has order 12
sage: E.set_order(11)
Traceback (most recent call last):
...
ValueError: Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 7 does not have order 11

Python

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(7)), [Integer(0), Integer(1)]) # This curve has order 12
>>> E.set_order(Integer(11))
Traceback (most recent call last):
...
ValueError: Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 7 does not have order 11

Sage Live

E = EllipticCurve(GF(7), [0, 1]) # This curve has order 12
E.set_order(11)

Todo

Add provable correctness check by computing the abelian group structure and comparing.

AUTHORS:

Mariah Lenox (2011-02-16): Initial implementation

Gareth Ma (2024-01-21): Fix bug for small curves

torsion_basis(n)[source]¶

Return a basis of the \(n\)-torsion subgroup of this elliptic curve, assuming it is fully rational.

EXAMPLES:

Sage

sage: # needs sage.rings.finite_rings
sage: E = EllipticCurve(GF(62207^2), [1,0])
sage: E.abelian_group()
Additive abelian group isomorphic to Z/62208 + Z/62208 embedded in
 Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x
  over Finite Field in z2 of size 62207^2
sage: PA,QA = E.torsion_basis(2^8)
sage: PA.weil_pairing(QA, 2^8).multiplicative_order()
256
sage: PB,QB = E.torsion_basis(3^5)
sage: PB.weil_pairing(QB, 3^5).multiplicative_order()
243

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> E = EllipticCurve(GF(Integer(62207)**Integer(2)), [Integer(1),Integer(0)])
>>> E.abelian_group()
Additive abelian group isomorphic to Z/62208 + Z/62208 embedded in
 Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x
  over Finite Field in z2 of size 62207^2
>>> PA,QA = E.torsion_basis(Integer(2)**Integer(8))
>>> PA.weil_pairing(QA, Integer(2)**Integer(8)).multiplicative_order()
256
>>> PB,QB = E.torsion_basis(Integer(3)**Integer(5))
>>> PB.weil_pairing(QB, Integer(3)**Integer(5)).multiplicative_order()
243

Sage Live

# needs sage.rings.finite_rings
E = EllipticCurve(GF(62207^2), [1,0])
E.abelian_group()
PA,QA = E.torsion_basis(2^8)
PA.weil_pairing(QA, 2^8).multiplicative_order()
PB,QB = E.torsion_basis(3^5)
PB.weil_pairing(QB, 3^5).multiplicative_order()

Sage

sage: E = EllipticCurve(GF(101), [4,4])
sage: E.torsion_basis(23)
Traceback (most recent call last):
...
ValueError: curve does not have full rational 23-torsion
sage: F = E.division_field(23); F
Finite Field in t of size 101^11
sage: EE = E.change_ring(F)
sage: P, Q = EE.torsion_basis(23)
sage: P  # random
(89*z11^10 + 51*z11^9 + 96*z11^8 + 8*z11^7 + 67*z11^6
 + 31*z11^5 + 55*z11^4 + 59*z11^3 + 28*z11^2 + 8*z11 + 88
 : 40*z11^10 + 33*z11^9 + 80*z11^8 + 87*z11^7 + 97*z11^6
 + 69*z11^5 + 56*z11^4 + 17*z11^3 + 26*z11^2 + 69*z11 + 11
 : 1)
sage: Q  # random
(25*z11^10 + 61*z11^9 + 49*z11^8 + 17*z11^7 + 80*z11^6
 + 20*z11^5 + 49*z11^4 + 52*z11^3 + 61*z11^2 + 27*z11 + 61
 : 60*z11^10 + 91*z11^9 + 89*z11^8 + 7*z11^7 + 63*z11^6
 + 55*z11^5 + 23*z11^4 + 17*z11^3 + 90*z11^2 + 91*z11 + 68
 : 1)

Python

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(101)), [Integer(4),Integer(4)])
>>> E.torsion_basis(Integer(23))
Traceback (most recent call last):
...
ValueError: curve does not have full rational 23-torsion
>>> F = E.division_field(Integer(23)); F
Finite Field in t of size 101^11
>>> EE = E.change_ring(F)
>>> P, Q = EE.torsion_basis(Integer(23))
>>> P  # random
(89*z11^10 + 51*z11^9 + 96*z11^8 + 8*z11^7 + 67*z11^6
 + 31*z11^5 + 55*z11^4 + 59*z11^3 + 28*z11^2 + 8*z11 + 88
 : 40*z11^10 + 33*z11^9 + 80*z11^8 + 87*z11^7 + 97*z11^6
 + 69*z11^5 + 56*z11^4 + 17*z11^3 + 26*z11^2 + 69*z11 + 11
 : 1)
>>> Q  # random
(25*z11^10 + 61*z11^9 + 49*z11^8 + 17*z11^7 + 80*z11^6
 + 20*z11^5 + 49*z11^4 + 52*z11^3 + 61*z11^2 + 27*z11 + 61
 : 60*z11^10 + 91*z11^9 + 89*z11^8 + 7*z11^7 + 63*z11^6
 + 55*z11^5 + 23*z11^4 + 17*z11^3 + 90*z11^2 + 91*z11 + 68
 : 1)

Sage Live

E = EllipticCurve(GF(101), [4,4])
E.torsion_basis(23)
F = E.division_field(23); F
EE = E.change_ring(F)
P, Q = EE.torsion_basis(23)
P  # random
Q  # random

Python

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(101)), [Integer(4),Integer(4)])
>>> E.torsion_basis(Integer(23))
Traceback (most recent call last):
...
ValueError: curve does not have full rational 23-torsion
>>> F = E.division_field(Integer(23)); F
Finite Field in t of size 101^11
>>> EE = E.change_ring(F)
>>> P, Q = EE.torsion_basis(Integer(23))
>>> P  # random
(89*z11^10 + 51*z11^9 + 96*z11^8 + 8*z11^7 + 67*z11^6
 + 31*z11^5 + 55*z11^4 + 59*z11^3 + 28*z11^2 + 8*z11 + 88
 : 40*z11^10 + 33*z11^9 + 80*z11^8 + 87*z11^7 + 97*z11^6
 + 69*z11^5 + 56*z11^4 + 17*z11^3 + 26*z11^2 + 69*z11 + 11
 : 1)
>>> Q  # random
(25*z11^10 + 61*z11^9 + 49*z11^8 + 17*z11^7 + 80*z11^6
 + 20*z11^5 + 49*z11^4 + 52*z11^3 + 61*z11^2 + 27*z11 + 61
 : 60*z11^10 + 91*z11^9 + 89*z11^8 + 7*z11^7 + 63*z11^6
 + 55*z11^5 + 23*z11^4 + 17*z11^3 + 90*z11^2 + 91*z11 + 68
 : 1)

Sage Live

E = EllipticCurve(GF(101), [4,4])
E.torsion_basis(23)
F = E.division_field(23); F
EE = E.change_ring(F)
P, Q = EE.torsion_basis(23)
P  # random
Q  # random

See also

Use division_field() to determine a field extension containing the full \(\ell\)-torsion subgroup.

ALGORITHM:

This method currently uses abelian_group() and AdditiveAbelianGroupWrapper.torsion_subgroup().

trace_of_frobenius()[source]¶

Return the trace of Frobenius acting on this elliptic curve.

Note

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

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(101)),[Integer(2),Integer(3)])
>>> E.trace_of_frobenius()
6
>>> E = EllipticCurve(GF(Integer(11)**Integer(5),'a'),[Integer(2),Integer(5)])                                 # needs sage.rings.finite_rings
>>> E.trace_of_frobenius()                                                # needs sage.rings.finite_rings
802

Sage Live

E = EllipticCurve(GF(101),[2,3])
E.trace_of_frobenius()
E = EllipticCurve(GF(11^5,'a'),[2,5])                                 # needs sage.rings.finite_rings
E.trace_of_frobenius()                                                # needs sage.rings.finite_rings

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

Sage

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

Python

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(3)**Integer(5),'a'),[-Integer(1),-Integer(1)])                                # needs sage.rings.finite_rings
>>> E.trace_of_frobenius()                                                # needs sage.rings.finite_rings
-27

Sage Live

E = EllipticCurve(GF(3^5,'a'),[-1,-1])                                # needs sage.rings.finite_rings
E.trace_of_frobenius()                                                # needs sage.rings.finite_rings

twists()[source]¶

Return a list of \(k\)-isomorphism representatives of all twists of this elliptic curve, where \(k\) is the base field.

The input curve appears as the first entry of the result.

Note

A twist of \(E/k\) is an elliptic curve \(E'\) defined over \(k\) that is isomorphic to \(E\) over the algebraic closure \(\bar k\).

Most elliptic curves over a finite field only admit a single nontrivial twist (the quadratic twist); the only exceptions are curves with \(j\)-invariant \(0\) or \(1728\).

In all cases the sum over all the twists \(E'\) of \(1/|Aut(E')|\) is 1.

See also

EXAMPLES:

Sage

sage: E = EllipticCurve(GF(97), [1,1])
sage: E.j_invariant()
54
sage: E.twists()
[Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 97,
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 97]

Python

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(97)), [Integer(1),Integer(1)])
>>> E.j_invariant()
54
>>> E.twists()
[Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 97,
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 97]

Sage Live

E = EllipticCurve(GF(97), [1,1])
E.j_invariant()
E.twists()

Sage

sage: E = EllipticCurve(GF(97), [1,0])
sage: E.j_invariant()
79
sage: E.twists()
[Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 97,
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 97,
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 97,
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 97]

Python

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(97)), [Integer(1),Integer(0)])
>>> E.j_invariant()
79
>>> E.twists()
[Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 97,
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 97,
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 97,
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 97]

Sage Live

E = EllipticCurve(GF(97), [1,0])
E.j_invariant()
E.twists()

Python

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(97)), [Integer(1),Integer(0)])
>>> E.j_invariant()
79
>>> E.twists()
[Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 97,
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 97,
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 97,
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 97]

Sage Live

E = EllipticCurve(GF(97), [1,0])
E.j_invariant()
E.twists()

Sage

sage: E = EllipticCurve(GF(97), [0,1])
sage: E.j_invariant()
0
sage: E.twists()
[Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 97,
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 97,
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 97,
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 97,
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 97,
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 97]

Python

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(97)), [Integer(0),Integer(1)])
>>> E.j_invariant()
0
>>> E.twists()
[Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 97,
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 97,
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 97,
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 97,
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 97,
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 97]

Sage Live

E = EllipticCurve(GF(97), [0,1])
E.j_invariant()
E.twists()

Python

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(97)), [Integer(0),Integer(1)])
>>> E.j_invariant()
0
>>> E.twists()
[Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 97,
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 97,
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 97,
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 97,
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 97,
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 97]

Sage Live

E = EllipticCurve(GF(97), [0,1])
E.j_invariant()
E.twists()

This can be useful to quickly compute a list of all elliptic curves over a finite field \(k\) up to \(k\)-isomorphism:

Sage

sage: Es = [E for j in GF(13) for E in EllipticCurve(j=j).twists()]
sage: len(Es)
32
sage: Es
[Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 13,
 ...
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 13]

Python

>>> from sage.all import *
>>> Es = [E for j in GF(Integer(13)) for E in EllipticCurve(j=j).twists()]
>>> len(Es)
32
>>> Es
[Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 13,
 ...
 Elliptic Curve defined by y^2 = x^3 + ... over Finite Field of size 13]

Sage Live

Es = [E for j in GF(13) for E in EllipticCurve(j=j).twists()]
len(Es)
Es

In characteristic 3, the number of twists is 2 except for \(j=0=1728\), when there are either 4 or 6 depending on whether the field has odd or even degree over \(\GF{3}\):

Sage

sage: # needs sage.rings.finite_rings
sage: K = GF(3**5)
sage: [E.ainvs() for E in EllipticCurve(j=K(1)).twists()]
[(0, 1, 0, 0, 2), (0, z5, 0, 0, 2*z5^3)]

sage: # needs sage.rings.finite_rings
sage: K = GF(3**5)
sage: [E.ainvs() for E in EllipticCurve(j=K(0)).twists()] # random
[(0, 0, 0, 1, 0),
 (0, 0, 0, 2, 0),
 (0, 0, 0, 2, z5^4 + z5^3 + z5^2),
 (0, 0, 0, 2, 2*z5^4 + 2*z5^3 + 2*z5^2)]

sage: # needs sage.rings.finite_rings
sage: K = GF(3**4)
sage: [E.ainvs() for E in EllipticCurve(j=K(1)).twists()]
[(0, 1, 0, 0, 2), (0, z4, 0, 0, 2*z4^3)]

sage: # needs sage.rings.finite_rings
sage: K = GF(3**4)
sage: [E.ainvs() for E in EllipticCurve(j=K(0)).twists()] # random
[(0, 0, 0, 1, 0),
 (0, 0, 0, 2, 2*z4^3 + 2*z4^2 + 2*z4 + 2),
 (0, 0, 0, 1, 0),
 (0, 0, 0, 1, 2*z4^3 + 2*z4^2 + 2*z4 + 2),
 (0, 0, 0, z4, 0),
 (0, 0, 0, z4^3, 0)]

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> K = GF(Integer(3)**Integer(5))
>>> [E.ainvs() for E in EllipticCurve(j=K(Integer(1))).twists()]
[(0, 1, 0, 0, 2), (0, z5, 0, 0, 2*z5^3)]

>>> # needs sage.rings.finite_rings
>>> K = GF(Integer(3)**Integer(5))
>>> [E.ainvs() for E in EllipticCurve(j=K(Integer(0))).twists()] # random
[(0, 0, 0, 1, 0),
 (0, 0, 0, 2, 0),
 (0, 0, 0, 2, z5^4 + z5^3 + z5^2),
 (0, 0, 0, 2, 2*z5^4 + 2*z5^3 + 2*z5^2)]

>>> # needs sage.rings.finite_rings
>>> K = GF(Integer(3)**Integer(4))
>>> [E.ainvs() for E in EllipticCurve(j=K(Integer(1))).twists()]
[(0, 1, 0, 0, 2), (0, z4, 0, 0, 2*z4^3)]

>>> # needs sage.rings.finite_rings
>>> K = GF(Integer(3)**Integer(4))
>>> [E.ainvs() for E in EllipticCurve(j=K(Integer(0))).twists()] # random
[(0, 0, 0, 1, 0),
 (0, 0, 0, 2, 2*z4^3 + 2*z4^2 + 2*z4 + 2),
 (0, 0, 0, 1, 0),
 (0, 0, 0, 1, 2*z4^3 + 2*z4^2 + 2*z4 + 2),
 (0, 0, 0, z4, 0),
 (0, 0, 0, z4^3, 0)]

Sage Live

# needs sage.rings.finite_rings
K = GF(3**5)
[E.ainvs() for E in EllipticCurve(j=K(1)).twists()]
# needs sage.rings.finite_rings
K = GF(3**5)
[E.ainvs() for E in EllipticCurve(j=K(0)).twists()] # random
# needs sage.rings.finite_rings
K = GF(3**4)
[E.ainvs() for E in EllipticCurve(j=K(1)).twists()]
# needs sage.rings.finite_rings
K = GF(3**4)
[E.ainvs() for E in EllipticCurve(j=K(0)).twists()] # random

In characteristic 2, the number of twists is 2 except for \(j=0=1728\), when there are either 3 or 7 depending on whether the field has odd or even degree over \(\GF{2}\):

Sage

sage: # needs sage.rings.finite_rings
sage: K = GF(2**7)
sage: [E.ainvs() for E in EllipticCurve(j=K(1)).twists()]
[(1, 0, 0, 0, 1), (1, 1, 0, 0, 1)]

sage: # needs sage.rings.finite_rings
sage: K = GF(2**7)
sage: [E.ainvs() for E in EllipticCurve(j=K(0)).twists()]
[(0, 0, 1, 0, 0), (0, 0, 1, 1, 0), (0, 0, 1, 1, 1)]

sage: # needs sage.rings.finite_rings
sage: K = GF(2**8)
sage: [E.ainvs() for E in EllipticCurve(j=K(1)).twists()] # random
[(1, 0, 0, 0, 1), (1, z8^7 + z8^6 + z8^5 + z8^4 + z8^2 + z8, 0, 0, 1)]

sage: # needs sage.rings.finite_rings
sage: K = GF(2**8)
sage: [E.ainvs() for E in EllipticCurve(j=K(0)).twists()] # random
[(0, 0, 1, 0, 0),
 (0, 0, 1, 0, z8^5 + z8^4 + z8^3),
 (0, 0, 1, z8^6 + z8^5 + z8^2 + 1, 0),
 (0, 0, z8^4 + z8^3 + z8^2 + 1, 0, 0),
 (0, 0, z8^4 + z8^3 + z8^2 + 1, 0, z8^3 + z8^2 + 1),
 (0, 0, z8^6 + z8^3 + z8^2, 0, 0),
 (0, 0, z8^6 + z8^3 + z8^2, 0, z8^3 + z8^2)]

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> K = GF(Integer(2)**Integer(7))
>>> [E.ainvs() for E in EllipticCurve(j=K(Integer(1))).twists()]
[(1, 0, 0, 0, 1), (1, 1, 0, 0, 1)]

>>> # needs sage.rings.finite_rings
>>> K = GF(Integer(2)**Integer(7))
>>> [E.ainvs() for E in EllipticCurve(j=K(Integer(0))).twists()]
[(0, 0, 1, 0, 0), (0, 0, 1, 1, 0), (0, 0, 1, 1, 1)]

>>> # needs sage.rings.finite_rings
>>> K = GF(Integer(2)**Integer(8))
>>> [E.ainvs() for E in EllipticCurve(j=K(Integer(1))).twists()] # random
[(1, 0, 0, 0, 1), (1, z8^7 + z8^6 + z8^5 + z8^4 + z8^2 + z8, 0, 0, 1)]

>>> # needs sage.rings.finite_rings
>>> K = GF(Integer(2)**Integer(8))
>>> [E.ainvs() for E in EllipticCurve(j=K(Integer(0))).twists()] # random
[(0, 0, 1, 0, 0),
 (0, 0, 1, 0, z8^5 + z8^4 + z8^3),
 (0, 0, 1, z8^6 + z8^5 + z8^2 + 1, 0),
 (0, 0, z8^4 + z8^3 + z8^2 + 1, 0, 0),
 (0, 0, z8^4 + z8^3 + z8^2 + 1, 0, z8^3 + z8^2 + 1),
 (0, 0, z8^6 + z8^3 + z8^2, 0, 0),
 (0, 0, z8^6 + z8^3 + z8^2, 0, z8^3 + z8^2)]

Sage Live

# needs sage.rings.finite_rings
K = GF(2**7)
[E.ainvs() for E in EllipticCurve(j=K(1)).twists()]
# needs sage.rings.finite_rings
K = GF(2**7)
[E.ainvs() for E in EllipticCurve(j=K(0)).twists()]
# needs sage.rings.finite_rings
K = GF(2**8)
[E.ainvs() for E in EllipticCurve(j=K(1)).twists()] # random
# needs sage.rings.finite_rings
K = GF(2**8)
[E.ainvs() for E in EllipticCurve(j=K(0)).twists()] # random

sage.schemes.elliptic_curves.ell_finite_field.EllipticCurve_with_order(m, D)[source]¶

Return an iterator for elliptic curves over finite fields with the given order. The curves are computed using the Complex Multiplication (CM) method.

A Factorization can be passed for m, in which case the algorithm is more efficient.

If D is specified, it is used as the discriminant.

EXAMPLES:

Sage

sage: from sage.schemes.elliptic_curves.ell_finite_field import EllipticCurve_with_order
sage: E = next(EllipticCurve_with_order(1234)); E  # random
Elliptic Curve defined by y^2 = x^3 + 1142*x + 1209 over Finite Field of size 1237
sage: E.order() == 1234
True

Python

>>> from sage.all import *
>>> from sage.schemes.elliptic_curves.ell_finite_field import EllipticCurve_with_order
>>> E = next(EllipticCurve_with_order(Integer(1234))); E  # random
Elliptic Curve defined by y^2 = x^3 + 1142*x + 1209 over Finite Field of size 1237
>>> E.order() == Integer(1234)
True

Sage Live

from sage.schemes.elliptic_curves.ell_finite_field import EllipticCurve_with_order
E = next(EllipticCurve_with_order(1234)); E  # random
E.order() == 1234

When iter is set, the function returns an iterator of all elliptic curves with the given order:

Sage

sage: from sage.schemes.elliptic_curves.ell_finite_field import EllipticCurve_with_order
sage: it = EllipticCurve_with_order(21); it
<generator object EllipticCurve_with_order at 0x...>
sage: E = next(it); E  # random
Elliptic Curve defined by y^2 = x^3 + 6*x + 14 over Finite Field of size 23
sage: E.order() == 21
True
sage: Es = [E] + list(it); Es  # random
[Elliptic Curve defined by y^2 = x^3 + 6*x + 14 over Finite Field of size 23,
 Elliptic Curve defined by y^2 = x^3 + 12*x + 4 over Finite Field of size 23,
 Elliptic Curve defined by y^2 = x^3 + 5*x + 2 over Finite Field of size 23,
 Elliptic Curve defined by y^2 = x^3 + (z2+3) over Finite Field in z2 of size 5^2,
 Elliptic Curve defined by y^2 = x^3 + (2*z2+2) over Finite Field in z2 of size 5^2,
 Elliptic Curve defined by y^2 = x^3 + 7*x + 1 over Finite Field of size 19,
 Elliptic Curve defined by y^2 = x^3 + 17*x + 10 over Finite Field of size 19,
 Elliptic Curve defined by y^2 = x^3 + 5*x + 12 over Finite Field of size 17,
 Elliptic Curve defined by y^2 = x^3 + 9*x + 1 over Finite Field of size 17,
 Elliptic Curve defined by y^2 = x^3 + 7*x + 6 over Finite Field of size 17,
 Elliptic Curve defined by y^2 = x^3 + z3^2*x^2 + (2*z3^2+z3) over Finite Field in z3 of size 3^3,
 Elliptic Curve defined by y^2 = x^3 + (z3^2+2*z3+1)*x^2 + (2*z3^2+2*z3) over Finite Field in z3 of size 3^3,
 Elliptic Curve defined by y^2 = x^3 + (z3^2+z3+1)*x^2 + (2*z3^2+1) over Finite Field in z3 of size 3^3,
 Elliptic Curve defined by y^2 + (z4^2+z4+1)*y = x^3 over Finite Field in z4 of size 2^4,
 Elliptic Curve defined by y^2 + (z4^2+z4)*y = x^3 over Finite Field in z4 of size 2^4,
 Elliptic Curve defined by y^2 = x^3 + 18*x + 26 over Finite Field of size 29,
 Elliptic Curve defined by y^2 = x^3 + 11*x + 19 over Finite Field of size 29,
 Elliptic Curve defined by y^2 = x^3 + 4 over Finite Field of size 19,
 Elliptic Curve defined by y^2 = x^3 + 19 over Finite Field of size 31,
 Elliptic Curve defined by y^2 = x^3 + 4 over Finite Field of size 13]
sage: all(E.order() == 21 for E in Es)
True

Python

>>> from sage.all import *
>>> from sage.schemes.elliptic_curves.ell_finite_field import EllipticCurve_with_order
>>> it = EllipticCurve_with_order(Integer(21)); it
<generator object EllipticCurve_with_order at 0x...>
>>> E = next(it); E  # random
Elliptic Curve defined by y^2 = x^3 + 6*x + 14 over Finite Field of size 23
>>> E.order() == Integer(21)
True
>>> Es = [E] + list(it); Es  # random
[Elliptic Curve defined by y^2 = x^3 + 6*x + 14 over Finite Field of size 23,
 Elliptic Curve defined by y^2 = x^3 + 12*x + 4 over Finite Field of size 23,
 Elliptic Curve defined by y^2 = x^3 + 5*x + 2 over Finite Field of size 23,
 Elliptic Curve defined by y^2 = x^3 + (z2+3) over Finite Field in z2 of size 5^2,
 Elliptic Curve defined by y^2 = x^3 + (2*z2+2) over Finite Field in z2 of size 5^2,
 Elliptic Curve defined by y^2 = x^3 + 7*x + 1 over Finite Field of size 19,
 Elliptic Curve defined by y^2 = x^3 + 17*x + 10 over Finite Field of size 19,
 Elliptic Curve defined by y^2 = x^3 + 5*x + 12 over Finite Field of size 17,
 Elliptic Curve defined by y^2 = x^3 + 9*x + 1 over Finite Field of size 17,
 Elliptic Curve defined by y^2 = x^3 + 7*x + 6 over Finite Field of size 17,
 Elliptic Curve defined by y^2 = x^3 + z3^2*x^2 + (2*z3^2+z3) over Finite Field in z3 of size 3^3,
 Elliptic Curve defined by y^2 = x^3 + (z3^2+2*z3+1)*x^2 + (2*z3^2+2*z3) over Finite Field in z3 of size 3^3,
 Elliptic Curve defined by y^2 = x^3 + (z3^2+z3+1)*x^2 + (2*z3^2+1) over Finite Field in z3 of size 3^3,
 Elliptic Curve defined by y^2 + (z4^2+z4+1)*y = x^3 over Finite Field in z4 of size 2^4,
 Elliptic Curve defined by y^2 + (z4^2+z4)*y = x^3 over Finite Field in z4 of size 2^4,
 Elliptic Curve defined by y^2 = x^3 + 18*x + 26 over Finite Field of size 29,
 Elliptic Curve defined by y^2 = x^3 + 11*x + 19 over Finite Field of size 29,
 Elliptic Curve defined by y^2 = x^3 + 4 over Finite Field of size 19,
 Elliptic Curve defined by y^2 = x^3 + 19 over Finite Field of size 31,
 Elliptic Curve defined by y^2 = x^3 + 4 over Finite Field of size 13]
>>> all(E.order() == Integer(21) for E in Es)
True

Sage Live

from sage.schemes.elliptic_curves.ell_finite_field import EllipticCurve_with_order
it = EllipticCurve_with_order(21); it
E = next(it); E  # random
E.order() == 21
Es = [E] + list(it); Es  # random
all(E.order() == 21 for E in Es)

Indeed, we can verify that this is correct. Hasse’s bounds tell us that \(p \leq 50\) (approximately), and the rest can be checked via bruteforce:

Sage

sage: for p in prime_range(50):
....:     for j in range(p):
....:         E0 = EllipticCurve(GF(p), j=j)
....:         for Et in E0.twists():
....:             if Et.order() == 21:
....:                 assert any(Et.is_isomorphic(E) for E in Es)

Python

>>> from sage.all import *
>>> for p in prime_range(Integer(50)):
...     for j in range(p):
...         E0 = EllipticCurve(GF(p), j=j)
...         for Et in E0.twists():
...             if Et.order() == Integer(21):
...                 assert any(Et.is_isomorphic(E) for E in Es)

Sage Live

for p in prime_range(50):
    for j in range(p):
        E0 = EllipticCurve(GF(p), j=j)
        for Et in E0.twists():
            if Et.order() == 21:
                assert any(Et.is_isomorphic(E) for E in Es)

Note

The output curves are not deterministic, as EllipticCurve_finite_field.twists() is not deterministic. However, the order of the j-invariants and base fields is fixed.

AUTHORS:

Gareth Ma and Giacomo Pope (Sage Days 123): initial version

sage.schemes.elliptic_curves.ell_finite_field.EllipticCurve_with_prime_order(N)[source]¶

Given a prime number N, find another prime number \(p\) and construct an elliptic curve \(E\) defined over \(\mathbb F_p\) such that \(\#E(\mathbb F_p) = N\).

INPUT:

N – integer; the order for which we seek an elliptic curve. Must be a prime number.

OUTPUT: an iterator of (some) elliptic curves \(E/\mathbb F_p\) of order N

ALGORITHM:

Our algorithm is based on [BS2007], Algorithm 2.2, but we deviate for several key steps. Firstly, the authors in the paper perform the search for a suitable \(D\) incrementally, by enlarging the table \(S\) by \(log(N)\)-size interval of primes \(p\) and testing all products of distinct primes \(p\) (or rather \(p^*\)). We find this difficult to implement without testing duplicate \(D\)s, so we instead enlarge the table one prime at a time (effectively replacing \([r\log(N), (r + 1)\log(N)]\) in the paper by \([r, r]\)). To compensate for the speed loss, we begin the algorithm by prefilling \(S\) with the primes below \(1000\) (satisfying quadratic reciprocity properties). The constant \(1000\) is determined experimentally to be fast for many purposes, and for most \(N\) we tested we are able to find a suitable small \(D\) without increasing the size of \(S\).

The paper also doesn’t specify how to enumerate such \(D\)s, which recall should be product of distinct values in the table \(S\). We implement this with a priority queue (min heap), which also allows us to search for the suitable \(D\)s in increasing (absolute value) order. This is suitable for the algorithm because smaller \(D\) means the Hilbert class polynomial is computed quicker.

Finally, to avoid repeatedly testing the same \(D\)s, we require the latest prime to be added to the table to be included as a factor of \(D\) (see code for more explanation). As we need to find integers \(x, y\) such that \(x^2 + (-D)y^2 = 4N\) with \(D < 0\) and \(N\) prime, we actually need \(|D| \leq 4N\), so we terminate the algorithm when the primes in the table are larger than that bound. This makes the iterator return all curves it can find in finite time.

ALGORITHM: Based on [BS2007], Algorithm 2.2

EXAMPLES:

Sage

sage: N = 8314040072427107567
sage: E = next(EllipticCurve_with_prime_order(N))
sage: E
Elliptic Curve defined by y^2 = x^3 + 4757897140353078952*x + 1841350074072114366
 over Finite Field of size 8314040074357871443
sage: E.has_order(N)
True

Python

>>> from sage.all import *
>>> N = Integer(8314040072427107567)
>>> E = next(EllipticCurve_with_prime_order(N))
>>> E
Elliptic Curve defined by y^2 = x^3 + 4757897140353078952*x + 1841350074072114366
 over Finite Field of size 8314040074357871443
>>> E.has_order(N)
True

Sage Live

N = 8314040072427107567
E = next(EllipticCurve_with_prime_order(N))
E
E.has_order(N)

The returned curves are sometimes random because twists() is not deterministic. However, it’s always isomorphic:

Sage

sage: E = next(EllipticCurve_with_prime_order(23)); E # random
Elliptic Curve defined by y^2 = x^3 + 12*x + 6 over Finite Field of size 17
sage: E.is_isomorphic(EllipticCurve(GF(17), [3, 5]))
True

Python

>>> from sage.all import *
>>> E = next(EllipticCurve_with_prime_order(Integer(23))); E # random
Elliptic Curve defined by y^2 = x^3 + 12*x + 6 over Finite Field of size 17
>>> E.is_isomorphic(EllipticCurve(GF(Integer(17)), [Integer(3), Integer(5)]))
True

Sage Live

E = next(EllipticCurve_with_prime_order(23)); E # random
E.is_isomorphic(EllipticCurve(GF(17), [3, 5]))

You can directly iterate over the iterator; here only on the first 10 curves:

Sage

sage: N = 54675917
sage: for _, E in zip(range(10), EllipticCurve_with_prime_order(N)):
....:     assert E.has_order(N)

Python

>>> from sage.all import *
>>> N = Integer(54675917)
>>> for _, E in zip(range(Integer(10)), EllipticCurve_with_prime_order(N)):
...     assert E.has_order(N)

Sage Live

N = 54675917
for _, E in zip(range(10), EllipticCurve_with_prime_order(N)):
    assert E.has_order(N)

It works for large primes:

Sage

sage: N = 2666207849820848272386538889527600954292544013630953455833
sage: E = next(EllipticCurve_with_prime_order(N)); E
Elliptic Curve defined by y^2 = x^3 + 2666207849820848272386538889427721639173508298483739490459*x
 + 77986137112576 over Finite Field of size 2666207849820848272386538889427721639173508298487130585243
sage: E.has_order(N)
True

Python

>>> from sage.all import *
>>> N = Integer(2666207849820848272386538889527600954292544013630953455833)
>>> E = next(EllipticCurve_with_prime_order(N)); E
Elliptic Curve defined by y^2 = x^3 + 2666207849820848272386538889427721639173508298483739490459*x
 + 77986137112576 over Finite Field of size 2666207849820848272386538889427721639173508298487130585243
>>> E.has_order(N)
True

Sage Live

N = 2666207849820848272386538889527600954292544013630953455833
E = next(EllipticCurve_with_prime_order(N)); E
E.has_order(N)

Another example for large primes:

Sage

sage: N = next_prime(2^256)
sage: E = next(EllipticCurve_with_prime_order(N)); E                            # random
Elliptic Curve defined by y^2 = x^3 + 6056521267553273205988520276135607487700943205131813669424576873701361709521*x
 + 86942739955486781674010637133214195706465136689012129911736706024465988573567 over Finite Field of size
 115792089237316195423570985008687907853847329310253429036565151476471048389761
sage: E.j_invariant()
111836223967433630316209796253554285080540088646141285337487360944738698436350
sage: E.has_order(N)
True

Python

>>> from sage.all import *
>>> N = next_prime(Integer(2)**Integer(256))
>>> E = next(EllipticCurve_with_prime_order(N)); E                            # random
Elliptic Curve defined by y^2 = x^3 + 6056521267553273205988520276135607487700943205131813669424576873701361709521*x
 + 86942739955486781674010637133214195706465136689012129911736706024465988573567 over Finite Field of size
 115792089237316195423570985008687907853847329310253429036565151476471048389761
>>> E.j_invariant()
111836223967433630316209796253554285080540088646141285337487360944738698436350
>>> E.has_order(N)
True

Sage Live

N = next_prime(2^256)
E = next(EllipticCurve_with_prime_order(N)); E                            # random
E.j_invariant()
E.has_order(N)

Note that the iterator does not return all curves with the given order:

Sage

sage: any(E.base_ring() is GF(7) for E in EllipticCurve_with_prime_order(7))
False
sage: EllipticCurve(GF(7), [0, 5]).order()
7

Python

>>> from sage.all import *
>>> any(E.base_ring() is GF(Integer(7)) for E in EllipticCurve_with_prime_order(Integer(7)))
False
>>> EllipticCurve(GF(Integer(7)), [Integer(0), Integer(5)]).order()
7

Sage Live

any(E.base_ring() is GF(7) for E in EllipticCurve_with_prime_order(7))
EllipticCurve(GF(7), [0, 5]).order()

However, experimentally it returns many of them. Here it returns all of them:

Sage

sage: N = 23
sage: set_random_seed(1337)  # as the function returns random twists of curves
sage: curves = list(EllipticCurve_with_prime_order(N)); curves  # random
[Elliptic Curve defined by y^2 = x^3 + 3*x + 5 over Finite Field of size 17,
 Elliptic Curve defined by y^2 = x^3 + 19*x + 14 over Finite Field of size 31,
 Elliptic Curve defined by y^2 = x^3 + 2*x + 9 over Finite Field of size 19,
 Elliptic Curve defined by y^2 = x^3 + 7*x + 18 over Finite Field of size 29,
 Elliptic Curve defined by y^2 = x^3 + 20*x + 20 over Finite Field of size 23,
 Elliptic Curve defined by y^2 = x^3 + 10*x + 16 over Finite Field of size 23]
sage: import itertools
sage: # These are the only primes, by the Hasse-Weil bound
sage: for q in prime_range(17, 35):
....:     K = GF(q)
....:     for u in itertools.product(range(q), repeat=2):
....:         try: E = EllipticCurve(GF(q), u)
....:         except ArithmeticError: continue
....:         if E.has_order(N):
....:             assert any(E.is_isomorphic(E_) for E_ in curves)

Python

>>> from sage.all import *
>>> N = Integer(23)
>>> set_random_seed(Integer(1337))  # as the function returns random twists of curves
>>> curves = list(EllipticCurve_with_prime_order(N)); curves  # random
[Elliptic Curve defined by y^2 = x^3 + 3*x + 5 over Finite Field of size 17,
 Elliptic Curve defined by y^2 = x^3 + 19*x + 14 over Finite Field of size 31,
 Elliptic Curve defined by y^2 = x^3 + 2*x + 9 over Finite Field of size 19,
 Elliptic Curve defined by y^2 = x^3 + 7*x + 18 over Finite Field of size 29,
 Elliptic Curve defined by y^2 = x^3 + 20*x + 20 over Finite Field of size 23,
 Elliptic Curve defined by y^2 = x^3 + 10*x + 16 over Finite Field of size 23]
>>> import itertools
>>> # These are the only primes, by the Hasse-Weil bound
>>> for q in prime_range(Integer(17), Integer(35)):
...     K = GF(q)
...     for u in itertools.product(range(q), repeat=Integer(2)):
...         try: E = EllipticCurve(GF(q), u)
...         except ArithmeticError: continue
...         if E.has_order(N):
...             assert any(E.is_isomorphic(E_) for E_ in curves)

Sage Live

N = 23
set_random_seed(1337)  # as the function returns random twists of curves
curves = list(EllipticCurve_with_prime_order(N)); curves  # random
import itertools
# These are the only primes, by the Hasse-Weil bound
for q in prime_range(17, 35):
    K = GF(q)
    for u in itertools.product(range(q), repeat=2):
        try: E = EllipticCurve(GF(q), u)
        except ArithmeticError: continue
        if E.has_order(N):
            assert any(E.is_isomorphic(E_) for E_ in curves)

The algorithm is efficient for small N due to the low number of suitable discriminants (see the abs_products_under internal function of the code for details):

Sage

sage: len(list(EllipticCurve_with_prime_order(next_prime(5000))))
534
sage: len(list(EllipticCurve_with_prime_order(next_prime(50000))))              # long time (6s)
3841

Python

>>> from sage.all import *
>>> len(list(EllipticCurve_with_prime_order(next_prime(Integer(5000)))))
534
>>> len(list(EllipticCurve_with_prime_order(next_prime(Integer(50000)))))              # long time (6s)
3841

Sage Live

len(list(EllipticCurve_with_prime_order(next_prime(5000))))
len(list(EllipticCurve_with_prime_order(next_prime(50000))))              # long time (6s)

There is different verbose data for level \(2\) to \(4\), though level \(3\) rarely logs anything (it logs when a new prime \(p\) is added to the smoothness bound):

Sage

sage: from sage.misc.verbose import set_verbose
sage: set_random_seed(1337)  # as the function returns random twists of curves
sage: for _, E in zip(range(3), EllipticCurve_with_prime_order(10^9 + 7)):
....:     print(E)
Elliptic Curve defined by y^2 = x^3 + 265977778*x + 120868502 over Finite Field of size 1000041437
Elliptic Curve defined by y^2 = x^3 + 689795416*x + 188156157 over Finite Field of size 999969307
Elliptic Curve defined by y^2 = x^3 + 999178436*x + 900579394 over Finite Field of size 999969307
sage: set_verbose(2)
sage: set_random_seed(1337)
sage: for _, E in zip(range(3), EllipticCurve_with_prime_order(10^9 + 7)):
....:     print(E)
verbose 2 (...: ell_finite_field.py, EllipticCurve_with_prime_order) Computing the Hilbert class polynomial H_-163
Elliptic Curve defined by y^2 = x^3 + 265977778*x + 120868502 over Finite Field of size 1000041437
verbose 2 (...: ell_finite_field.py, EllipticCurve_with_prime_order) Computing the Hilbert class polynomial H_-667
Elliptic Curve defined by y^2 = x^3 + 689795416*x + 188156157 over Finite Field of size 999969307
Elliptic Curve defined by y^2 = x^3 + 999178436*x + 900579394 over Finite Field of size 999969307
sage: set_verbose(4)
sage: set_random_seed(1337)
sage: for _, E in zip(range(3), EllipticCurve_with_prime_order(10^9 + 7)):
....:     print(E)
verbose 4 (...: ell_finite_field.py, EllipticCurve_with_prime_order) Testing D=-19
...
verbose 4 (...: ell_finite_field.py, EllipticCurve_with_prime_order) Testing D=-163
verbose 2 (...: ell_finite_field.py, EllipticCurve_with_prime_order) Computing the Hilbert class polynomial H_-163
Elliptic Curve defined by y^2 = x^3 + 265977778*x + 120868502 over Finite Field of size 1000041437
verbose 4 (...: ell_finite_field.py, EllipticCurve_with_prime_order) Testing D=-179
...
verbose 4 (...: ell_finite_field.py, EllipticCurve_with_prime_order) Testing D=-667
verbose 2 (...: ell_finite_field.py, EllipticCurve_with_prime_order) Computing the Hilbert class polynomial H_-667
Elliptic Curve defined by y^2 = x^3 + 689795416*x + 188156157 over Finite Field of size 999969307
Elliptic Curve defined by y^2 = x^3 + 999178436*x + 900579394 over Finite Field of size 999969307

Python

>>> from sage.all import *
>>> from sage.misc.verbose import set_verbose
>>> set_random_seed(Integer(1337))  # as the function returns random twists of curves
>>> for _, E in zip(range(Integer(3)), EllipticCurve_with_prime_order(Integer(10)**Integer(9) + Integer(7))):
...     print(E)
Elliptic Curve defined by y^2 = x^3 + 265977778*x + 120868502 over Finite Field of size 1000041437
Elliptic Curve defined by y^2 = x^3 + 689795416*x + 188156157 over Finite Field of size 999969307
Elliptic Curve defined by y^2 = x^3 + 999178436*x + 900579394 over Finite Field of size 999969307
>>> set_verbose(Integer(2))
>>> set_random_seed(Integer(1337))
>>> for _, E in zip(range(Integer(3)), EllipticCurve_with_prime_order(Integer(10)**Integer(9) + Integer(7))):
...     print(E)
verbose 2 (...: ell_finite_field.py, EllipticCurve_with_prime_order) Computing the Hilbert class polynomial H_-163
Elliptic Curve defined by y^2 = x^3 + 265977778*x + 120868502 over Finite Field of size 1000041437
verbose 2 (...: ell_finite_field.py, EllipticCurve_with_prime_order) Computing the Hilbert class polynomial H_-667
Elliptic Curve defined by y^2 = x^3 + 689795416*x + 188156157 over Finite Field of size 999969307
Elliptic Curve defined by y^2 = x^3 + 999178436*x + 900579394 over Finite Field of size 999969307
>>> set_verbose(Integer(4))
>>> set_random_seed(Integer(1337))
>>> for _, E in zip(range(Integer(3)), EllipticCurve_with_prime_order(Integer(10)**Integer(9) + Integer(7))):
...     print(E)
verbose 4 (...: ell_finite_field.py, EllipticCurve_with_prime_order) Testing D=-19
...
verbose 4 (...: ell_finite_field.py, EllipticCurve_with_prime_order) Testing D=-163
verbose 2 (...: ell_finite_field.py, EllipticCurve_with_prime_order) Computing the Hilbert class polynomial H_-163
Elliptic Curve defined by y^2 = x^3 + 265977778*x + 120868502 over Finite Field of size 1000041437
verbose 4 (...: ell_finite_field.py, EllipticCurve_with_prime_order) Testing D=-179
...
verbose 4 (...: ell_finite_field.py, EllipticCurve_with_prime_order) Testing D=-667
verbose 2 (...: ell_finite_field.py, EllipticCurve_with_prime_order) Computing the Hilbert class polynomial H_-667
Elliptic Curve defined by y^2 = x^3 + 689795416*x + 188156157 over Finite Field of size 999969307
Elliptic Curve defined by y^2 = x^3 + 999178436*x + 900579394 over Finite Field of size 999969307

Sage Live

from sage.misc.verbose import set_verbose
set_random_seed(1337)  # as the function returns random twists of curves
for _, E in zip(range(3), EllipticCurve_with_prime_order(10^9 + 7)):
    print(E)
set_verbose(2)
set_random_seed(1337)
for _, E in zip(range(3), EllipticCurve_with_prime_order(10^9 + 7)):
    print(E)
set_verbose(4)
set_random_seed(1337)
for _, E in zip(range(3), EllipticCurve_with_prime_order(10^9 + 7)):
    print(E)

AUTHORS:

Martin Grenouilloux, Gareth Ma (2024-09): initial implementation

sage.schemes.elliptic_curves.ell_finite_field.curves_with_j_0(K)[source]¶

Return a complete list of pairwise nonisomorphic elliptic curves with \(j\)-invariant 0 over the finite field \(K\).

Note

In characteristics 2 and 3 this function simply calls curves_with_j_0_char2 or curves_with_j_0_char3. Otherwise there are either 2 or 6 curves, parametrised by \(K^*/(K^*)^6\).

Examples:

For \(K=\GF{q}\) where \(q\equiv1\mod{6}\) there are six curves, the sextic twists of \(y^2=x^3+1\):

Sage

sage: # needs sage.rings.finite_rings
sage: from sage.schemes.elliptic_curves.ell_finite_field import curves_with_j_0
sage: sorted(curves_with_j_0(GF(7)), key = lambda E: E.a_invariants())
[Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 7,
 Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field of size 7,
 Elliptic Curve defined by y^2 = x^3 + 3 over Finite Field of size 7,
 Elliptic Curve defined by y^2 = x^3 + 4 over Finite Field of size 7,
 Elliptic Curve defined by y^2 = x^3 + 5 over Finite Field of size 7,
 Elliptic Curve defined by y^2 = x^3 + 6 over Finite Field of size 7]
sage: curves = curves_with_j_0(GF(25)); len(curves)
6
sage: all(not curves[i].is_isomorphic(curves[j]) for i in range(6) for j in range(i + 1, 6))
True
sage: set(E.j_invariant() for E in curves)
{0}

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> from sage.schemes.elliptic_curves.ell_finite_field import curves_with_j_0
>>> sorted(curves_with_j_0(GF(Integer(7))), key = lambda E: E.a_invariants())
[Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 7,
 Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field of size 7,
 Elliptic Curve defined by y^2 = x^3 + 3 over Finite Field of size 7,
 Elliptic Curve defined by y^2 = x^3 + 4 over Finite Field of size 7,
 Elliptic Curve defined by y^2 = x^3 + 5 over Finite Field of size 7,
 Elliptic Curve defined by y^2 = x^3 + 6 over Finite Field of size 7]
>>> curves = curves_with_j_0(GF(Integer(25))); len(curves)
6
>>> all(not curves[i].is_isomorphic(curves[j]) for i in range(Integer(6)) for j in range(i + Integer(1), Integer(6)))
True
>>> set(E.j_invariant() for E in curves)
{0}

Sage Live

# needs sage.rings.finite_rings
from sage.schemes.elliptic_curves.ell_finite_field import curves_with_j_0
sorted(curves_with_j_0(GF(7)), key = lambda E: E.a_invariants())
curves = curves_with_j_0(GF(25)); len(curves)
all(not curves[i].is_isomorphic(curves[j]) for i in range(6) for j in range(i + 1, 6))
set(E.j_invariant() for E in curves)

For \(K=\GF{q}\) where \(q\equiv5\mod{6}\) there are two curves, quadratic twists of each other by \(-3\): \(y^2=x^3+1\) and \(y^2=x^3-27\):

Sage

sage: from sage.schemes.elliptic_curves.ell_finite_field import curves_with_j_0
sage: curves_with_j_0(GF(5))
[Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 5,
 Elliptic Curve defined by y^2 = x^3 + 3 over Finite Field of size 5]
sage: curves_with_j_0(GF(11))
[Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 11,
 Elliptic Curve defined by y^2 = x^3 + 6 over Finite Field of size 11]

Python

>>> from sage.all import *
>>> from sage.schemes.elliptic_curves.ell_finite_field import curves_with_j_0
>>> curves_with_j_0(GF(Integer(5)))
[Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 5,
 Elliptic Curve defined by y^2 = x^3 + 3 over Finite Field of size 5]
>>> curves_with_j_0(GF(Integer(11)))
[Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 11,
 Elliptic Curve defined by y^2 = x^3 + 6 over Finite Field of size 11]

Sage Live

from sage.schemes.elliptic_curves.ell_finite_field import curves_with_j_0
curves_with_j_0(GF(5))
curves_with_j_0(GF(11))

sage.schemes.elliptic_curves.ell_finite_field.curves_with_j_0_char2(K)[source]¶

Return a complete list of pairwise nonisomorphic elliptic curves with \(j\)-invariant 0 over the finite field \(K\) of characteristic 2.

Note

The number of twists is either 3 or 7 depending on whether the field has odd or even degree over \(\GF{2}\). See [Connell1999], pages 429-431.

Examples:

In odd degree, there are three isomorphism classes all with representatives defined over \(\GF{2}\):

Sage

sage: from sage.schemes.elliptic_curves.ell_finite_field import curves_with_j_0_char2
sage: # needs sage.rings.finite_rings
sage: K = GF(2**7)
sage: curves = curves_with_j_0_char2(K)
sage: len(curves)
3
sage: [E.ainvs() for E in curves]
[(0, 0, 1, 0, 0), (0, 0, 1, 1, 0), (0, 0, 1, 1, 1)]

Python

>>> from sage.all import *
>>> from sage.schemes.elliptic_curves.ell_finite_field import curves_with_j_0_char2
>>> # needs sage.rings.finite_rings
>>> K = GF(Integer(2)**Integer(7))
>>> curves = curves_with_j_0_char2(K)
>>> len(curves)
3
>>> [E.ainvs() for E in curves]
[(0, 0, 1, 0, 0), (0, 0, 1, 1, 0), (0, 0, 1, 1, 1)]

Sage Live

from sage.schemes.elliptic_curves.ell_finite_field import curves_with_j_0_char2
# needs sage.rings.finite_rings
K = GF(2**7)
curves = curves_with_j_0_char2(K)
len(curves)
[E.ainvs() for E in curves]

Check that the curves are mutually non-isomorphic:

Sage

sage: all((e1 == e2 or not e1.is_isomorphic(e2))                                # needs sage.rings.finite_rings
....:     for e1 in curves for e2 in curves)
True

Python

>>> from sage.all import *
>>> all((e1 == e2 or not e1.is_isomorphic(e2))                                # needs sage.rings.finite_rings
...     for e1 in curves for e2 in curves)
True

Sage Live

all((e1 == e2 or not e1.is_isomorphic(e2))                                # needs sage.rings.finite_rings
    for e1 in curves for e2 in curves)

Check that the weight formula holds:

Sage

sage: sum(1/len(E.automorphisms()) for E in curves) == 1                        # needs sage.rings.finite_rings
True

Python

>>> from sage.all import *
>>> sum(Integer(1)/len(E.automorphisms()) for E in curves) == Integer(1)                        # needs sage.rings.finite_rings
True

Sage Live

sum(1/len(E.automorphisms()) for E in curves) == 1                        # needs sage.rings.finite_rings

In even degree there are seven isomorphism classes:

Sage

sage: from sage.schemes.elliptic_curves.ell_finite_field import curves_with_j_0_char2
sage: # needs sage.rings.finite_rings
sage: K = GF(2**8)
sage: curves = EllipticCurve(j=K(0)).twists()
sage: len(curves)
7
sage: [E.ainvs() for E in curves] # random
[(0, 0, 1, 0, 0),
 (0, 0, 1, 0, z8^5 + z8^4 + z8^3),
 (0, 0, 1, z8^6 + z8^5 + z8^2 + 1, 0),
 (0, 0, z8^4 + z8^3 + z8^2 + 1, 0, 0),
 (0, 0, z8^4 + z8^3 + z8^2 + 1, 0, z8^3 + z8^2 + 1),
 (0, 0, z8^6 + z8^3 + z8^2, 0, 0),
 (0, 0, z8^6 + z8^3 + z8^2, 0, z8^3 + z8^2)]

Python

>>> from sage.all import *
>>> from sage.schemes.elliptic_curves.ell_finite_field import curves_with_j_0_char2
>>> # needs sage.rings.finite_rings
>>> K = GF(Integer(2)**Integer(8))
>>> curves = EllipticCurve(j=K(Integer(0))).twists()
>>> len(curves)
7
>>> [E.ainvs() for E in curves] # random
[(0, 0, 1, 0, 0),
 (0, 0, 1, 0, z8^5 + z8^4 + z8^3),
 (0, 0, 1, z8^6 + z8^5 + z8^2 + 1, 0),
 (0, 0, z8^4 + z8^3 + z8^2 + 1, 0, 0),
 (0, 0, z8^4 + z8^3 + z8^2 + 1, 0, z8^3 + z8^2 + 1),
 (0, 0, z8^6 + z8^3 + z8^2, 0, 0),
 (0, 0, z8^6 + z8^3 + z8^2, 0, z8^3 + z8^2)]

Sage Live

from sage.schemes.elliptic_curves.ell_finite_field import curves_with_j_0_char2
# needs sage.rings.finite_rings
K = GF(2**8)
curves = EllipticCurve(j=K(0)).twists()
len(curves)
[E.ainvs() for E in curves] # random

Check that the twists are mutually non-isomorphic:

Sage

sage: all((e1 == e2 or not e1.is_isomorphic(e2))                                # needs sage.rings.finite_rings
....:     for e1 in curves for e2 in curves)
True

Python

>>> from sage.all import *
>>> all((e1 == e2 or not e1.is_isomorphic(e2))                                # needs sage.rings.finite_rings
...     for e1 in curves for e2 in curves)
True

Sage Live

all((e1 == e2 or not e1.is_isomorphic(e2))                                # needs sage.rings.finite_rings
    for e1 in curves for e2 in curves)

Check that the weight formula holds:

Sage

sage: sum(1/len(E.automorphisms()) for E in curves) == 1                        # needs sage.rings.finite_rings
True

Python

>>> from sage.all import *
>>> sum(Integer(1)/len(E.automorphisms()) for E in curves) == Integer(1)                        # needs sage.rings.finite_rings
True

Sage Live

sum(1/len(E.automorphisms()) for E in curves) == 1                        # needs sage.rings.finite_rings

sage.schemes.elliptic_curves.ell_finite_field.curves_with_j_0_char3(K)[source]¶

Return a complete list of pairwise nonisomorphic elliptic curves with \(j\)-invariant 0 over the finite field \(K\) of characteristic 3.

Note

The number of twists is either 4 or 6 depending on whether the field has odd or even degree over \(\GF{3}\). See [Connell1999], pages 429-431.

Examples:

In odd degree, there are four isomorphism classes:

Sage

sage: from sage.schemes.elliptic_curves.ell_finite_field import curves_with_j_0_char3
sage: # needs sage.rings.finite_rings
sage: K = GF(3**5)
sage: curves = curves_with_j_0_char3(K)
sage: len(curves)
4
sage: [E.ainvs() for E in curves] # random
[(0, 0, 0, 1, 0),
 (0, 0, 0, 2, 0),
 (0, 0, 0, 2, z5^4 + z5^3 + z5^2),
 (0, 0, 0, 2, 2*z5^4 + 2*z5^3 + 2*z5^2)]

Python

>>> from sage.all import *
>>> from sage.schemes.elliptic_curves.ell_finite_field import curves_with_j_0_char3
>>> # needs sage.rings.finite_rings
>>> K = GF(Integer(3)**Integer(5))
>>> curves = curves_with_j_0_char3(K)
>>> len(curves)
4
>>> [E.ainvs() for E in curves] # random
[(0, 0, 0, 1, 0),
 (0, 0, 0, 2, 0),
 (0, 0, 0, 2, z5^4 + z5^3 + z5^2),
 (0, 0, 0, 2, 2*z5^4 + 2*z5^3 + 2*z5^2)]

Sage Live

from sage.schemes.elliptic_curves.ell_finite_field import curves_with_j_0_char3
# needs sage.rings.finite_rings
K = GF(3**5)
curves = curves_with_j_0_char3(K)
len(curves)
[E.ainvs() for E in curves] # random

Check that the twists are mutually non-isomorphic:

Sage

sage: all((e1 == e2 or not e1.is_isomorphic(e2))                                # needs sage.rings.finite_rings
....:     for e1 in curves for e2 in curves)
True

Python

>>> from sage.all import *
>>> all((e1 == e2 or not e1.is_isomorphic(e2))                                # needs sage.rings.finite_rings
...     for e1 in curves for e2 in curves)
True

Sage Live

all((e1 == e2 or not e1.is_isomorphic(e2))                                # needs sage.rings.finite_rings
    for e1 in curves for e2 in curves)

Check that the weight formula holds:

Sage

sage: sum(1/len(E.automorphisms()) for E in curves) == 1                        # needs sage.rings.finite_rings
True

Python

>>> from sage.all import *
>>> sum(Integer(1)/len(E.automorphisms()) for E in curves) == Integer(1)                        # needs sage.rings.finite_rings
True

Sage Live

sum(1/len(E.automorphisms()) for E in curves) == 1                        # needs sage.rings.finite_rings

In even degree, there are six isomorphism classes:

Sage

sage: from sage.schemes.elliptic_curves.ell_finite_field import curves_with_j_0_char3
sage: # needs sage.rings.finite_rings
sage: K = GF(3**4)
sage: curves = EllipticCurve(j=K(0)).twists()
sage: len(curves)
6
sage: [E.ainvs() for E in curves] # random
[(0, 0, 0, 1, 0),
 (0, 0, 0, 2, 2*z4^3 + 2*z4^2 + 2*z4 + 2),
 (0, 0, 0, 1, 0),
 (0, 0, 0, 1, 2*z4^3 + 2*z4^2 + 2*z4 + 2),
 (0, 0, 0, z4, 0),
 (0, 0, 0, z4^3, 0)]

Python

>>> from sage.all import *
>>> from sage.schemes.elliptic_curves.ell_finite_field import curves_with_j_0_char3
>>> # needs sage.rings.finite_rings
>>> K = GF(Integer(3)**Integer(4))
>>> curves = EllipticCurve(j=K(Integer(0))).twists()
>>> len(curves)
6
>>> [E.ainvs() for E in curves] # random
[(0, 0, 0, 1, 0),
 (0, 0, 0, 2, 2*z4^3 + 2*z4^2 + 2*z4 + 2),
 (0, 0, 0, 1, 0),
 (0, 0, 0, 1, 2*z4^3 + 2*z4^2 + 2*z4 + 2),
 (0, 0, 0, z4, 0),
 (0, 0, 0, z4^3, 0)]

Sage Live

from sage.schemes.elliptic_curves.ell_finite_field import curves_with_j_0_char3
# needs sage.rings.finite_rings
K = GF(3**4)
curves = EllipticCurve(j=K(0)).twists()
len(curves)
[E.ainvs() for E in curves] # random

Check that the twists are mutually non-isomorphic:

Sage

sage: all((e1 == e2 or not e1.is_isomorphic(e2))                                # needs sage.rings.finite_rings
....:     for e1 in curves for e2 in curves)
True

Python

>>> from sage.all import *
>>> all((e1 == e2 or not e1.is_isomorphic(e2))                                # needs sage.rings.finite_rings
...     for e1 in curves for e2 in curves)
True

Sage Live

all((e1 == e2 or not e1.is_isomorphic(e2))                                # needs sage.rings.finite_rings
    for e1 in curves for e2 in curves)

Check that the weight formula holds:

Sage

sage: sum(1/len(E.automorphisms()) for E in curves) == 1                        # needs sage.rings.finite_rings
True

Python

>>> from sage.all import *
>>> sum(Integer(1)/len(E.automorphisms()) for E in curves) == Integer(1)                        # needs sage.rings.finite_rings
True

Sage Live

sum(1/len(E.automorphisms()) for E in curves) == 1                        # needs sage.rings.finite_rings

sage.schemes.elliptic_curves.ell_finite_field.curves_with_j_1728(K)[source]¶

Return a complete list of pairwise nonisomorphic elliptic curves with \(j\)-invariant 1728 over the finite field \(K\).

Note

In characteristics 2 and 3 (so 0=1728) this function simply calls curves_with_j_0_char2 or curves_with_j_0_char3. Otherwise there are either 2 or 4 curves, parametrised by \(K^*/(K^*)^4\).

EXAMPLES:

For \(K=\GF{q}\) where \(q\equiv1\mod{4}\), there are four curves, the quartic twists of \(y^2=x^3+x\):

Sage

sage: from sage.schemes.elliptic_curves.ell_finite_field import curves_with_j_1728
sage: sorted(curves_with_j_1728(GF(5)), key = lambda E: E.a_invariants())
[Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 5,
 Elliptic Curve defined by y^2 = x^3 + 2*x over Finite Field of size 5,
 Elliptic Curve defined by y^2 = x^3 + 3*x over Finite Field of size 5,
 Elliptic Curve defined by y^2 = x^3 + 4*x over Finite Field of size 5]
sage: curves_with_j_1728(GF(49))  # random                                      # needs sage.rings.finite_rings
[Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 7^2,
 Elliptic Curve defined by y^2 = x^3 + z2*x over Finite Field in z2 of size 7^2,
 Elliptic Curve defined by y^2 = x^3 + (z2+4)*x over Finite Field in z2 of size 7^2,
 Elliptic Curve defined by y^2 = x^3 + (5*z2+4)*x over Finite Field in z2 of size 7^2]

Python

>>> from sage.all import *
>>> from sage.schemes.elliptic_curves.ell_finite_field import curves_with_j_1728
>>> sorted(curves_with_j_1728(GF(Integer(5))), key = lambda E: E.a_invariants())
[Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 5,
 Elliptic Curve defined by y^2 = x^3 + 2*x over Finite Field of size 5,
 Elliptic Curve defined by y^2 = x^3 + 3*x over Finite Field of size 5,
 Elliptic Curve defined by y^2 = x^3 + 4*x over Finite Field of size 5]
>>> curves_with_j_1728(GF(Integer(49)))  # random                                      # needs sage.rings.finite_rings
[Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 7^2,
 Elliptic Curve defined by y^2 = x^3 + z2*x over Finite Field in z2 of size 7^2,
 Elliptic Curve defined by y^2 = x^3 + (z2+4)*x over Finite Field in z2 of size 7^2,
 Elliptic Curve defined by y^2 = x^3 + (5*z2+4)*x over Finite Field in z2 of size 7^2]

Sage Live

from sage.schemes.elliptic_curves.ell_finite_field import curves_with_j_1728
sorted(curves_with_j_1728(GF(5)), key = lambda E: E.a_invariants())
curves_with_j_1728(GF(49))  # random                                      # needs sage.rings.finite_rings

For \(K=\GF{q}\) where \(q\equiv3\mod{4}\), there are two curves, quadratic twists of each other by \(-1\): \(y^2=x^3+x\) and \(y^2=x^3-x\):

Sage

sage: from sage.schemes.elliptic_curves.ell_finite_field import curves_with_j_1728
sage: curves_with_j_1728(GF(7))
[Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 7,
 Elliptic Curve defined by y^2 = x^3 + 6*x over Finite Field of size 7]
sage: curves_with_j_1728(GF(11))
[Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 11,
 Elliptic Curve defined by y^2 = x^3 + 10*x over Finite Field of size 11]

Python

>>> from sage.all import *
>>> from sage.schemes.elliptic_curves.ell_finite_field import curves_with_j_1728
>>> curves_with_j_1728(GF(Integer(7)))
[Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 7,
 Elliptic Curve defined by y^2 = x^3 + 6*x over Finite Field of size 7]
>>> curves_with_j_1728(GF(Integer(11)))
[Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 11,
 Elliptic Curve defined by y^2 = x^3 + 10*x over Finite Field of size 11]

Sage Live

from sage.schemes.elliptic_curves.ell_finite_field import curves_with_j_1728
curves_with_j_1728(GF(7))
curves_with_j_1728(GF(11))

sage.schemes.elliptic_curves.ell_finite_field.fill_ss_j_dict()[source]¶

Fill the global cache of supersingular j-_polynomials.

This function does nothing except the first time it is called, when it fills supersingular_j_polynomials with precomputed values for \(p<300\). Setting the values this way avoids start-up costs.

sage.schemes.elliptic_curves.ell_finite_field.is_j_supersingular(j, proof=True)[source]¶

Return True if \(j\) is a supersingular \(j\)-invariant.

INPUT:

j – finite field element
proof– boolean (default: True); if True, returns a proved result. If False, then a return value of False is certain but a return value of True may be based on a probabilistic test. See the ALGORITHM section below for more details.

OUTPUT: boolean; True if \(j\) is supersingular, else False

ALGORITHM:

For small characteristics \(p\) we check whether the \(j\)-invariant is in a precomputed list of supersingular values. Otherwise we next check the \(j\)-invariant. If \(j=0\), the curve is supersingular if and only if \(p=2\) or \(p\equiv3\pmod{4}\); if \(j=1728\), the curve is supersingular if and only if \(p=3\) or \(p\equiv2\pmod{3}\). Next, if the base field is the prime field \({\rm GF}(p)\), we check that \((p+1)P=0\) for several random points \(P\), returning False if any fail: supersingular curves over \({\rm GF}(p)\) have cardinality \(p+1\). If Proof is false we now return True. Otherwise we compute the cardinality and return True if and only if it is divisible by \(p\).

EXAMPLES:

Sage

sage: from sage.schemes.elliptic_curves.ell_finite_field import is_j_supersingular, supersingular_j_polynomials
sage: [(p,[j for j in GF(p) if is_j_supersingular(j)]) for p in prime_range(30)]
[(2, [0]), (3, [0]), (5, [0]), (7, [6]), (11, [0, 1]), (13, [5]),
 (17, [0, 8]), (19, [7, 18]), (23, [0, 3, 19]), (29, [0, 2, 25])]

sage: [j for j in GF(109) if is_j_supersingular(j)]
[17, 41, 43]
sage: PolynomialRing(GF(109),'j')(supersingular_j_polynomials[109]).roots()
[(43, 1), (41, 1), (17, 1)]

sage: [p for p in prime_range(100) if is_j_supersingular(GF(p)(0))]
[2, 3, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89]
sage: [p for p in prime_range(100) if is_j_supersingular(GF(p)(1728))]
[2, 3, 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, 79, 83]
sage: [p for p in prime_range(100) if is_j_supersingular(GF(p)(123456))]
[2, 3, 59, 89]

Python

>>> from sage.all import *
>>> from sage.schemes.elliptic_curves.ell_finite_field import is_j_supersingular, supersingular_j_polynomials
>>> [(p,[j for j in GF(p) if is_j_supersingular(j)]) for p in prime_range(Integer(30))]
[(2, [0]), (3, [0]), (5, [0]), (7, [6]), (11, [0, 1]), (13, [5]),
 (17, [0, 8]), (19, [7, 18]), (23, [0, 3, 19]), (29, [0, 2, 25])]

>>> [j for j in GF(Integer(109)) if is_j_supersingular(j)]
[17, 41, 43]
>>> PolynomialRing(GF(Integer(109)),'j')(supersingular_j_polynomials[Integer(109)]).roots()
[(43, 1), (41, 1), (17, 1)]

>>> [p for p in prime_range(Integer(100)) if is_j_supersingular(GF(p)(Integer(0)))]
[2, 3, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89]
>>> [p for p in prime_range(Integer(100)) if is_j_supersingular(GF(p)(Integer(1728)))]
[2, 3, 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, 79, 83]
>>> [p for p in prime_range(Integer(100)) if is_j_supersingular(GF(p)(Integer(123456)))]
[2, 3, 59, 89]

Sage Live

from sage.schemes.elliptic_curves.ell_finite_field import is_j_supersingular, supersingular_j_polynomials
[(p,[j for j in GF(p) if is_j_supersingular(j)]) for p in prime_range(30)]
[j for j in GF(109) if is_j_supersingular(j)]
PolynomialRing(GF(109),'j')(supersingular_j_polynomials[109]).roots()
[p for p in prime_range(100) if is_j_supersingular(GF(p)(0))]
[p for p in prime_range(100) if is_j_supersingular(GF(p)(1728))]
[p for p in prime_range(100) if is_j_supersingular(GF(p)(123456))]

sage.schemes.elliptic_curves.ell_finite_field.special_supersingular_curve(F, q, endomorphism=None)[source]¶

Given a finite field F of characteristic \(p\), and optionally a positive integer \(q\) such that the Hilbert conductor of \(-q\) and \(-p\) equals \(p\), construct a “special” supersingular elliptic curve \(E\) defined over F.

Such a curve

has coefficients in \(\mathbb F_p\);
has group structure \(E(\mathbb F_p) \cong \ZZ/(p+1)\) and \(E(\mathbb F_{p^2}) \cong \ZZ/(p+1) \times \ZZ/(p+1)\);
has an endomorphism \(\vartheta\) of degree \(q\) that anticommutes with the \(\mathbb F_p\)-Frobenius on \(E\).

(The significance of \(\vartheta\) is that any such endomorphism, together with the \(\mathbb F_p\)-Frobenius, generates the endomorphism algebra \(\mathrm{End}(E) \otimes \QQ\).)

The complexity grows exponentially in \(\log(q)\). Automatically chosen values of \(q\) lie in \(O((\log p)^2)\) assuming GRH.

INPUT:

F – finite field \(\mathbb F_{p^r}\)
q – positive integer (optional, default None)
endomorphism – boolean (default: False); when set to True, it is required that \(2 \mid r\), and the function then additionally returns \(\vartheta\)

Warning

Due to Issue #38481, calling this function with a value of \(q\) larger than approximately \(p/4\) may currently fail. This failure will not occur for automatically chosen values of \(q\).

EXAMPLES:

Sage

sage: special_supersingular_curve(GF(1013^2), endomorphism=True)
(Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in z2 of size 1013^2,
 Isogeny of degree 3 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in z2 of size 1013^2 to Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in z2 of size 1013^2)

sage: special_supersingular_curve(GF(1019^2), endomorphism=True)
(Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 1019^2,
 Elliptic-curve endomorphism of Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 1019^2
   Via:  (u,r,s,t) = (389*z2 + 241, 0, 0, 0))

sage: special_supersingular_curve(GF(1021^2), endomorphism=True)
(Elliptic Curve defined by y^2 = x^3 + 791*x + 230 over Finite Field in z2 of size 1021^2,
 Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + 791*x + 230 over Finite Field in z2 of size 1021^2 to Elliptic Curve defined by y^2 = x^3 + 791*x + 230 over Finite Field in z2 of size 1021^2)

sage: special_supersingular_curve(GF(1031^2), endomorphism=True)
(Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 1031^2,
 Elliptic-curve endomorphism of Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 1031^2
   Via:  (u,r,s,t) = (747*z2 + 284, 0, 0, 0))

sage: special_supersingular_curve(GF(1033^2), endomorphism=True)
(Elliptic Curve defined by y^2 = x^3 + 53*x + 980 over Finite Field in z2 of size 1033^2,
 Isogeny of degree 11 from Elliptic Curve defined by y^2 = x^3 + 53*x + 980 over Finite Field in z2 of size 1033^2 to Elliptic Curve defined by y^2 = x^3 + 53*x + 980 over Finite Field in z2 of size 1033^2)

sage: special_supersingular_curve(GF(1039^2), endomorphism=True)
(Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 1039^2,
 Elliptic-curve endomorphism of Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 1039^2
   Via:  (u,r,s,t) = (626*z2 + 200, 0, 0, 0))

sage: special_supersingular_curve(GF(1049^2), endomorphism=True)
(Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in z2 of size 1049^2,
 Isogeny of degree 3 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in z2 of size 1049^2 to Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in z2 of size 1049^2)

sage: special_supersingular_curve(GF(1051^2), endomorphism=True)
(Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 1051^2,
 Elliptic-curve endomorphism of Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 1051^2
   Via:  (u,r,s,t) = (922*z2 + 129, 0, 0, 0))

Python

>>> from sage.all import *
>>> special_supersingular_curve(GF(Integer(1013)**Integer(2)), endomorphism=True)
(Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in z2 of size 1013^2,
 Isogeny of degree 3 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in z2 of size 1013^2 to Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in z2 of size 1013^2)

>>> special_supersingular_curve(GF(Integer(1019)**Integer(2)), endomorphism=True)
(Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 1019^2,
 Elliptic-curve endomorphism of Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 1019^2
   Via:  (u,r,s,t) = (389*z2 + 241, 0, 0, 0))

>>> special_supersingular_curve(GF(Integer(1021)**Integer(2)), endomorphism=True)
(Elliptic Curve defined by y^2 = x^3 + 791*x + 230 over Finite Field in z2 of size 1021^2,
 Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + 791*x + 230 over Finite Field in z2 of size 1021^2 to Elliptic Curve defined by y^2 = x^3 + 791*x + 230 over Finite Field in z2 of size 1021^2)

>>> special_supersingular_curve(GF(Integer(1031)**Integer(2)), endomorphism=True)
(Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 1031^2,
 Elliptic-curve endomorphism of Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 1031^2
   Via:  (u,r,s,t) = (747*z2 + 284, 0, 0, 0))

>>> special_supersingular_curve(GF(Integer(1033)**Integer(2)), endomorphism=True)
(Elliptic Curve defined by y^2 = x^3 + 53*x + 980 over Finite Field in z2 of size 1033^2,
 Isogeny of degree 11 from Elliptic Curve defined by y^2 = x^3 + 53*x + 980 over Finite Field in z2 of size 1033^2 to Elliptic Curve defined by y^2 = x^3 + 53*x + 980 over Finite Field in z2 of size 1033^2)

>>> special_supersingular_curve(GF(Integer(1039)**Integer(2)), endomorphism=True)
(Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 1039^2,
 Elliptic-curve endomorphism of Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 1039^2
   Via:  (u,r,s,t) = (626*z2 + 200, 0, 0, 0))

>>> special_supersingular_curve(GF(Integer(1049)**Integer(2)), endomorphism=True)
(Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in z2 of size 1049^2,
 Isogeny of degree 3 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in z2 of size 1049^2 to Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in z2 of size 1049^2)

>>> special_supersingular_curve(GF(Integer(1051)**Integer(2)), endomorphism=True)
(Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 1051^2,
 Elliptic-curve endomorphism of Elliptic Curve defined by y^2 = x^3 + x over Finite Field in z2 of size 1051^2
   Via:  (u,r,s,t) = (922*z2 + 129, 0, 0, 0))

Sage Live

special_supersingular_curve(GF(1013^2), endomorphism=True)
special_supersingular_curve(GF(1019^2), endomorphism=True)
special_supersingular_curve(GF(1021^2), endomorphism=True)
special_supersingular_curve(GF(1031^2), endomorphism=True)
special_supersingular_curve(GF(1033^2), endomorphism=True)
special_supersingular_curve(GF(1039^2), endomorphism=True)
special_supersingular_curve(GF(1049^2), endomorphism=True)
special_supersingular_curve(GF(1051^2), endomorphism=True)

We can also supply a suitable value of \(q\) ourselves:

Sage

sage: special_supersingular_curve(GF(1019), q=99)
Elliptic Curve defined by y^2 = x^3 + 211*x + 808 over Finite Field of size 1019

sage: special_supersingular_curve(GF(1019^2), q=99, endomorphism=True)
(Elliptic Curve defined by y^2 = x^3 + 211*x + 808 over Finite Field in z2 of size 1019^2,
 Isogeny of degree 99 from Elliptic Curve defined by y^2 = x^3 + 211*x + 808 over Finite Field in z2 of size 1019^2 to Elliptic Curve defined by y^2 = x^3 + 211*x + 808 over Finite Field in z2 of size 1019^2)

sage: special_supersingular_curve(GF(1013), q=99)
Traceback (most recent call last):
...
ValueError: invalid choice of q

Python

>>> from sage.all import *
>>> special_supersingular_curve(GF(Integer(1019)), q=Integer(99))
Elliptic Curve defined by y^2 = x^3 + 211*x + 808 over Finite Field of size 1019

>>> special_supersingular_curve(GF(Integer(1019)**Integer(2)), q=Integer(99), endomorphism=True)
(Elliptic Curve defined by y^2 = x^3 + 211*x + 808 over Finite Field in z2 of size 1019^2,
 Isogeny of degree 99 from Elliptic Curve defined by y^2 = x^3 + 211*x + 808 over Finite Field in z2 of size 1019^2 to Elliptic Curve defined by y^2 = x^3 + 211*x + 808 over Finite Field in z2 of size 1019^2)

>>> special_supersingular_curve(GF(Integer(1013)), q=Integer(99))
Traceback (most recent call last):
...
ValueError: invalid choice of q

Sage Live

special_supersingular_curve(GF(1019), q=99)
special_supersingular_curve(GF(1019^2), q=99, endomorphism=True)
special_supersingular_curve(GF(1013), q=99)

Note

This function makes no guarantees about the distribution of the output. The current implementation is deterministic in many cases.

ALGORITHM: [Bro2009], Algorithm 2.4

sage.schemes.elliptic_curves.ell_finite_field.supersingular_j_polynomial(p, use_cache=True)[source]¶

Return a polynomial whose roots are the supersingular \(j\)-invariants in characteristic \(p\), other than 0, 1728.

INPUT:

p – integer; a prime number
use_cache – boolean (default: True); use cached coefficients if they exist

ALGORITHM:

First compute H(X) whose roots are the Legendre \(\lambda\)-invariants of supersingular curves (Silverman V.4.1(b)) in characteristic \(p\). Then, using a resultant computation with the polynomial relating \(\lambda\) and \(j\) (Silverman III.1.7(b)), we recover the polynomial (in variable j) whose roots are the \(j\)-invariants. Factors of \(j\) and \(j-1728\) are removed if present.

Note

The only point of the use_cache parameter is to allow checking the precomputed coefficients.

EXAMPLES:

Sage

sage: from sage.schemes.elliptic_curves.ell_finite_field import supersingular_j_polynomial
sage: f = supersingular_j_polynomial(67); f
j^5 + 53*j^4 + 4*j^3 + 47*j^2 + 36*j + 8
sage: f.factor()
(j + 1) * (j^2 + 8*j + 45) * (j^2 + 44*j + 24)

Python

>>> from sage.all import *
>>> from sage.schemes.elliptic_curves.ell_finite_field import supersingular_j_polynomial
>>> f = supersingular_j_polynomial(Integer(67)); f
j^5 + 53*j^4 + 4*j^3 + 47*j^2 + 36*j + 8
>>> f.factor()
(j + 1) * (j^2 + 8*j + 45) * (j^2 + 44*j + 24)

Sage Live

from sage.schemes.elliptic_curves.ell_finite_field import supersingular_j_polynomial
f = supersingular_j_polynomial(67); f
f.factor()

Sage

sage: [supersingular_j_polynomial(p) for p in prime_range(30)]
[1, 1, 1, 1, 1, j + 8, j + 9, j + 12, j + 4, j^2 + 2*j + 21]

Python

>>> from sage.all import *
>>> [supersingular_j_polynomial(p) for p in prime_range(Integer(30))]
[1, 1, 1, 1, 1, j + 8, j + 9, j + 12, j + 4, j^2 + 2*j + 21]

Sage Live

[supersingular_j_polynomial(p) for p in prime_range(30)]

Python

>>> from sage.all import *
>>> [supersingular_j_polynomial(p) for p in prime_range(Integer(30))]
[1, 1, 1, 1, 1, j + 8, j + 9, j + 12, j + 4, j^2 + 2*j + 21]

Sage Live

[supersingular_j_polynomial(p) for p in prime_range(30)]