Bound: RngInt Default: 0
Given a Jacobian J of a hyperelliptic curve defined over a finite field or the rationals, determine all rational points on the Jacobian J. In the case where the base field is Q, the corresponding curve must have genus two and be of the form y^2 = f(x), where f has integral coefficients. Furthermore, the parameter Bound must be given, bounding the naive height.
Find all points on J with first component a and degree d. So far only for genus 2 and curves of the form y^2 = f(x).
Several algorithms are used to compute the order of a Jacobian depending of its size, its genus and its type. In particular, in genus 2 it includes all the techniques described in [GH00]. A verbose flag can be set to see which strategy is chosen and the progress of the computation.
Set the verbose printing level for the point-counting on the Jacobians. Currently the legal values for v are true, false, 0, 1, 2 or 3 (false is the same as 0, and true is the same as 1).
Given the Jacobian J of a hyperelliptic curve defined over a finite field, determine the order of the group of rational points.
There are 4 optional parameters which concern every genus.
NaiveAlg: BoolElt Default: false
ShanksLimit: RngIntElt Default: 10^(12)
CartierManinLimit: RngIntElt Default: 5 x 10^5
UseSubexpAlg: BoolElt Default: trueThe parameter NaiveAlg can be set to one if one want to use the naive algorithm for point counting, consisting in counting points on the curve over the first g extensions, where g is the genus. Setting this parameter to true annihilates the effects of the others. By default, this strategy is used for small groups and Jacobians for which no group law is available.
The parameter ShanksLimit determines when we switch from a memory-consuming Shanks' algorithm to a slower Pollard's method. The value of the parameter CartierManinLimit is the maximal characteristic for which we may use the Cartier-Manin trick (see function EulerFactorModChar below).
When the genus is high compared to the size of the base field, the best known method is a subexponential algorithm. For this, we use the generic machinery of the function fields. This functionality can be disabled by setting UseSubexpAlg to false.
The next 2 parameters are used only for genus 2 curves in odd characteristic.
UseSchoof: BoolElt Default: true
UseHalving: BoolElt Default: trueWhen the base field is large enough, it is better to firstly compute the cardinality of the Jacobian modulo some odd primes and some power of two. These two parameters allow the user to disable one or both of these methods.
Comparison between Shanks and Pollard:
> P<x> := PolynomialRing(GF(1000003)); > f := x^7 + 123456*x^6 + 123*x^5 + 456*x^4 + 98*x^3 + 76*x^2 + 54*x + 32; > J := Jacobian(HyperellipticCurve(f)); > curr_mem := GetMemoryUsage(); ResetMaximumMemoryUsage(); > time Order(J : ShanksLimit := 10^15); 1001800207033014252 Time: 180.420 > GetMaximumMemoryUsage()-curr_mem; 103520512
The computation took about 100 MB of central memory.
> delete J`Order; // clear the result which has been stored > curr_mem := GetMemoryUsage(); > ResetMaximumMemoryUsage(); > time Order(J : ShanksLimit := 0); 1001800207033014252 Time: 592.370 > GetMaximumMemoryUsage()-curr_mem; 0
Now it takes almost no memory, but it is slower (and runtime may vary a lot).
In genus 2, usually UseSchoof and UseHalving do help:
> P<x> := PolynomialRing(GF(100000007)); > f := x^5 + 456*x^4 + 98*x^3 + 76*x^2 + 54*x + 32; > J := Jacobian(HyperellipticCurve(f)); > time Order(J); 10001648178050390 Time: 66.860 > delete J`Order; > time Order(J: UseSchoof := false, UseHalving := false); 10001648178050390 Time: 300.720
But if you know in advance that the Jacobian is highly non--cyclic, it may be slightly better to switch them off. The Jacobian below is the direct product of two times the same supersingular elliptic curve.
> P<x> := PolynomialRing(GF(500083)); > f := x^5 + 250039*x^4 + 222262*x^3 + 416734*x^2 + 166695*x + 222259; > J := Jacobian(HyperellipticCurve(f)); > time Order(J); 250084007056 Time: 22.460 > delete J`Order; > time Order(J : UseSchoof:=false, UseHalving := false); 250084007056 Time: 21.269
Given the Jacobian J of a hyperelliptic curve defined over a finite field, returns the factorization of the order of the group of rational points.
Given the Jacobian J of a hyperelliptic curve defined over a finite field, returns the Euler factor J, i.e. the reciprocal of the characteristic polynomial of Frobenius acting on H^1(J).
Given the Jacobian J of a hyperelliptic curve defined over a finite field, returns the Euler factor J modulo the characteristic of the base field. This function should not be used in high characteristic (say p should be <= 10^6).
Given a Jacobian J of a hyperelliptic curve defined over the rationals and a finite field K at which J has good reduction, returns the Euler factor of the base extension of J to K.
Given the Jacobian J of a genus 2 curve C, where C is given in the form of a simplified model, this function returns the rational 2-torsion subgroup of the group of rational points of J.
Given the Jacobian J of a hyperelliptic curve defined over the rationals, this function returns a bound on the size of the rational torsion subgroup of the Jacobian. The bound is obtained by examining the first n good primes.
Given the Jacobian J of a genus 2 curve defined over the rationals, this function returns the rational torsion subgroup of J, and the map from the group into J. The curve must have the form y^2 = f(x) with integral coefficients.
Given the Jacobian J of a hyperelliptic curve defined over a finite field and a prime p, this function returns the Sylow p-subgroup of the group of rational points of J, as an abstract abelian group A. The injection from A to J is also returned as well as the generators of the p-Sylow subgroup.
UseGenerators: Bool Default: false
Generators: SetEnum Default:
Given the Jacobian J of a hyperelliptic curve defined over a finite field K, this function returns the group of rational points of J as an abstract abelian group A. The isomorphism from A to J(K) is returned as a second value.
If UseGenerators is set then the group structure computation is achieved by extracting relations from the user-supplied set of generators in Generators.
> Px<x> := PolynomialRing(Rationals());
> C := HyperellipticCurve(&*[x-n : n in [-3..2]]);
> J := Jacobian(C);
> T, m := TwoTorsionSubgroup(J);
> T;
Abelian Group isomorphic to Z/2 + Z/2 + Z/2 + Z/2
Defined on 4 generators
Relations:
2*P[1] = 0
2*P[2] = 0
2*P[3] = 0
2*P[4] = 0
> [ m(T.i) : i in [1..4] ];
[ (x^2 - 3*x + 2, 0, 2), (x^2 - 2*x, 0, 2), (x^2 - x - 2, 0, 2),
(x^2 - 4, 0, 2) ]
> #T eq #TorsionSubgroup(J);
true
And here is a curve where that is not the case:
> C := HyperellipticCurve((2*x^2-2*x-1)*(2*x^4-10*x^3+7*x^2+4*x-4));
> J := Jacobian(C);
> T, m := TwoTorsionSubgroup(J);
> T;
Abelian Group isomorphic to Z/2
Defined on 1 generator
Relations:
2*P[1] = 0
> m(T.1);
(x^2 - x - 1/2, 0, 2)
> A,h := TorsionSubgroup(J);
> #T eq #A;
false
> A;
Abelian Group isomorphic to Z/24
Defined on 1 generator
Relations:
24*P[1] = 0
> P := h(A.1);
> P;
(x^2 - 1/2, -1, 2)
> Order(P);
24
> 12 * P eq m(T.1);
true;