Points on elliptic curves¶

The base class EllipticCurvePoint_field, derived from AdditiveGroupElement, provides support for points on elliptic curves defined over general fields. The derived classes EllipticCurvePoint_number_field and EllipticCurvePoint_finite_field provide further support for point on curves defined over number fields (including the rational field $\QQ$ ) and over finite fields. Although there is no special class for points over $\QQ$ , there is currently greater functionality implemented over $\QQ$ than over other number fields.

The class EllipticCurvePoint, which is based on SchemeMorphism_projective_coordinates_ring, currently has little extra functionality.

EXAMPLES:

An example over $\QQ$ :

sage: E = EllipticCurve('389a1')
sage: P = E(-1,1); P
(-1 : 1 : 1)
sage: Q = E(0,-1); Q
(0 : -1 : 1)
sage: P+Q
(4 : 8 : 1)
sage: P-Q
(1 : 0 : 1)
sage: 3*P-5*Q
(328/361 : -2800/6859 : 1)

An example over a number field:

sage: K.<i> = QuadraticField(-1)
sage: E = EllipticCurve(K,[1,0,0,0,-1])
sage: P = E(0,i); P
(0 : i : 1)
sage: P.order()
+Infinity
sage: 101*P-100*P==P
True

An example over a finite field:

sage: K.<a> = GF(101^3)
sage: E = EllipticCurve(K,[1,0,0,0,-1])
sage: P = E(40*a^2 + 69*a + 84 , 58*a^2 + 73*a + 45)
sage: P.order()
1032210
sage: E.cardinality()
1032210

Arithmetic with a point over an extension of a finite field:

sage: k.<a> = GF(5^2)
sage: E = EllipticCurve(k,[1,0]); E
Elliptic Curve defined by y^2 = x^3 + x over Finite Field in a of size 5^2
sage: P = E([a,2*a+4])
sage: 5*P
(2*a + 3 : 2*a : 1)
sage: P*5
(2*a + 3 : 2*a : 1)
sage: P + P + P + P + P
(2*a + 3 : 2*a : 1)

sage: F = Zmod(3)
sage: E = EllipticCurve(F,[1,0]);
sage: P = E([2,1])
sage: import sys
sage: n = sys.maxint
sage: P*(n+1)-P*n == P
True

Arithmetic over $\ZZ/N\ZZ$ with composite $N$ is supported. When an operation tries to invert a non-invertible element, a ZeroDivisoinError is raised and a factorization of the modulus appears in the error message:

sage: N = 1715761513
sage: E = EllipticCurve(Integers(N),[3,-13])
sage: P = E(2,1)
sage: LCM([2..60])*P
...
ZeroDivisionError: Inverse of 1520944668 does not exist (characteristic = 1715761513 = 26927*63719)

AUTHORS:

William Stein (2005) – Initial version
Robert Bradshaw et al....
John Cremona (Feb 2008) – Point counting and group structure for

non-prime fields, Frobenius endomorphism and order, elliptic logs
John Cremona (Aug 2008) – Introduced EllipticCurvePoint_number_field class
Tobias Nagel, Michael Mardaus, John Cremona (Dec 2008) – $p$ -adic elliptic logarithm over $\QQ$
David Hansen (Jan 2009) – Added weil_pairing function to EllipticCurvePoint_finite_field class

class sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint(X, v, check=True)¶

Bases: sage.schemes.generic.morphism.SchemeMorphism_projective_coordinates_ring

A point on an elliptic curve.

class sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_field(curve, v, check=True)¶

Bases: sage.structure.element.AdditiveGroupElement

A point on an elliptic curve over a field. The point has coordinates in the base field.

EXAMPLES:

sage: E = EllipticCurve('37a')
sage: E([0,0])
(0 : 0 : 1)
sage: E(0,0)               # brackets are optional
(0 : 0 : 1)
sage: E([GF(5)(0), 0])     # entries are coerced
(0 : 0 : 1)      

sage: E(0.000, 0)
(0 : 0 : 1)
 
sage: E(1,0,0)  
...
TypeError: Coordinates [1, 0, 0] do not define a point on
Elliptic Curve defined by y^2 + y = x^3 - x over Rational Field

sage: E = EllipticCurve([0,0,1,-1,0])
sage: S = E(QQ); S
Abelian group of points on Elliptic Curve defined by y^2 + y = x^3 - x over Rational Field

sage: K.<i>=NumberField(x^2+1)
sage: E=EllipticCurve(K,[0,1,0,-160,308])
sage: P=E(26,-120)
sage: Q=E(2+12*i,-36+48*i)
sage: P.order() == Q.order() == 4
True
sage: 2*P==2*Q
False

sage: K.<t>=FractionField(PolynomialRing(QQ,'t'))
sage: E=EllipticCurve([0,0,0,0,t^2])    
sage: P=E(0,t)
sage: P,2*P,3*P
((0 : t : 1), (0 : -t : 1), (0 : 1 : 0))

TESTS:

sage: loads(S.dumps()) == S
True
sage: E = EllipticCurve('37a')
sage: P = E(0,0); P
(0 : 0 : 1)
sage: loads(P.dumps()) == P
True
sage: T = 100*P
sage: loads(T.dumps()) == T
True

Test pickling an elliptic curve that has known points on it:

sage: e = EllipticCurve([0, 0, 1, -1, 0]); g = e.gens(); loads(dumps(e)) == e
True

additive_order()¶

Return the order of this point on the elliptic curve.

If the point is zero, returns 1, otherwise raise a NotImplementedError.

For curves over number fields and finite fields, see below.

Note

additive_order() is a synonym for order()

EXAMPLE:

sage: K.<t>=FractionField(PolynomialRing(QQ,'t'))
sage: E=EllipticCurve([0,0,0,-t^2,0])   
sage: P=E(t,0) 
sage: P.order()                                  
...
NotImplementedError: Computation of order of a point not implemented over general fields.
sage: E(0).additive_order()
1
sage: E(0).order() == 1
True

codomain()¶

Return the codomain of this point, which is the curve it is on. Synonymous with curve() which is perhaps more intuitive.

EXAMPLES:

sage: E=EllipticCurve(QQ,[1,1])
sage: P=E(0,1)
sage: P.domain()
Spectrum of Rational Field
sage: K.<a>=NumberField(x^2-3,'a')
sage: P=E.base_extend(K)(1,a)
sage: P.codomain()
Elliptic Curve defined by y^2 = x^3 + x + 1 over Number Field in a with defining polynomial x^2 - 3
sage: P.codomain() == P.curve()
True

curve()¶

Return the curve that this point is on.

EXAMPLES:

sage: E = EllipticCurve('389a')
sage: P = E([-1,1])
sage: P.curve()
Elliptic Curve defined by y^2 + y = x^3 + x^2 - 2*x over Rational Field

division_points(m, poly_only=False)¶

Return a list of all points $Q$ such that $mQ=P$ where $P$ = self.

Only points on the elliptic curve containing self and defined over the base field are included.

INPUT:

m – a positive integer
poly_only – bool (default: False); if True return polynomial whose roots give all possible $x$ -coordinates of $m$ -th roots of self.

OUTPUT:

(list) – a (possibly empty) list of solutions $Q$ to $mQ=P$ , where $P$ = self.

EXAMPLES:

We find the five 5-torsion points on an elliptic curve:

sage: E = EllipticCurve('11a'); E
Elliptic Curve defined by y^2 + y = x^3 - x^2 - 10*x - 20 over Rational Field
sage: P = E(0); P
(0 : 1 : 0)
sage: P.division_points(5)
[(0 : 1 : 0), (5 : -6 : 1), (5 : 5 : 1), (16 : -61 : 1), (16 : 60 : 1)]

Note above that 0 is included since [5]*0 = 0.

We create a curve of rank 1 with no torsion and do a consistency check:

sage: E = EllipticCurve('11a').quadratic_twist(-7)
sage: Q = E([44,-270])
sage: (4*Q).division_points(4)
[(44 : -270 : 1)]

We create a curve over a non-prime finite field with group of order $18$ :

sage: k.<a> = GF(25)
sage: E = EllipticCurve(k, [1,2+a,3,4*a,2])
sage: P = E([3,3*a+4])
sage: factor(E.order())
2 * 3^2
sage: P.order()
9

We find the $1$ -division points as a consistency check – there is just one, of course:

sage: P.division_points(1)
[(3 : 3*a + 4 : 1)]

The point $P$ has order coprime to 2 but divisible by 3, so:

sage: P.division_points(2)
[(2*a + 1 : 3*a + 4 : 1), (3*a + 1 : a : 1)]

We check that each of the 2-division points works as claimed:

sage: [2*Q for Q in P.division_points(2)]
[(3 : 3*a + 4 : 1), (3 : 3*a + 4 : 1)]

Some other checks:

sage: P.division_points(3)
[]
sage: P.division_points(4)
[(0 : 3*a + 2 : 1), (1 : 0 : 1)]
sage: P.division_points(5)
[(1 : 1 : 1)]

