Operations on Points

Points on an elliptic curve over a field are given in terms of projective coordinates: A point \((a, b, c)\) is equivalent to \((x, y, z)\) if and only if there exists an element \(u\) (in the field of definition) such that \(ua=x\), \(ub=y\), and \(uc=z\). The equivalence class of \((x, y, z)\) is denoted by the projective point \((x:y:z)\). At least one of the projective coordinates must be nonzero. We call the coefficients normalised if either \(z=1\), or \(z=0\) and \(y=1\).

Creation of Points

In this section the descriptions will refer to a point set \(H\), which is either the \(H\) in the signature or the base point set of the elliptic curve \(E\) in the signature.

H ! [x, y, z]: SetPtEll, [ RngElt ] -> PtEll
elt< H | x, y, z >: SetPtEll, RngElt, RngElt, RngElt -> PtEll
E ! [x, y, z]: CrvEll, [ RngElt ] -> PtEll
elt< E | x, y, z >: CrvEll, RngElt, RngElt, RngElt -> PtEll: Given a point set \(H=E(R)\) and coefficients \(x, y, z\) in \(R\) satisfying the equation for \(E\), return the normalised point \(P=(x:y:z)\) in \(H\). If \(z\) is not specified it is assumed to be \(1\).

H ! 0: SetPtEll, RngIntElt -> PtEll
Id(H): SetPtEll -> PtEll
Identity(H): SetPtEll -> PtEll
E ! 0: CrvEll, RngIntElt -> PtEll
Id(E): CrvEll -> PtEll
Identity(E): CrvEll -> PtEll: Returns the normalised identity point \((0:1:0)\) of the point set \(H\) on the elliptic curve \(E\).

Points(H, x): SetPtEll, RngElt -> [ PtEll ]
Points(E, x): CrvEll, RngElt -> [ PtEll ]: Returns the sequence of points in the pointset \(H\) on the elliptic curve \(E\) whose x-coordinate is \(x\).

Points(H): SetPtEll -> {@ PtEll @}

RationalPoints(H): SetPtEll -> {@ PtEll @}

Points(E): CrvEll -> {@ PtEll @}

RationalPoints(E): CrvEll -> {@ PtEll @}

Bound           : RngIntElt                    Default: 0
DenominatorBound: RngIntElt                    Default: Bound
Denominators    : Setq                         Default: 
Max             : RngIntElt                    Default: 
NPrimes         : RngIntElt                    Default: 30

Given an elliptic curve \(E\) (or associated point set) over the rationals, a number field, or a finite field, this function returns an indexed set of points on the curve (or in the point set). When over a finite field this will contain all the rational points.

When over \({\mathbb{Q}}\) or a number field, a positive value for the parameter Bound must be given. Over \({\mathbb{Q}}\) this refers to the height of the \(x\)-coordinate of the points. Over number fields the algorithm searches \(x\)-coordinates in some chosen box and with some chosen denominators depending on the Bound (so here, too, there is loosely a linear relationship between the Bound and the heights of the \(x\)-coordinates searched).

The other optional parameters are only for the number field case. The denominators of \(x\)-coordinates to be searched can be specified as Denominators (a set of integral elements in the field) or by setting DenominatorBound (an integer). If an integer Max is specified then the routine returns as soon as this many points are found. The parameter NPrimes is an internal parameter that controls the number of primes used in the sieving.

The algorithm uses a sieve method; the number field case is described in Appendix A of [Bru02]. In both cases the implementation of the sieving is reasonably fast.

PointsAtInfinity(H): SetPtEll -> {@ PtEll @}
PointsAtInfinity(E): CrvEll -> {@ PtEll @}: Returns the indexed set containing the identity point of the pointset \(H\) or on the elliptic curve \(E\).

Creation Predicates

IsPoint(H, S): SetPtEll, [ RngElt ] -> BoolElt, PtEll
IsPoint(E, S): CrvEll, [ RngElt ] -> BoolElt, PtEll: Returns true if the sequence of values in \(S\) are the coordinates of a point in the pointset \(H\) or on the elliptic curve \(E\), false otherwise. If this is true then the corresponding point is returned as the second value.

