|
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.
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) : SetPtEll -> {@ PtEll @}
RationalPoints(H) : SetPtEll -> {@ PtEll @}
Points(E) : CrvEll -> {@ PtEll @}
RationalPoints(E) : CrvEll -> {@ PtEll @}
var Bound: RngIntElt Default: 0
var DenominatorBound: RngIntElt Default: Bound
var Denominators: Setq Default:
var Max: RngIntElt Default:
var 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 Q or a number field, a positive value for the parameter
Bound must be given. Over 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.
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.
PointsAtInfinity(E) : CrvEll -> @ PtEll @
Returns the indexed set containing the identity point of the pointset
H or on the elliptic curve E.
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(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.
Returns the i-th coefficient for an elliptic curve point P, for
1≤i≤3.
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).
Type(P) : PtEll -> Cat
Given a point P on an elliptic curve, this function
returns PtEll, the category of elliptic curve points.
Given a point P on an elliptic curve, this function
returns the parent point set for P.
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.
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).
Returns the additive inverse of the point P on an elliptic curve E.
Returns the sum P + Q of
two points P and Q on the same elliptic curve.
Given two points P and Q on the same elliptic curve, sets P
equal to their sum.
Returns the difference P - Q of two points P and Q on the same
elliptic curve.
Given two points P and Q on the same elliptic curve, sets P
equal to
their difference.
P * n : PtEll, RngIntElt -> PtEll
Returns the n-th multiple of the point P on an elliptic curve.
Sets the point P equal to the n-th multiple of itself.
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.
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.
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.
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.
> 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) ]
We construct some points in a certain elliptic curve over 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.
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)
Given a point on an elliptic curve defined over Q or a finite
field, this function computes the order of P; that is, the smallest
positive integer n such that n.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.
Given a point on an elliptic curve defined over 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 Q and P
has infinite order.
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> ]
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.
Returns true if and only if P and Q are points on the same elliptic curve
and have the same normalised coordinates.
The logical negation of eq.
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).
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.
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.
Given a point P on an elliptic curve defined over Q, this function
returns true if and only if the coordinates of the (normalisation of) P
are integers.
Given a point P on an elliptic curve defined over 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.
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) ]
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.
Given n-torsion points P and Q of an elliptic curve E,
this function computes the Weil pairing of P and Q.
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 Z/nZ.
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.
We compute the Weil pairing of two 3-torsion points on the curve
y 2 = x 3 - 3 over 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
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|