An example over a number field (see trac #3383):

sage: E = EllipticCurve('19a1')
sage: K.<t> = NumberField(x^9-3*x^8-4*x^7+16*x^6-3*x^5-21*x^4+5*x^3+7*x^2-7*x+1)
sage: EK = E.base_extend(K)
sage: E(0).division_points(3)
[(0 : 1 : 0), (5 : -10 : 1), (5 : 9 : 1)]
sage: EK(0).division_points(3)
[(0 : 1 : 0), (5 : 9 : 1), (5 : -10 : 1)]
sage: E(0).division_points(9) 
[(0 : 1 : 0), (5 : -10 : 1), (5 : 9 : 1)]
sage: EK(0).division_points(9)
[(0 : 1 : 0), (5 : 9 : 1), (5 : -10 : 1), (-150/121*t^8 + 414/121*t^7 + 1481/242*t^6 - 2382/121*t^5 - 103/242*t^4 + 629/22*t^3 - 367/242*t^2 - 1307/121*t + 625/121 : 35/484*t^8 - 133/242*t^7 + 445/242*t^6 - 799/242*t^5 + 373/484*t^4 + 113/22*t^3 - 2355/484*t^2 - 753/242*t + 1165/484 : 1), (-150/121*t^8 + 414/121*t^7 + 1481/242*t^6 - 2382/121*t^5 - 103/242*t^4 + 629/22*t^3 - 367/242*t^2 - 1307/121*t + 625/121 : -35/484*t^8 + 133/242*t^7 - 445/242*t^6 + 799/242*t^5 - 373/484*t^4 - 113/22*t^3 + 2355/484*t^2 + 753/242*t - 1649/484 : 1), (-1383/484*t^8 + 970/121*t^7 + 3159/242*t^6 - 5211/121*t^5 + 37/484*t^4 + 654/11*t^3 - 909/484*t^2 - 4831/242*t + 6791/484 : 927/121*t^8 - 5209/242*t^7 - 8187/242*t^6 + 27975/242*t^5 - 1147/242*t^4 - 1729/11*t^3 + 1566/121*t^2 + 12873/242*t - 10871/242 : 1), (-1383/484*t^8 + 970/121*t^7 + 3159/242*t^6 - 5211/121*t^5 + 37/484*t^4 + 654/11*t^3 - 909/484*t^2 - 4831/242*t + 6791/484 : -927/121*t^8 + 5209/242*t^7 + 8187/242*t^6 - 27975/242*t^5 + 1147/242*t^4 + 1729/11*t^3 - 1566/121*t^2 - 12873/242*t + 10629/242 : 1), (-4793/484*t^8 + 6791/242*t^7 + 10727/242*t^6 - 18301/121*t^5 + 2347/484*t^4 + 2293/11*t^3 - 7311/484*t^2 - 17239/242*t + 26767/484 : 30847/484*t^8 - 21789/121*t^7 - 34605/121*t^6 + 117164/121*t^5 - 10633/484*t^4 - 29437/22*t^3 + 39725/484*t^2 + 55428/121*t - 176909/484 : 1), (-4793/484*t^8 + 6791/242*t^7 + 10727/242*t^6 - 18301/121*t^5 + 2347/484*t^4 + 2293/11*t^3 - 7311/484*t^2 - 17239/242*t + 26767/484 : -30847/484*t^8 + 21789/121*t^7 + 34605/121*t^6 - 117164/121*t^5 + 10633/484*t^4 + 29437/22*t^3 - 39725/484*t^2 - 55428/121*t + 176425/484 : 1)]

domain()¶

Return the domain of this point, which is $Spec(F)$ where $F$ is the field of definition.

EXAMPLES:

sage: E=EllipticCurve(QQ,[1,1])
sage: P=E(0,1)
sage: P.domain()
Spectrum of Rational Field
sage: K.<a>=NumberField(x^2-3,'a')
sage: P=E.base_extend(K)(1,a)
sage: P.domain()
Spectrum of Number Field in a with defining polynomial x^2 - 3

has_finite_order()¶

Return True if this point has finite additive order as an element of the group of points on this curve.

For fields other than number fields and finite fields, this is NotImplemented unless self.is_zero().

EXAMPLES:

sage: K.<t>=FractionField(PolynomialRing(QQ,'t'))
sage: E=EllipticCurve([0,0,0,-t^2,0])   
sage: P = E(0)
sage: P.has_finite_order()
True
sage: P=E(t,0) 
sage: P.has_finite_order()                                  
...
NotImplementedError: Computation of order of a point not implemented over general fields.
sage: (2*P).is_zero()
True

has_infinite_order()¶

Return True if this point has infinite additive order as an element of the group of points on this curve.

For fields other than number fields and finite fields, this is NotImplemented unless self.is_zero().

EXAMPLES:

sage: K.<t>=FractionField(PolynomialRing(QQ,'t'))
sage: E=EllipticCurve([0,0,0,-t^2,0])   
sage: P = E(0)
sage: P.has_infinite_order()
False
sage: P=E(t,0) 
sage: P.has_infinite_order()                                  
...
NotImplementedError: Computation of order of a point not implemented over general fields.
sage: (2*P).is_zero()
True

is_divisible_by(m)¶

Return True if there exists a point $Q$ defined over the same field as self such that $mQ$ == self.

INPUT:

m – a positive integer.

OUTPUT:

(bool) – True if there is a solution, else False.

EXAMPLES:

sage: E = EllipticCurve('389a')
sage: Q = 5*E(0,0); Q
(-2739/1444 : -77033/54872 : 1)
sage: Q.is_divisible_by(4)
False
sage: Q.is_divisible_by(5)
True

is_finite_order()¶

Return True if this point has finite additive order as an element of the group of points on this curve.

For fields other than number fields and finite fields, this is NotImplemented unless self.is_zero().

EXAMPLES:

sage: K.<t>=FractionField(PolynomialRing(QQ,'t'))
sage: E=EllipticCurve([0,0,0,-t^2,0])   
sage: P = E(0)
sage: P.has_finite_order()
True
sage: P=E(t,0) 
sage: P.has_finite_order()                                  
...
NotImplementedError: Computation of order of a point not implemented over general fields.
sage: (2*P).is_zero()
True

order()¶

Return the order of this point on the elliptic curve.

If the point is zero, returns 1, otherwise raise a NotImplementedError.

For curves over number fields and finite fields, see below.

Note

additive_order() is a synonym for order()

EXAMPLE:

sage: K.<t>=FractionField(PolynomialRing(QQ,'t'))
sage: E=EllipticCurve([0,0,0,-t^2,0])   
sage: P=E(t,0) 
sage: P.order()                                  
...
NotImplementedError: Computation of order of a point not implemented over general fields.
sage: E(0).additive_order()
1
sage: E(0).order() == 1
True

plot(**args)¶

Plot this point on an elliptic curve.

INPUT:

**args – all arguments get passed directly onto the point plotting function.

EXAMPLES:

sage: E = EllipticCurve('389a')
sage: P = E([-1,1])
sage: P.plot(pointsize=30, rgbcolor=(1,0,0))

scheme()¶

Return the scheme of this point, i.e., the curve it is on. This is synonymous with curve() which is perhaps more intuitive.

EXAMPLES:

sage: E=EllipticCurve(QQ,[1,1])
sage: P=E(0,1)
sage: P.scheme()
Elliptic Curve defined by y^2 = x^3 + x + 1 over Rational Field
sage: P.scheme() == P.curve()
True
sage: K.<a>=NumberField(x^2-3,'a')
sage: P=E.base_extend(K)(1,a)
sage: P.scheme()
Elliptic Curve defined by y^2 = x^3 + x + 1 over Number Field in a with defining polynomial x^2 - 3

weil_pairing(Q, n)¶

Compute the Weil pairing of self and $Q$ using Miller’s algorithm.

INPUT:

Q – a point on self.curve().
n – an integer $n$ such that $nP = nQ = (0:1:0)$ where $P$ = self.

OUTPUT:

An $n$ ‘th root of unity in the base field self.curve().base_field()

EXAMPLES:

sage: F.<a>=GF(2^5)
sage: E=EllipticCurve(F,[0,0,1,1,1])
sage: P = E(a^4 + 1, a^3)
sage: Fx.<b>=GF(2^(4*5))
sage: Ex=EllipticCurve(Fx,[0,0,1,1,1])
sage: phi=Hom(F,Fx)(F.gen().minpoly().roots(Fx)[0][0])
sage: Px=Ex(phi(P.xy()[0]),phi(P.xy()[1]))
sage: O = Ex(0)
sage: Qx = Ex(b^19 + b^18 + b^16 + b^12 + b^10 + b^9 + b^8 + b^5 + b^3 + 1, b^18 + b^13 + b^10 + b^8 + b^5 + b^4 + b^3 + b) 
sage: Px.weil_pairing(Qx,41) == b^19 + b^15 + b^9 + b^8 + b^6 + b^4 + b^3 + b^2 + 1
True
sage: Px.weil_pairing(17*Px,41) == Fx(1)
True
sage: Px.weil_pairing(O,41) == Fx(1)
True

An error is raised if either point is not n-torsion:

sage: Px.weil_pairing(O,40)
...
ValueError: points must both be n-torsion

A larger example (see trac #4964):

sage: P,Q = EllipticCurve(GF(19^4,'a'),[-1,0]).gens()
sage: P.order(), Q.order()
(360, 360)
sage: z = P.weil_pairing(Q,360)
sage: z.multiplicative_order()
360

An example over a number field:

sage: P,Q = EllipticCurve('11a1').change_ring(CyclotomicField(5)).torsion_subgroup().gens()
sage: (P.order(),Q.order())
(5, 5)
sage: P.weil_pairing(Q,5)
zeta5^2
sage: Q.weil_pairing(P,5)
zeta5^3        

ALGORITHM:

Implemented using Proposition 8 in [Mil04]. The value 1 is returned for linearly dependent input points. This condition is caught via a DivisionByZeroError, since the use of a discrete logarithm test for linear dependence, is much to slow for large $n$ .

REFERENCES:

[Mil04] Victor S. Miller, “The Weil pairing, and its efficient calculation”, J. Cryptol., 17(4):235-261, 2004

AUTHOR:

David Hansen (2009-01-25)

xy()¶

Return the $x$ and $y$ coordinates of this point, as a 2-tuple. If this is the point at infinity a ZeroDivisionError is raised.

EXAMPLES:

sage: E = EllipticCurve('389a')
sage: P = E([-1,1])
sage: P.xy()
(-1, 1)
sage: Q = E(0); Q
(0 : 1 : 0)
sage: Q.xy()
...
ZeroDivisionError: Rational division by zero

class sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field(curve, v, check=True)¶

Bases: sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_field

Class for elliptic curve points over finite fields.

additive_order()¶

Return the order of this point on the elliptic curve.

ALGORITHM:

Use generic functions from sage.groups.generic. If the group order is known, use order_from_multiple(), otherwise use order_from_bounds() with the Hasse bounds for the base field. In the latter case, we might find that we have a generator for the group, in which case it is cached.

We do not cause the group order to be calculated when not known, since this function is used in determining the group order via computation of several random points and their orders.

Note

additive_order() is a synonym for order()

AUTHOR:

John Cremona, 2008-02-10, adapted 2008-04-05 to use generic functions.

EXAMPLES:

sage: k.<a> = GF(5^5)
sage: E = EllipticCurve(k,[2,4]); E
Elliptic Curve defined by y^2 = x^3 + 2*x + 4 over Finite Field in a of size 5^5
sage: P = E(3*a^4 + 3*a , 2*a + 1 )
sage: P.order()
3227
sage: Q = E(0,2)
sage: Q.order()
7
sage: Q.additive_order()
7

In the next example, the cardinality of E will be computed (using SEA) and cached:

sage: p=next_prime(2^150)
sage: E=EllipticCurve(GF(p),[1,1])
sage: P=E(831623307675610677632782670796608848711856078, 42295786042873366706573292533588638217232964)
sage: P.order()
1427247692705959881058262545272474300628281448
sage: P.order()==E.cardinality()
True

discrete_log(Q, ord=None)¶

Returns discrete log of $Q$ with respect to $P$ =self.

INPUT:

Q (point) – another point on the same curve as self.
ord (integer or None (default)) – the order of self.

OUTPUT:

(integer) – The discrete log of $Q$ with respect to $P$ , which is an integer $m$ with $0\le m<o(P)$ such that $mP=Q$ , if one exists. A ValueError is raised if there is no solution.

Note

The order of self is computed if not supplied.

AUTHOR:

John Cremona. Adapted to use generic functions 2008-04-05.

EXAMPLE:

sage: F=GF(3^6,'a')
sage: a=F.gen()
sage: E= EllipticCurve([0,1,1,a,a])
sage: E.cardinality()
762
sage: A,G=E.abelian_group() ## set since this E is cyclic
sage: P=G[0]
sage: Q=400*P
sage: P.discrete_log(Q)
400

order()¶

Return the order of this point on the elliptic curve.

ALGORITHM:

Use generic functions from sage.groups.generic. If the group order is known, use order_from_multiple(), otherwise use order_from_bounds() with the Hasse bounds for the base field. In the latter case, we might find that we have a generator for the group, in which case it is cached.

We do not cause the group order to be calculated when not known, since this function is used in determining the group order via computation of several random points and their orders.

Note

additive_order() is a synonym for order()

AUTHOR:

John Cremona, 2008-02-10, adapted 2008-04-05 to use generic functions.

EXAMPLES:

sage: k.<a> = GF(5^5)
sage: E = EllipticCurve(k,[2,4]); E
Elliptic Curve defined by y^2 = x^3 + 2*x + 4 over Finite Field in a of size 5^5
sage: P = E(3*a^4 + 3*a , 2*a + 1 )
sage: P.order()
3227
sage: Q = E(0,2)
sage: Q.order()
7
sage: Q.additive_order()
7

In the next example, the cardinality of E will be computed (using SEA) and cached:

sage: p=next_prime(2^150)
sage: E=EllipticCurve(GF(p),[1,1])
sage: P=E(831623307675610677632782670796608848711856078, 42295786042873366706573292533588638217232964)
sage: P.order()
1427247692705959881058262545272474300628281448
sage: P.order()==E.cardinality()
True

class sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_number_field(curve, v, check=True)¶

Bases: sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_field

A point on an elliptic curve over a number field.

Most of the functionality is derived from the parent class EllipticCurvePoint_field. In addition we have support for the order of a point, and heights (currently only implemented over $\QQ$ ).

EXAMPLES:

sage: E = EllipticCurve('37a')
sage: E([0,0])
(0 : 0 : 1)
sage: E(0,0)               # brackets are optional
(0 : 0 : 1)
sage: E([GF(5)(0), 0])     # entries are coerced
(0 : 0 : 1)      

sage: E(0.000, 0)
(0 : 0 : 1)
 
sage: E(1,0,0)  
...
TypeError: Coordinates [1, 0, 0] do not define a point on
Elliptic Curve defined by y^2 + y = x^3 - x over Rational Field

sage: E = EllipticCurve([0,0,1,-1,0])
sage: S = E(QQ); S
Abelian group of points on Elliptic Curve defined by y^2 + y = x^3 - x over Rational Field

TESTS:

sage: loads(S.dumps()) == S
True
sage: P = E(0,0); P
(0 : 0 : 1)
sage: loads(P.dumps()) == P
True
sage: T = 100*P
sage: loads(T.dumps()) == T
True

Test pickling an elliptic curve that has known points on it:

sage: e = EllipticCurve([0, 0, 1, -1, 0]); g = e.gens(); loads(dumps(e)) == e
True

additive_order()¶

Return the order of this point on the elliptic curve.

If the point has infinite order, returns +Infinity. For curves defined over $\QQ$ , we call pari; over other number fields we implement the function here.

Note

additive_order() is a synonym for order()

EXAMPLES:

sage: E = EllipticCurve([0,0,1,-1,0])
sage: P = E([0,0]); P
(0 : 0 : 1)
sage: P.order()
+Infinity

sage: E = EllipticCurve([0,1])
sage: P = E([-1,0])
sage: P.order()
2
sage: P.additive_order()
2

archimedian_local_height(v=None, prec=None)¶

Computes the local height of self at the archimedian place $v$ .

If $v$ is None, returns the (weighted) sum of all archimedian contributions to the height.

The normalization is taken to be independant of the base field, but twice that in the paper. Note also that this local height depends on the model of the curve.

INPUT:

v – a real or complex embedding, or None
prec – the precision of the computation. If None, the precision is deduced from v.

ALGORITHM:

See section 4 of Silverman, J. Computing Heights on Elliptic Curves. Mathematics of Computation, Vol. 51, No. 183 (Jul., 1988), pp. 339-358

EXAMPLES:

Examples 1, 2, and 3 from the above paper:

sage: K.<a> = QuadraticField(-2)
sage: E = EllipticCurve(K, [0,-1,1,0,0]); E
Elliptic Curve defined by y^2 + y = x^3 + (-1)*x^2 over Number Field in a with defining polynomial x^2 + 2
sage: P = E.lift_x(2+a); P
(a + 2 : 2*a + 1 : 1)
sage: P.archimedian_local_height(K.places(prec=170)[0]) / 2
0.45754773287523276736211210741423654346576029814695

sage: K.<i> = NumberField(x^2+1)
sage: E = EllipticCurve(K, [0,0,4,6*i,0]); E
Elliptic Curve defined by y^2 + 4*y = x^3 + 6*i*x over Number Field in i with defining polynomial x^2 + 1
sage: P = E((0,0))
sage: P.archimedian_local_height(K.places()[0]) / 2
0.510184995162373

sage: Q = E.lift_x(-9/4); Q
(-9/4 : 27/8*i - 4 : 1)
sage: Q.archimedian_local_height(K.places()[0]) / 2
0.654445619529600

elliptic_logarithm(embedding=None, precision=100, algorithm='pari')¶

Returns the elliptic logarithm of this elliptic curve point.

An embedding of the base field into $\RR$ or $\CC$ (with arbitrary precision) may be given; otherwise the first real embedding is used (with the specified precision) if any, else the first complex embedding.

INPUT:

embedding: an embedding of the base field into $\RR$ or $\CC$
precision: a positive integer (default 100) setting the number of bits of precision for the computation
algorithm: either ‘pari’ (default for real embeddings) to use Pari’s ellpointtoz{}, or ‘sage’ for a native implementation. Ignored for complex embeddings.

ALGORITHM:

See [Co2] Cohen H., A Course in Computational Algebraic Number Theory GTM 138, Springer 1996 for the case of real embeddings, and Cremona, J.E. and Thongjunthug , T. 2010 for the complex case.

AUTHORS:

Michael Mardaus (2008-07),
Tobias Nagel (2008-07) – original version from [Co2].
John Cremona (2008-07) – revision following eclib code.
John Cremona (2010-03) – implementation for complex embeddings.

EXAMPLES:

sage: E = EllipticCurve('389a')
sage: E.discriminant() > 0
True
sage: P = E([-1,1])
sage: P.is_on_identity_component ()
False
sage: P.elliptic_logarithm (precision=96) 
0.4793482501902193161295330101 + 0.985868850775824102211203849...*I
sage: Q=E([3,5])
sage: Q.is_on_identity_component()     
True
sage: Q.elliptic_logarithm (precision=96)                  
1.931128271542559442488585220

An example with negative discriminant, and a torsion point:

sage: E = EllipticCurve('11a1')
sage: E.discriminant() < 0
True
sage: P = E([16,-61])
sage: P.elliptic_logarithm(precision=70)
0.25384186085591068434
sage: E.period_lattice().real_period(prec=70) / P.elliptic_logarithm(precision=70)
5.0000000000000000000

A larger example. The default algorithm uses Pari and makes sure the result has the requested precision:

sage: E = EllipticCurve([1, 0, 1, -85357462, 303528987048]) #18074g1
sage: P = E([4458713781401/835903744, -64466909836503771/24167649046528, 1])
sage: P.elliptic_logarithm()  # 100 bits
0.27656204014107061464076203097

The native algorithm ‘sage’ used to have trouble with precision in this example, but no longer:

sage: P.elliptic_logarithm(algorithm='sage')  # 100 bits
0.27656204014107061464076203097

This shows that the bug reported at #4901 has been fixed:

sage: E = EllipticCurve("4390c2")
sage: P = E(683762969925/44944,-565388972095220019/9528128)
sage: P.elliptic_logarithm()
0.00025638725886520225353198932529
sage: P.elliptic_logarithm(precision=64)
0.000256387258865202254
sage: P.elliptic_logarithm(precision=65)
0.0002563872588652022535
sage: P.elliptic_logarithm(precision=128)
0.00025638725886520225353198932528666427412
sage: P.elliptic_logarithm(precision=129)
0.00025638725886520225353198932528666427412
sage: P.elliptic_logarithm(precision=256)
0.0002563872588652022535319893252866642741168388008346370015005142128009610936373
sage: P.elliptic_logarithm(precision=257)
0.00025638725886520225353198932528666427411683880083463700150051421280096109363730

Examples over number fields:

sage: K.<a> = NumberField(x^3-2)                                
sage: embs = K.embeddings(CC)
sage: E = EllipticCurve([0,1,0,a,a])                            
sage: Ls = [E.period_lattice(e) for e in embs]
sage: [L.real_flag for L in Ls]
[0, 0, -1]
sage: P = E.torsion_points()[0]                                 
sage: [L.elliptic_logarithm(P) for L in Ls]   
[-1.73964256006716 - 1.07861534489191*I, -0.363756518406398 - 1.50699412135253*I, 1.90726488608927]

sage: E = EllipticCurve([-a^2 - a - 1, a^2 + a])
sage: Ls = [E.period_lattice(e) for e in embs]
sage: pts = [E(2*a^2 - a - 1 , -2*a^2 - 2*a + 6 ), E(-2/3*a^2 - 1/3 , -4/3*a - 2/3 ), E(5/4*a^2 - 1/2*a , -a^2 - 1/4*a + 9/4 ), E(2*a^2 + 3*a + 4 , -7*a^2 - 10*a - 12 )]
sage: [[L.elliptic_logarithm(P) for P in pts] for L in Ls]
[[0.250819591818930 - 0.411963479992219*I, -0.290994550611374 - 1.37239400324105*I, -0.693473752205595 - 2.45028458830342*I, -0.151659609775291 - 1.48985406505459*I], [1.33444787667954 - 1.50889756650544*I, 0.792633734249234 - 0.548467043256610*I, 0.390154532655013 + 0.529423541805758*I, 0.931968675085317 - 0.431006981443071*I], [1.14758249500109 + 0.853389664016075*I, 2.59823462472518 + 0.853389664016075*I, 1.75372176444709, 0.303069634723001]]

sage: K.<i> = QuadraticField(-1)
sage: E = EllipticCurve([0,0,0,9*i-10,21-i])
sage: emb = K.embeddings(CC)[1]
sage: L = E.period_lattice(emb)
sage: P = E(2-i,4+2*i)
sage: L.elliptic_logarithm(P,prec=100)
0.70448375537782208460499649302 - 0.79246725643650979858266018068*I

has_finite_order()¶

Return True iff this point has finite order on the elliptic curve.

EXAMPLES:

sage: E = EllipticCurve([0,0,1,-1,0])
sage: P = E([0,0]); P
(0 : 0 : 1)
sage: P.has_finite_order()
False

sage: E = EllipticCurve([0,1])
sage: P = E([-1,0])
sage: P.has_finite_order()
True

has_good_reduction(P=None)¶

Returns True iff this point has good reduction modulo a prime.

INPUT:

P – a prime of the base_field of the point’s curve, or None (default)

OUTPUT:

(bool) If a prime $P$ of the base field is specified, returns True iff the point has good reduction at $P$ ; otherwise, return true if the point has god reduction at all primes in the support of the discriminant of this model.

EXAMPLES:

sage: E = EllipticCurve('990e1')
sage: P = E.gen(0); P
(15 : 51 : 1)
sage: [E.has_good_reduction(p) for p in [2,3,5,7]]
[False, False, False, True]
sage: [P.has_good_reduction(p) for p in [2,3,5,7]]
[True, False, True, True]
sage: [E.tamagawa_exponent(p) for p in [2,3,5,7]]
[2, 2, 1, 1]
sage: [(2*P).has_good_reduction(p) for p in [2,3,5,7]]
[True, True, True, True]
sage: P.has_good_reduction()
False
sage: (2*P).has_good_reduction()
True
sage: (3*P).has_good_reduction()
False

sage: K.<i> = NumberField(x^2+1)
sage: E = EllipticCurve(K,[0,1,0,-160,308])
sage: P = E(26,-120)
sage: E.discriminant().support()
[Fractional ideal (i + 1),
Fractional ideal (-i - 2),
Fractional ideal (2*i + 1),
Fractional ideal (3)]
sage: [E.tamagawa_exponent(p) for p in E.discriminant().support()]
[1, 4, 4, 4]
sage: P.has_good_reduction()
False
sage: (2*P).has_good_reduction()
False
sage: (4*P).has_good_reduction()
True

TESTS:

An example showing that #8498 is fixed:

sage: E = EllipticCurve('11a1')
sage: K.<t> = NumberField(x^2+47)
sage: EK = E.base_extend(K)
sage: T = EK(5,5)
sage: P = EK(-2, -1/2*t - 1/2)
sage: p = K.ideal(11)
sage: T.has_good_reduction(p)
False
sage: P.has_good_reduction(p)
True

has_infinite_order()¶

Return True iff this point has infinite order on the elliptic curve.

EXAMPLES:

sage: E = EllipticCurve([0,0,1,-1,0])
sage: P = E([0,0]); P
(0 : 0 : 1)
sage: P.has_infinite_order()
True

sage: E = EllipticCurve([0,1])
sage: P = E([-1,0])
sage: P.has_infinite_order()
False

height(precision=None)¶

The Neron-Tate canonical height of the point.

INPUT:

self – a point on a curve over a number field
precision – (int or None (default)): the precision in bits of the result (default real precision if None)

OUTPUT:

The rational number 0, or a nonzero real field element.

The returned height is normalized to be independant of the base field. Fixing this, there are two normalizations used in the literature, one of which is double the other. We use the larger of the two, which is the one appropriate for the BSD conjecture. This is consistant with [Cre] and double that of [Sil].

REFERENCES:

[Cre] John Cremona, Algorithms for modular elliptic curves, Cambridge University Press, 1997.
[Sil] Silverman, Joseph H. The arithmetic of elliptic curves. Second edition. Graduate Texts in Mathematics, 106. Springer, 2009.

EXAMPLES:

sage: E = EllipticCurve('11a'); E
Elliptic Curve defined by y^2 + y = x^3 - x^2 - 10*x - 20 over Rational Field
sage: P = E([5,5]); P
(5 : 5 : 1)
sage: P.height()
0
sage: Q = 5*P
sage: Q.height()
0

sage: E = EllipticCurve('37a'); E
Elliptic Curve defined by y^2 + y = x^3 - x over Rational Field
sage: P = E([0,0])
sage: P.height()
0.0511114082399688
sage: P.order()
+Infinity
sage: E.regulator()
0.0511114082399688...

sage: def naive_height(P):
...       return log(RR(max(abs(P[0].numerator()), abs(P[0].denominator()))))
sage: for n in [1..10]:
...       print naive_height(2^n*P)/4^n
0.000000000000000
0.0433216987849966
0.0502949347635656
0.0511006335618645
0.0511007834799612
0.0511013666152466
0.0511034199907743
0.0511106492906471
0.0511114081541082
0.0511114081541180

sage: E = EllipticCurve('4602a1'); E
Elliptic Curve defined by y^2 + x*y  = x^3 + x^2 - 37746035*x - 89296920339 over Rational Field
sage: x = 77985922458974949246858229195945103471590
sage: y = 19575260230015313702261379022151675961965157108920263594545223
sage: d = 2254020761884782243
sage: E([ x / d^2,  y / d^3 ]).height()
86.7406561381275

sage: E = EllipticCurve([17, -60, -120, 0, 0]); E
Elliptic Curve defined by y^2 + 17*x*y - 120*y = x^3 - 60*x^2 over Rational Field
sage: E([30, -90]).height()
0

sage: E = EllipticCurve('389a1'); E
Elliptic Curve defined by y^2 + y = x^3 + x^2 - 2*x over Rational Field 
sage: [P,Q] = [E(-1,1),E(0,-1)] 
sage: P.height(precision=100) 
0.68666708330558658572355210295 
sage: (3*Q).height(precision=100)/Q.height(precision=100) 
9.0000000000000000000000000000 
sage: _.parent() 
Real Field with 100 bits of precision

Canonical heights over number fields are implemented as well:

sage: R.<x> = QQ[]
sage: K.<a> = NumberField(x^3-2)
sage: E = EllipticCurve([a, 4]); E
Elliptic Curve defined by y^2 = x^3 + a*x + 4 over Number Field in a with defining polynomial x^3 - 2
sage: P = E((0,2))
sage: P.height()
0.810463096585925
sage: P.height(precision=100)
0.81046309658592536863991810577
sage: P.height(precision=200)
0.81046309658592536863991810576865158896130286417155832378086
sage: (2*P).height() / P.height()
4.00000000000000
sage: (100*P).height() / P.height()
10000.0000000000

Some consistency checks:

sage: E = EllipticCurve('5077a1')
sage: P = E([-2,3,1])
sage: P.height()
1.36857250535393

sage: EK = E.change_ring(QuadraticField(-3,'a'))
sage: PK = EK([-2,3,1])
sage: PK.height()
1.36857250535393

sage: K.<i> = NumberField(x^2+1)
sage: E = EllipticCurve(K, [0,0,4,6*i,0])
sage: Q = E.lift_x(-9/4); Q
(-9/4 : 27/8*i - 4 : 1)
sage: Q.height()
2.69518560017909
sage: (15*Q).height() / Q.height()
225.000000000000

sage: E = EllipticCurve('37a')
sage: P = E([0,-1])
sage: P.height()
0.0511114082399688
sage: K.<a> = QuadraticField(-7)
sage: ED = E.quadratic_twist(-7)
sage: Q = E.isomorphism_to(ED.change_ring(K))(P); Q
(0 : -7/2*a - 1/2 : 1)
sage: Q.height()
0.0511114082399688
sage: Q.height(precision=100)
0.051111408239968840235886099755

An example to show that the bug at #5252 is fixed:

sage: E = EllipticCurve([1, -1, 1, -2063758701246626370773726978, 32838647793306133075103747085833809114881])
sage: P = E([-30987785091199, 258909576181697016447])
sage: P.height()
25.8603170675462
sage: P.height(precision=100)
25.860317067546190743868840741
sage: P.height(precision=250)
25.860317067546190743868840740735110323098872903844416215577171041783572513
sage: P.height(precision=500)
25.8603170675461907438688407407351103230988729038444162155771710417835725129551130570889813281792157278507639909972112856019190236125362914195452321720

An example to show that the bug at #8319 is fixed (correct height when the curve is not minimal):

sage: E = EllipticCurve([-5580472329446114952805505804593498080000,-157339733785368110382973689903536054787700497223306368000000])
sage: xP = 204885147732879546487576840131729064308289385547094673627174585676211859152978311600/23625501907057948132262217188983681204856907657753178415430361
sage: P = E.lift_x(xP)
sage: P.height()
157.432598516754
sage: Q = 2*P
sage: Q.height() # long time (4s)
629.730394067016
sage: Q.height()-4*P.height() # long time
0.000000000000000

is_on_identity_component(embedding=None)¶

Returns True iff this point is on the identity component of its curve with respect to a given (real or complex) embedding.

INPUT:

self – a point on a curve over any ordered field (e.g. $\QQ$ )
embedding – an embedding from the base_field of the point’s curve into $\RR$ or $\CC$ ; if None (the default) it uses the first embedding of the base_field into $\RR$ if any, else the first embedding into $\CC$ .

OUTPUT:

(bool) – True iff the point is on the identity component of the curve. (If the point is zero then the result is True.)

EXAMPLES:

For $K=\QQ$ there is no need to specify an embedding:

sage: E=EllipticCurve('5077a1')     
sage: [E.lift_x(x).is_on_identity_component() for x in range(-3,5)] 
[False, False, False, False, False, True, True, True]

An example over a field with two real embeddings:

sage: L.<a> = QuadraticField(2)                               
sage: E=EllipticCurve(L,[0,1,0,a,a])
sage: P=E(-1,0)
sage: [P.is_on_identity_component(e) for e in L.embeddings(RR)]
[False, True]

We can check this as follows:

sage: [e(E.discriminant())>0 for e in L.embeddings(RR)]
[True, False]
sage: e = L.embeddings(RR)[0]
sage: E1 = EllipticCurve(RR,[e(ai) for ai in E.ainvs()])
sage: e1,e2,e3 = E1.two_division_polynomial().roots(RR,multiplicities=False)                           
sage: e1 < e2 < e3 and e(P[0]) < e3
True

nonarchimedian_local_height(v=None, prec=None, weighted=False, is_minimal=None)¶

Computes the local height of self at the non-archimedian place $v$ .

If $v$ is None, returns the (weighted) sum of all non-archimedian contributions to the height.

The normalization is taken to be independant of the base field, but twice that in the paper. Note also that this local height depends on the model of the curve.

INPUT:

v – a non-archimedean place of the base field of the curve, or None, in which case the total nonarchimedian contribution is returned
prec – working precision, or None in which case the height is returned symbolically

ALGORITHM:

See section 5 of Silverman, J. Computing Heights on Elliptic Curves. Mathematics of Computation, Vol. 51, No. 183 (Jul., 1988), pp. 339-358

EXAMPLES:

Examples 2 and 3 from the above paper:

sage: K.<i> = NumberField(x^2+1)
sage: E = EllipticCurve(K, [0,0,4,6*i,0]); E
Elliptic Curve defined by y^2 + 4*y = x^3 + 6*i*x over Number Field in i with defining polynomial x^2 + 1
sage: P = E((0,0))
sage: P.nonarchimedian_local_height(K.ideal(i+1))
-1/2*log(2)
sage: P.nonarchimedian_local_height(K.ideal(3))
0
sage: P.nonarchimedian_local_height(K.ideal(1-2*i))
0

sage: Q = E.lift_x(-9/4); Q
(-9/4 : 27/8*i - 4 : 1)
sage: Q.nonarchimedian_local_height(K.ideal(1+i))
2*log(2)
sage: Q.nonarchimedian_local_height(K.ideal(3))
0
sage: Q.nonarchimedian_local_height(K.ideal(1-2*i))
0
sage: Q.nonarchimedian_local_height()
1/2*log(16)

TESTS:

sage: Q.nonarchimedian_local_height(prec=100)
1.3862943611198906188344642429
sage: (3*Q).nonarchimedian_local_height()
1/2*log(75923153929839865104)

sage: F.<a> = NumberField(x^4 + 2*x^3 + 19*x^2 + 18*x + 288)
sage: F.ring_of_integers().gens()
[1, 5/6*a^3 + 1/6*a, 1/6*a^3 + 1/6*a^2, a^3]
sage: F.class_number()
12
sage: E = EllipticCurve('37a').change_ring(F)
sage: P = E((-a^2/6 - a/6 - 1, a)); P
(-1/6*a^2 - 1/6*a - 1 : a : 1)
sage: P[0].is_integral()
True
sage: P.nonarchimedian_local_height()
0

order()¶

Return the order of this point on the elliptic curve.

If the point has infinite order, returns +Infinity. For curves defined over $\QQ$ , we call pari; over other number fields we implement the function here.

Note

additive_order() is a synonym for order()

EXAMPLES:

sage: E = EllipticCurve([0,0,1,-1,0])
sage: P = E([0,0]); P
(0 : 0 : 1)
sage: P.order()
+Infinity

sage: E = EllipticCurve([0,1])
sage: P = E([-1,0])
sage: P.order()
2
sage: P.additive_order()
2

padic_elliptic_logarithm(p, absprec=20)¶

Computes the $p$ -adic elliptic logarithm of this point.

INPUT:

p - integer: a prime absprec - integer (default: 20): the initial $p$ -adic absolute precision of the computation

OUTPUT:

The $p$ -adic elliptic logarithm of self, with precision absprec.

AUTHORS:

Tobias Nagel
Michael Mardaus
John Cremona

ALGORITHM:

For points in the formal group (i.e. not integral at $p$ ) we take the log() function from the formal groups module and evaluate it at $-x/y$ . Otherwise we first multiply the point to get into the formal group, and divide the result afterwards.

TODO:

See comments at trac #4805. Currently the absolute precision of the result may be less than the given value of absprec, and error-handling is imperfect.

EXAMPLES:

sage: E = EllipticCurve([0,1,1,-2,0])
sage: E(0).padic_elliptic_logarithm(3)
0
sage: P = E(0,0)
sage: P.padic_elliptic_logarithm(3)
2 + 2*3 + 3^3 + 2*3^7 + 3^8 + 3^9 + 3^11 + 3^15 + 2*3^17 + 3^18 + O(3^19)
sage: P.padic_elliptic_logarithm(3).lift()
660257522
sage: P = E(-11/9,28/27)
sage: [(2*P).padic_elliptic_logarithm(p)/P.padic_elliptic_logarithm(p) for p in prime_range(20)]
[2 + O(2^19), 2 + O(3^20), 2 + O(5^19), 2 + O(7^19), 2 + O(11^19), 2 + O(13^19), 2 + O(17^19), 2 + O(19^19)]
sage: [(3*P).padic_elliptic_logarithm(p)/P.padic_elliptic_logarithm(p) for p in prime_range(12)]
[1 + 2 + O(2^19), 3 + 3^20 + O(3^21), 3 + O(5^19), 3 + O(7^19), 3 + O(11^19)]
sage: [(5*P).padic_elliptic_logarithm(p)/P.padic_elliptic_logarithm(p) for p in prime_range(12)]
[1 + 2^2 + O(2^19), 2 + 3 + O(3^20), 5 + O(5^19), 5 + O(7^19), 5 + O(11^19)]

An example which arose during reviewing #4741:

sage: E = EllipticCurve('794a1')
sage: P = E(-1,2)
sage: P.padic_elliptic_logarithm(2) # default precision=20
2^4 + 2^5 + 2^6 + 2^8 + 2^9 + 2^13 + 2^14 + 2^15 + O(2^16)
sage: P.padic_elliptic_logarithm(2, absprec=30)
2^4 + 2^5 + 2^6 + 2^8 + 2^9 + 2^13 + 2^14 + 2^15 + 2^22 + 2^23 + 2^24 + O(2^26)
sage: P.padic_elliptic_logarithm(2, absprec=40)
2^4 + 2^5 + 2^6 + 2^8 + 2^9 + 2^13 + 2^14 + 2^15 + 2^22 + 2^23 + 2^24 + 2^28 + 2^29 + 2^31 + 2^34 + O(2^35)

Points on elliptic curves¶

Previous topic

Next topic

This Page

Navigation

Points on elliptic curves¶

Previous topic

Next topic

This Page

Quick search

Navigation