IsPoint(H, x): SetPtEll, RngElt -> BoolElt, PtEll
IsPoint(E, x): CrvEll, RngElt -> BoolElt, PtEll: Returns true if \(x\) is the x-coordinate of a point in the pointset \(H\) or on the elliptic curve \(E\), false otherwise. If this is true then a corresponding point is returned as the second value. Note that the point at infinity of \(H\) will never be returned.

Access Operations

P[i]: PtEll, RngIntElt -> RngElt: Returns the \(i\)-th coefficient for an elliptic curve point \(P\), for \(1\leq i\leq 3\).

ElementToSequence(P): PtEll -> [ RngElt ]
Eltseq(P): PtEll -> [ RngElt ]: Given a point \(P\) on an elliptic curve, this function returns a sequence of length \(3\) consisting of its coefficients (normalised).

Associated Structures

Category(P): PtEll -> Cat
Type(P): PtEll -> Cat: Given a point \(P\) on an elliptic curve, this function returns PtEll, the category of elliptic curve points.

Parent(P): PtEll -> SetPtEll: Given a point \(P\) on an elliptic curve, this function returns the parent point set for \(P\).

Scheme(P): SetPtEll -> CrvEll
Curve(P): SetPtEll -> CrvEll: Given a point \(P\) on an elliptic curve, this function returns the corresponding scheme or elliptic curve for the parent point set of \(P\).

Arithmetic

The points on an elliptic curve over a field form an abelian group, for which we use the additive notation. The identity element is the point \(O = (0:1:0)\).

- P: PtEll -> PtEll: Returns the additive inverse of the point \(P\) on an elliptic curve \(E\).

P + Q: PtEll, PtEll -> PtEll: Returns the sum \(P + Q\) of two points \(P\) and \(Q\) on the same elliptic curve.

P +:= Q: PtEll, PtEll: Given two points \(P\) and \(Q\) on the same elliptic curve, sets \(P\) equal to their sum.

P - Q: PtEll, PtEll -> PtEll: Returns the difference \(P - Q\) of two points \(P\) and \(Q\) on the same elliptic curve.

P -:= Q: PtEll, PtEll: Given two points \(P\) and \(Q\) on the same elliptic curve, sets \(P\) equal to their difference.

n * P: RngIntElt, PtEll -> PtEll
P * n: PtEll, RngIntElt -> PtEll: Returns the \(n\)-th multiple of the point \(P\) on an elliptic curve.

P *:= n: PtEll, RngIntElt: Sets the point \(P\) equal to the \(n\)-th multiple of itself.

Division Points

P / n: PtEll, RngIntElt -> PtEll: Given a point \(P\) on an elliptic curve \(E\) and an integer \(n\), this function returns a point \(Q\) on \(E\) such that \(P = nQ\), if such a point exists. If no such point exists then a runtime error results.

P /:= n: PtEll, RngIntElt: Given a point \(P\) on an elliptic curve \(E\) and an integer \(n\), this function sets \(P\) equal to a point \(Q\) on \(E\) such that \(P = nQ\), if such a point exists. If no such point exists then a runtime error results.

DivisionPoints(P, n): PtEll, RngIntElt -> [ PtEll ]: Given a point \(P\) on an elliptic curve \(E\) and an integer \(n\), this function returns the sequence of all points \(Q\) on \(E\) such that \(P = nQ\) holds. If there are no such points then an empty sequence is returned.

IsDivisibleBy(P, n): PtEll, RngIntElt -> BoolElt, PtEll: Given a point \(P\) on an elliptic curve \(E\) and an integer \(n\), this function returns true if \(P\) is \(n\)-divisible, and if so, an \(n\)-division point. Otherwise false is returned.

Example: Three-Division Points (ex-8bfcbb)

Run in calculator (opens in a new tab)

