|
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
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 normalized if either
z=1, or z=0 and y=1.
Subsections
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 normalized 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
Return the normalized 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 NPrimes: RngIntElt Default: 30
var DenominatorBound: RngIntElt Default: Bound
Given a point set H or an elliptic curve E
over the rationals, a number field or a finite field, an indexed
set of the rational points in the set is returned. If the point set is over
the rationals or a number field, then a positive value for the parameter
Bound must be
given; this function then returns those points whose naive height is bounded
by Bound.
If E is over a number field, the parameters NPrimes and
DenominatorBound may be given. The parameter NPrimes controls
the number of primes which are used and DenominatorBound
the size of the denominators used. A sieve method, described in
Appendix A of [Bru02], is used.
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.
Access 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 (normalized).
Type(P) : PtEll -> Cat
Given a point P on an elliptic curve, this function
returns the category of elliptic curve points, PtEll.
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 or scheme, 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).
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, set 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, set P
equal to
their difference.
P * n : PtEll, RngIntElt -> PtEll
Returns the n-th multiple of the point P on an elliptic curve.
Set 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 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 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, 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, 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 factorization of the order of P.
If the curve is over a finite field then on repeated applications
this is generally much faster than factorizing Order(P) because
the factorization 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 normalized 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 (normalization 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 (normalization 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 optimized 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
y2 = x3 - 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]
|
