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
) and over finite fields. Although there is no special
class for points over
, there is currently greater
functionality implemented over
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 :
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
AUTHORS:
William Stein (2005) – Initial version
Robert Bradshaw et al....
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) – -adic elliptic logarithm over
David Hansen (Jan 2009) – Added weil_pairing function to EllipticCurvePoint_finite_field class
A point on an elliptic curve.
Standard comparison function for points on elliptic curves, to allow sorting and equality testing.
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
Comparison function for points to allow sorting and equality testing.
EXAMPLES:
sage: E = EllipticCurve('45a')
sage: P = E([2, -1, 1])
sage: P == E(0)
False
sage: P+P == E(0)
True
Return the n’th coordinate of this point.
EXAMPLE:
sage: E = EllipticCurve('42a')
sage: P = E([-17, -51, 17])
sage: [P[i] for i in [2,1,0]]
[1, -3, -1]
Constructor for a point on an elliptic curve.
INPUT:
curve – an elliptic curve
0, or a tuple of coordinates)
EXAMPLE:
sage: E = EllipticCurve('43a')
sage: P = E([2, -4, 2]); P
(1 : -2 : 1)
sage: P = E(0); P
(0 : 1 : 0)
sage: P=E(2, -4, 2); P
(1 : -2 : 1)
Return the coordinates of this point as a list.
EXAMPLE:
sage: E = EllipticCurve('37a')
sage: list(E([0,0]))
[0, 0, 1]
Return the additive inverse of this point.
EXAMPLES:
sage: E = EllipticCurve('389a')
sage: P = E([-1,1])
sage: Q = -P; Q
(-1 : -2 : 1)
sage: Q + P
(0 : 1 : 0)
Example to show that bug #4820 is fixed:
sage: [type(c) for c in -EllipticCurve('37a1').gen(0)]
[<type 'sage.rings.rational.Rational'>,
<type 'sage.rings.rational.Rational'>,
<type 'sage.rings.rational.Rational'>]
Return True if this is not the zero point on the curve.
EXAMPLES:
sage: E = EllipticCurve('37a')
sage: P = E(0); P
(0 : 1 : 0)
sage: P.is_zero()
True
sage: P = E.gens()[0]
sage: P.is_zero()
False
Return the coordinates of this point as a tuple.
EXAMPLE:
sage: E = EllipticCurve('44a')
sage: P = E([1, -2, 1])
sage: P.__tuple__()
(1, -2, 1)
Add self to right.
EXAMPLES:
sage: E = EllipticCurve('389a')
sage: P = E([-1,1]); Q = E([0,0])
sage: P + Q
(1 : 0 : 1)
sage: P._add_(Q) == P + Q
True
Example to show that bug #4820 is fixed:
sage: [type(c) for c in 2*EllipticCurve('37a1').gen(0)]
[<type 'sage.rings.rational.Rational'>,
<type 'sage.rings.rational.Rational'>,
<type 'sage.rings.rational.Rational'>]
Return where
== self and
cannot be divided by
.
..WARNING:
It is up to the caller to make sure that this does not loop
endlessly. It is used in
EllipticCurve_generic._p_primary_torsion_basis(), when
self will always have (finite) order which is a power of ,
so that the order of
increases by a factor of
at each
stage.
Since it will clearly be in danger of looping when self.is_zero(), this case is caught, but otherwise caveat user.
EXAMPLES:
sage: E = EllipticCurve('37a1')
sage: P = E([0, 0])
sage: R = 12*P
sage: R._divide_out(2)
((-1 : -1 : 1), 2)
sage: R._divide_out(3)
((2 : -3 : 1), 1)
sage: R._divide_out(5)
((1357/841 : 28888/24389 : 1), 0)
sage: R._divide_out(12)
...
ValueError: p (=12) should be prime.
Return a LaTeX representation of this point.
EXAMPLE:
sage: E = EllipticCurve('40a')
sage: P = E([3, 0])
sage: P._latex_()
'\left(3 : 0 : 1\right)'
Computes the value at of a straight line through points self and
.
INPUT:
OUTPUT:
An element of 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: Q = E(a^4, a^4 + a^3)
sage: O = E(0)
sage: P._line_(P,-2*P) == 0
True
sage: P._line_(Q,-(P+Q)) == 0
True
sage: O._line_(O,Q) == F(1)
True
sage: P._line_(O,Q) == a^4 - a^4 + 1
True
sage: P._line_(13*P,Q) == a^4
True
sage: P._line_(P,Q) == a^4 + a^3 + a^2 + 1
True
..NOTES:
This function is used in _miller_ algorithm.
AUTHOR:
Compute the value at of the rational function
, where the divisor of
is
.
INPUT:
OUTPUT:
An element 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: 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._miller_(Qx,41) == b^17 + b^13 + b^12 + b^9 + b^8 + b^6 + b^4 + 1
True
sage: Qx._miller_(Px,41) == b^13 + b^10 + b^8 + b^7 + b^6 + b^5
True
An example of even order:
sage: F.<a> = GF(19^4)
sage: E = EllipticCurve(F,[-1,0])
sage: P = E(15*a^3 + 17*a^2 + 14*a + 13,16*a^3 + 7*a^2 + a + 18)
sage: Q = E(10*a^3 + 16*a^2 + 4*a + 2, 6*a^3 + 4*a^2 + 3*a + 2)
sage: x=P.weil_pairing(Q,360)
sage: x^360 == F(1)
True
You can use the _miller_ function on linearly dependent points, but with the risk of a dividing with zero:
sage: Px._miller_(2*Px,41)
...
ZeroDivisionError: division by zero in finite field.
ALGORITHM:
Double-and-add.
REFERENCES:
AUTHOR:
Return a string representation of this point.
EXAMPLE:
sage: E = EllipticCurve('39a')
sage: P = E([-2, 1, 1])
sage: P._repr_()
'(-2 : 1 : 1)'
Subtract right from self.
EXAMPLES:
sage: E = EllipticCurve('389a')
sage: P = E([-1,1]); Q = E([0,0])
sage: P - Q
(4 : 8 : 1)
sage: P - Q == P._sub_(Q)
True
sage: (P - Q) + Q
(-1 : 1 : 1)
sage: P
(-1 : 1 : 1)
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
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
Return a list of all points such that
where
= self.
Only points on the elliptic curve containing self and defined over the base field are included.
INPUT:
OUTPUT:
(list) – a (possibly empty) list of solutions to
, where
= 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 :
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 -division points as a consistency check – there
is just one, of course:
sage: P.division_points(1)
[(3 : 3*a + 4 : 1)]
The point 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)]
Return the domain of this point, which is where
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
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
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
Return True if there exists a point defined over the same
field as self such that
== self.
INPUT:
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
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
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.
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).order() == 1
True
Plot this point on an elliptic curve.
INPUT:
EXAMPLES:
sage: E = EllipticCurve('389a')
sage: P = E([-1,1])
sage: P.plot(pointsize=30, rgbcolor=(1,0,0))
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
Compute the Weil pairing of self and using Miller’s algorithm.
INPUT:
OUTPUT:
An ‘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 .
REFERENCES:
[Mil04] Victor S. Miller, “The Weil pairing, and its efficient calculation”, J. Cryptol., 17(4):235-261, 2004
AUTHOR:
Return the and
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 for elliptic curve points over finite fields.
Return a string representation of self that MAGMA can use for input.
EXAMPLE:
sage: E = EllipticCurve(GF(17), [1,-1])
sage: P = E([13, 4])
sage: P._magma_init_(magma) # optional - magma
'EllipticCurve([_sage_ref...|GF(17)!0,GF(17)!0,GF(17)!0,GF(17)!1,GF(17)!16])![13,4]'
Returns discrete log of with respect to
=self.
INPUT:
OUTPUT:
(integer) – The discrete log of with respect to
, which is an
integer
with
such that
, if one
exists. A ValueError is raised if there is no solution.
Note
The order of self is computed if not supplied.
AUTHOR:
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
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.
AUTHOR:
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
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
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
).
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
Returns the elliptic logarithm of this elliptic curve point.
An embedding of the base field into (with arbitrary
precision) may be given; otherwise the first real embedding is
used (with the specified precision), if there are any;
otherwise a NotImplementedError is raised, since we have not
yet implemented the complex elliptic logarithm.
INPUT:
ALGORITHM:
See [Co2] Cohen H., A Course in Computational Algebraic Number Theory GTM 138, Springer 1996.
AUTHORS:
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
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
Returns True iff this point has good reduction modulo a prime.
INPUT:
OUTPUT:
(bool) If a prime of the base field is specified, returns
True iff the point has good reduction at
; 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
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
The Neron-Tate canonical height of the point.
Currently only implemented for curves defined over (using
pari); and for points of finite order.
INPUT:
OUTPUT:
The rational number 0, or a nonzero real field element
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() # slightly random output
0.051111408239968840
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
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
Unfortunately, canonical height is not yet implemented in general:
sage: E = EllipticCurve('5077a1').change_ring(QuadraticField(-3,'a'))
sage: P = E([-2,3,1])
sage: P.height()
...
NotImplementedError: canonical height not yet implemented over general number fields.
Returns True iff this point is on the identity component of its curve with respect to a given (real or complex) embedding.
INPUT:
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 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
Return the order of this point on the elliptic curve.
If the point has infinite order, returns +Infinity. For
curves defined over , we call pari; over other
number fields we implement the function here.
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
Computes the -adic elliptic logarithm of this point.
INPUT:
p - integer: a prime absprec - integer (default: 20):
the initial -adic absolute precision of the computation
OUTPUT:
The -adic elliptic logarithm of self, with precision absprec.
AUTHORS:
ALGORITHM:
For points in the formal group (i.e. not integral at ) we
take the log() function from the formal groups module and
evaluate it at
. 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)