> E := EllipticCurve([1, 0, 0, 12948, 421776]);
> P := E![ -65498304*1567, -872115836268, 1567^3 ];
> DivisionPoints(P, 3);
[ (312 : -6060 : 1), (-30 : -66 : 1), (216 : 3540 : 1) ]

Note that \(P\) has three three-division points — this tells us that there are three \(3\)-torsion points in \(E\). In fact, there are \(9\) points in the torsion subgroup.

> DivisionPoints(E!0, 9);
[ (0 : 1 : 0), (24 : 852 : 1), (24 : -876 : 1), (-24 : -300 : 1), (-24 : 324 : 1),
(600 : 14676 : 1), (600 : -15276 : 1), (132 : 2040 : 1), (132 : -2172 : 1) ]

Run in calculator (opens in a new tab)

Example: Reducing a Set of Generators (ex-c4b7a1)

Run in calculator (opens in a new tab)

We construct some points in a certain elliptic curve over \({\mathbb{Q}}\) and try by hand to find a “smaller” set of points that generate the same group.

> E := EllipticCurve([0, 0, 1, -7, 6]);
> P1 := E![ 175912024457 * 278846, -41450244419357361, 278846^3 ];
> P2 := E![ -151 * 8, -1845, 8^3 ];
> P3 := E![ 36773 * 41, -7036512, 41^3 ];
> P1; P2; P3;
(175912024457/77755091716 : -41450244419357361/21681696304639736 : 1)
(-151/64 : -1845/512 : 1)
(36773/1681 : -7036512/68921 : 1)

Now we try small linear combinations in the hope of finding nicer looking points. We shall omit the bad guesses and just show the good ones.

> P1 + P2;
(777/3364 : 322977/195112 : 1)

Success! We replace P1 with this new point and keep going.

> P1 +:= P2;
> P2 + P3;
(-3 : 0 : 1)
> P2 +:= P3;
> P3 - P1;
(-1 : -4 : 1)
> P3 -:= P1;
> P1 - 2*P2;
(0 : 2 : 1)
> P1 -:= 2*P2;
> [ P1, P2, P3 ];
[ (0 : 2 : 1), (-3 : 0 : 1), (-1 : -4 : 1) ]

The pairwise reductions no longer help, but there is a smaller point with \(x\)-coordinate \(1\):

> IsPoint(E, 1);
true (1 : 0 : 1)

After a small search we find:

> P1 - P2 - P3;
(1 : 0 : 1)
> P2 := P1 - P2 - P3;
> [ P1, P2, P3 ];
[ (0 : 2 : 1), (1 : 0 : 1), (-1 : -4 : 1) ]

Using a naive definition of “small” these are the smallest possible points. (Note that there are points of smaller canonical height.) These points are in fact the generators of the Mordell–Weil group for this particular elliptic curve. Since none of the transformations changed the size of the space spanned by the points it follows that the original set of points are also generators of \(E\). However, the reduced points form a much more convenient basis.

Run in calculator (opens in a new tab)

Example: Generic Point on an Elliptic Surface (ex-10e418)

Run in calculator (opens in a new tab)

We construct an elliptic curve over a function field (hence an elliptic surface) and form a “generic” point on it. First, we construct the function field.

> E := EllipticCurve([GF(97) | 1, 2]);
> K<x, y> := FunctionField(E);

Now we lift the curve to be over its own function field and form a generic point on \(E\).

> EK := BaseChange(E, K);
> P := EK![x, y, 1];
> P;
(x : y : 1)
> 2*P;
((73*x^4 + 48*x^2 + 93*x + 73)/(x^3 + x + 2) : (85*x^6 + 37*x^4 + 5*x^3
    + 60*x^2 + 96*x + 8)/(x^6 + 2*x^4 + 4*x^3 + x^2 + 4*x + 4)*y : 1)

Finally, we verify that addition of the generic point defines the addition law on the curve.

> m2 := MultiplicationByMMap(E, 2);
> P := E![ 32, 93, 1 ];
> m2(P);
(95 : 63 : 1)
> 2*P;
(95 : 63 : 1)

Run in calculator (opens in a new tab)

Point Order

Order(P): PtEll -> RngIntElt: Given a point on an elliptic curve defined over \({\mathbb{Q}}\) or a finite field, this function computes the order of \(P\); that is, the smallest positive integer \(n\) such that \(n\cdot P=O\) on the curve. If no such positive \(n\) exists then \(0\) is returned to indicate infinite order. If the curve is defined over a finite field then the order of the curve will first be computed.

FactoredOrder(P): PtEll -> RngIntElt: Given a point on an elliptic curve defined over \({\mathbb{Q}}\) or over a finite field, this function returns the factorisation of the order of \(P\). If the curve is over a finite field then on repeated applications this is generally much faster than factorising Order(P) because the factorisation of the order of the curve will be computed and stored. An error ensues if the curve is defined over \({\mathbb{Q}}\) and \(P\) has infinite order.

Example: Points over a Large Finite Field (ex-712399)

We show a few simple operations with points on an elliptic curve over a large finite field.

> E := EllipticCurve([GF(NextPrime(10^12)) | 1, 1]);
> Order(E);
1000001795702
> FactoredOrder(E);
[ <2, 1>, <7, 1>, <13, 1>, <19, 1>, <31, 1>, <43, 1>, <59, 1>, <3677, 1> ]
> P := E ! [652834414164, 320964687531, 1];
> P;
(652834414164 : 320964687531 : 1)
> IsOrder(P, Order(E));
true
> FactoredOrder(P);
[ <2, 1>, <7, 1>, <13, 1>, <19, 1>, <31, 1>, <43, 1>, <59, 1>, <3677, 1> ]
> FactoredOrder(3677 * 59 * P);
[ <2, 1>, <7, 1>, <13, 1>, <19, 1>, <31, 1>, <43, 1> ]

Run in calculator (opens in a new tab)

Predicates on Points

IsId(P): PtEll -> BoolElt
IsIdentity(P): PtEll -> BoolElt
IsZero(P): PtEll -> BoolElt: Returns true if and only if the point \(P\) is the identity point of its point set, false otherwise.

P eq Q: PtEll, PtEll -> BoolElt: Returns true if and only if \(P\) and \(Q\) are points on the same elliptic curve and have the same normalised coordinates.

P ne Q: PtEll, PtEll -> BoolElt: The logical negation of eq.

P in H: PtEll, SetPtEll -> BoolElt: Given a point \(P\), return true if and only if \(P\) is in the point set \(H\). That is, it satisfies the equation of \(E\) and its coordinates lie in \(R\), where \(H = E(R)\).

P in E: PtEll, CrvEll -> BoolElt: Given a point \(P\), return true if and only if \(P\) is on the elliptic curve \(E\) (i.e., satisfies its defining equation). Note that this is an exception to the general rule, in that \(P\) does not have to lie in the base point set of \(E\) for this to be true.

IsOrder(P, m): PtEll, RngIntElt -> BoolElt: Returns true if and only if the point \(P\) has order \(m\). If you believe that you know the order of the point then this intrinsic is likely to be much faster than just calling Order.

IsIntegral(P): PtEll -> BoolElt: Given a point \(P\) on an elliptic curve defined over \({\mathbb{Q}}\), this function returns true if and only if the coordinates of the (normalisation of) \(P\) are integers.

IsSIntegral(P, S): PtEll, SeqEnum -> BoolElt: Given a point \(P\) on an elliptic curve defined over \({\mathbb{Q}}\) and a sequence \(S\) of primes, this function returns true if and only if the coordinates of the (normalisation of) \(P\) are \(S\)-integers. That is, the denominators of \(x(P)\) and \(y(P)\) are only supported by primes of \(S\).

Example: Integral and S-Integral Points (ex-e572c3)

Run in calculator (opens in a new tab)

We find some integral and \(S\)-integral points on a well-known elliptic curve.

> E := EllipticCurve([0, 17]);
> P1 := E![ -2, 3 ];
> P2 := E![ -1, 4 ];
> S := [ a*P1 + b*P2 : a,b in [-3..3] ];
> #S;
49
> [ P : P in S | IsIntegral(P) ];
[ (43 : -282 : 1), (5234 : -378661 : 1), (2 : -5 : 1), (8 : 23 : 1),
(4 : 9 : 1), (-2 : -3 : 1), (52 : -375 : 1), (-1 : -4 : 1), (-1 : 4 : 1),
(52 : 375 : 1), (-2 : 3 : 1), (4 : -9 : 1), (8 : -23 : 1), (2 : 5 : 1),
(5234 : 378661 : 1), (43 : 282 : 1) ]
> [ P : P in S | IsSIntegral(P, [2, 3]) and not IsIntegral(P) ];
[ (1/4 : 33/8 : 1), (-8/9 : 109/27 : 1), (-206/81 : -541/729 : 1),
(137/64 : 2651/512 : 1), (137/64 : -2651/512 : 1), (-206/81 : 541/729 : 1),
(-8/9 : -109/27 : 1), (1/4 : -33/8 : 1) ]

Run in calculator (opens in a new tab)

Weil Pairing

Magma contains an optimised implementation of the Weil pairing on an elliptic curve. This function is used in the computation of the group structure of elliptic curves over finite fields, making the determination of the group structure efficient.

WeilPairing(P, Q, n): PtEll, PtEll, RngIntElt -> RngElt: Given \(n\)-torsion points \(P\) and \(Q\) of an elliptic curve \(E\), this function computes the Weil pairing of \(P\) and \(Q\).

IsLinearlyIndependent(S, n): [ PtEll ], RngIntElt -> BoolElt: Given a sequence \(S\) of points of an elliptic curve \(E\) such that each point has order dividing \(n\), this function returns true if and only if the points in \(S\) are linearly independent over \({\mathbb{Z}}/n{\mathbb{Z}}\).

IsLinearlyIndependent(P, Q, n): PtEll, PtEll, RngIntElt -> BoolElt: Given points \(P\) and \(Q\) of an elliptic curve \(E\), this function returns true if and only if \(P\) and \(Q\) form a basis of the \(n\)-torsion points of \(E\).

Example: Weil Pairing of 3-Torsion Points (ex-c9a88c)

Run in calculator (opens in a new tab)

We compute the Weil pairing of two \(3\)-torsion points on the curve \(y^2 = x^3 - 3\) over \({\mathbb{Q}}\).

> E := EllipticCurve([0, -3]);
> E;
> P1, P2, P3 := Explode(ThreeTorsionPoints(E));
> P1;
(0 : 2*zeta_3 + 1 : 1)
> Parent(P1);
Set of points of E with coordinates in Cyclotomic Field
  of order 3 and degree 2
> Parent(P2);
Set of points of E with coordinates in Number Field with
  defining polynomial X^3 - 18*X - 30 over the Rational Field

In order to take the Weil pairing of two points we need to coerce them into the same point set. This turns out to be a point set over a number field \(K\) of degree \(6\).

> Qmu3 := Ring(Parent(P1));
> K<w> := CompositeFields(Ring(Parent(P1)), Ring(Parent(P2)))[1];
> wp := WeilPairing( E(K)!P1, E(K)!P2, 3 );
> wp;
1/975*(14*w^5 + 5*w^4 - 410*w^3 - 620*w^2 + 3964*w + 8744)
> Qmu3!wp;
zeta_3

Run in calculator (opens in a new tab)

Operations on Points#

Creation of Points#

Creation Predicates#

Access Operations#

Associated Structures#

Arithmetic#

Division Points#

Point Order#

Predicates on Points#

Weil Pairing#

Operations on Points

Creation of Points

Creation Predicates

Access Operations

Associated Structures

Arithmetic

Division Points

Point Order

Predicates on Points

Weil Pairing