### Functions related to elliptic curves

#### Elliptic curve structures

An elliptic curve is given by a Weierstrass model

y^2+a_1xy+a_3y = x^3+a_2x^2+a_4x+a_6,

whose discriminant is non-zero. Affine points on E are represented as two-component vectors [x,y]; the point at infinity, i.e. the identity element of the group law, is represented by the one-component vector [0].

Given a vector of coefficients [a_1,a_2,a_3,a_4,a_6], the function ellinit initializes and returns an ell structure. (An additional optional argument allows to specify the base field in case it cannot be inferred from the curve coefficients.) This structure contains data needed by elliptic curve related functions, and is generally passed as a first argument. Expensive data are skipped on initialization: they will be dynamically computed when (and if) needed, and then inserted in the structure. The precise layout of the ell structure is left undefined and should never be used directly. The following member functions are available, depending on the underlying domain.

#### ellL1(e, r)

Returns the value at s = 1 of the derivative of order r of the L-function of the elliptic curve e assuming that r is at most the order of vanishing of the L-function at s = 1. (The result is wrong if r is strictly larger than the order of vanishing at 1.)

  ? e = ellinit("11a1"); \\ order of vanishing is 0
? ellL1(e, 0)
%2 = 0.2538418608559106843377589233
? e = ellinit("389a1");  \\ order of vanishing is 2
? ellL1(e, 0)
%4 = -5.384067311837218089235032414 E-29
? ellL1(e, 1)
%5 = 0
? ellL1(e, 2)
%6 = 1.518633000576853540460385214


The main use of this function, after computing at low accuracy the order of vanishing using ellanalyticrank, is to compute the leading term at high accuracy to check (or use) the Birch and Swinnerton-Dyer conjecture:

  ? \p18
realprecision = 18 significant digits
? ellanalyticrank(ellinit([0, 0, 1, -7, 6]))
time = 32 ms.
%1 = [3, 10.3910994007158041]
? \p200
realprecision = 202 significant digits (200 digits displayed)
? ellL1(e, 3)
time = 23,113 ms.
%3 = 10.3910994007158041387518505103609170697263563756570092797 [...]


The library syntax is GEN ellL1(GEN e, long r, long prec).

Sum of the points z1 and z2 on the elliptic curve corresponding to E.

The library syntax is GEN elladd(GEN E, GEN z1, GEN z2).

#### ellak(E,n)

Computes the coefficient a_n of the L-function of the elliptic curve E/Q, i.e. coefficients of a newform of weight 2 by the modularity theorem (Taniyama-Shimura-Weil conjecture). E must be an ell structure over Q as output by ellinit. E must be given by an integral model, not necessarily minimal, although a minimal model will make the function faster.

  ? E = ellinit([0,1]);
? ellak(E, 10)
%2 = 0
? e = ellinit([5^4,5^6]); \\ not minimal at 5
? ellak(e, 5) \\ wasteful but works
%3 = -3
? E = ellminimalmodel(e); \\ now minimal
? ellak(E, 5)
%5 = -3

If the model is not minimal at a number of bad primes, then the function will be slower on those n divisible by the bad primes. The speed should be comparable for other n:

  ? for(i=1,10^6, ellak(E,5))
time = 820 ms.
? for(i=1,10^6, ellak(e,5)) \\ 5 is bad, markedly slower
time = 1,249 ms.

? for(i=1,10^5,ellak(E,5*i))
time = 977 ms.
? for(i=1,10^5,ellak(e,5*i)) \\ still slower but not so much on average
time = 1,008 ms.


The library syntax is GEN akell(GEN E, GEN n).

#### ellan(E,n)

Computes the vector of the first n Fourier coefficients a_k corresponding to the elliptic curve E. The curve must be given by an integral model, not necessarily minimal, although a minimal model will make the function faster.

The library syntax is GEN anell(GEN E, long n). Also available is GEN anellsmall(GEN e, long n), which returns a t_VECSMALL instead of a t_VEC, saving on memory.

#### ellanalyticrank(e, {eps})

Returns the order of vanishing at s = 1 of the L-function of the elliptic curve e and the value of the first non-zero derivative. To determine this order, it is assumed that any value less than eps is zero. If no value of eps is given, a value of half the current precision is used.

  ? e = ellinit("11a1"); \\ rank 0
? ellanalyticrank(e)
%2 = [0, 0.2538418608559106843377589233]
? e = ellinit("37a1"); \\ rank 1
? ellanalyticrank(e)
%4 = [1, 0.3059997738340523018204836835]
? e = ellinit("389a1"); \\ rank 2
? ellanalyticrank(e)
%6 = [2, 1.518633000576853540460385214]
? e = ellinit("5077a1"); \\ rank 3
? ellanalyticrank(e)
%8 = [3, 10.39109940071580413875185035]


The library syntax is GEN ellanalyticrank(GEN e, GEN eps = NULL, long prec).

#### ellap(E,{p})

Let E be an ell structure as output by ellinit, defined over Q or a finite field F_q. The argument p is best left omitted if the curve is defined over a finite field, and must be a prime number otherwise. This function computes the trace of Frobenius t for the elliptic curve E, defined by the equation #E(F_q) = q+1 - t.

If the curve is defined over Q, p must be explicitly given and the function computes the trace of the reduction over F_p. The trace of Frobenius is also the a_p coefficient in the curve L-series L(E,s) = sum_n a_n n^{-s}, whence the function name. The equation must be integral at p but need not be minimal at p; of course, a minimal model will be more efficient.

  ? E = ellinit([0,1]);  \\ y^2 = x^3 + 0.x + 1, defined over Q
? ellap(E, 7) \\ 7 necessary here
%2 = -4       \\ #E(F_7) = 7+1-(-4) = 12
? ellcard(E, 7)
%3 = 12       \\ OK

? E = ellinit([0,1], 11);  \\ defined over F_11
? ellap(E)       \\ no need to repeat 11
%4 = 0
? ellap(E, 11)   \\ ... but it also works
%5 = 0
? ellgroup(E, 13) \\ ouch, inconsistent input!
***   at top-level: ellap(E,13)
***                 ^-----------
*** ellap: inconsistent moduli in Rg_to_Fp:
11
13

? Fq = ffgen(ffinit(11,3), 'a); \\ defines F_q := F_{11^3}
? E = ellinit([a+1,a], Fq);  \\ y^2 = x^3 + (a+1)x + a, defined over F_q
? ellap(E)
%8 = -3


Algorithms used. If E/F_q has CM by a principal imaginary quadratic order we use a fast explicit formula (involving essentially Kronecker symbols and Cornacchia's algorithm), in O(log q)^2. Otherwise, we use Shanks-Mestre's baby-step/giant-step method, which runs in time q(p^{1/4}) using O(q^{1/4}) storage, hence becomes unreasonable when q has about 30 digits. If the seadata package is installed, the SEA algorithm becomes available, heuristically in Õ(log q)^4, and primes of the order of 200 digits become feasible. In very small characteristic (2,3,5,7 or 13), we use Harley's algorithm.

The library syntax is GEN ellap(GEN E, GEN p = NULL).

#### ellbil(E,z1,z2)

If z1 and z2 are points on the elliptic curve E, assumed to be integral given by a minimal model, this function computes the value of the canonical bilinear form on z1, z2: ( h(E,z1+z2) - h(E,z1) - h(E,z2) ) / 2 where + denotes of course addition on E. In addition, z1 or z2 (but not both) can be vectors or matrices.

The library syntax is GEN bilhell(GEN E, GEN z1, GEN z2, long prec).

#### ellcard(E,{p})

Let E be an ell structure as output by ellinit, defined over Q or a finite field F_q. The argument p is best left omitted if the curve is defined over a finite field, and must be a prime number otherwise. This function computes the order of the group E(F_q) (as would be computed by ellgroup).

If the curve is defined over Q, p must be explicitly given and the function computes the cardinal of the reduction over F_p; the equation need not be minimal at p, but a minimal model will be more efficient. The reduction is allowed to be singular, and we return the order of the group of non-singular points in this case.

The library syntax is GEN ellcard(GEN E, GEN p = NULL). Also available is GEN ellcard(GEN E, GEN p) where p is not NULL.

#### ellchangecurve(E,v)

Changes the data for the elliptic curve E by changing the coordinates using the vector v = [u,r,s,t], i.e. if x' and y' are the new coordinates, then x = u^2x'+r, y = u^3y'+su^2x'+t. E must be an ell structure as output by ellinit. The special case v = 1 is also used instead of [1,0,0,0] to denote the trivial coordinate change.

The library syntax is GEN ellchangecurve(GEN E, GEN v).

#### ellchangepoint(x,v)

Changes the coordinates of the point or vector of points x using the vector v = [u,r,s,t], i.e. if x' and y' are the new coordinates, then x = u^2x'+r, y = u^3y'+su^2x'+t (see also ellchangecurve).

  ? E0 = ellinit([1,1]); P0 = [0,1]; v = [1,2,3,4];
? E = ellchangecurve(E0, v);
? P = ellchangepoint(P0,v)
%3 = [-2, 3]
? ellisoncurve(E, P)
%4 = 1
? ellchangepointinv(P,v)
%5 = [0, 1]


The library syntax is GEN ellchangepoint(GEN x, GEN v). The reciprocal function GEN ellchangepointinv(GEN x, GEN ch) inverts the coordinate change.

#### ellchangepointinv(x,v)

Changes the coordinates of the point or vector of points x using the inverse of the isomorphism associated to v = [u,r,s,t], i.e. if x' and y' are the old coordinates, then x = u^2x'+r, y = u^3y'+su^2x'+t (inverse of ellchangepoint).

  ? E0 = ellinit([1,1]); P0 = [0,1]; v = [1,2,3,4];
? E = ellchangecurve(E0, v);
? P = ellchangepoint(P0,v)
%3 = [-2, 3]
? ellisoncurve(E, P)
%4 = 1
? ellchangepointinv(P,v)
%5 = [0, 1]  \\ we get back P0


The library syntax is GEN ellchangepointinv(GEN x, GEN v).

#### ellconvertname(name)

Converts an elliptic curve name, as found in the elldata database, from a string to a triplet [conductor, isogeny class, index]. It will also convert a triplet back to a curve name. Examples:

  ? ellconvertname("123b1")
%1 = [123, 1, 1]
? ellconvertname(%)
%2 = "123b1"


The library syntax is GEN ellconvertname(GEN name).

#### elldivpol(E,n,{v = 'x})

n-division polynomial f_n for the curve E in the variable v. In standard notation, for any affine point P = (X,Y) on the curve, we have [n]P = (phi_n(P)psi_n(P) : omega_n(P) : psi_n(P)^3) for some polynomials phi_n,omega_n,psi_n in Z[a_1,a_2,a_3,a_4,a_6][X,Y]. We have f_n(X) = psi_n(X) for n odd, and f_n(X) = psi_n(X,Y) (2Y + a_1X+a_3) for n even. We have f_1 = 1, f_2 = 4X^3 + b_2X^2 + 2b_4 X + b_6, f_3 = 3 X^4 + b_2 X^3 + 3b_4 X^2 + 3 b_6 X + b8, f_4 = f_2(2X^6 + b_2 X^5 + 5b_4 X^4 + 10 b_6 X^3 + 10 b_8 X^2 + (b_2b_8-b_4b_6)X + (b_8b_4 - b_6^2)),... For n >= 2, the roots of f_n are the X-coordinates of points in E[n].

The library syntax is GEN elldivpol(GEN E, long n, long v = -1), where v is a variable number.

#### elleisnum(w,k,{flag = 0})

k being an even positive integer, computes the numerical value of the Eisenstein series of weight k at the lattice w, as given by ellperiods, namely

(2i Pi/omega_2)^k (1 + 2/zeta(1-k) sum_{n >= 0} n^{k-1}q^n / (1-q^n)),

where q = exp(2iPi tau) and tau := omega_1/omega_2 belongs to the complex upper half-plane. It is also possible to directly input w = [omega_1,omega_2], or an elliptic curve E as given by ellinit.

  ? w = ellperiods([1,I]);
? elleisnum(w, 4)
%2 = 2268.8726415508062275167367584190557607
? elleisnum(w, 6)
%3 = -3.977978632282564763 E-33
? E = ellinit([1, 0]);
? elleisnum(E, 4, 1)
%5 = -47.999999999999999999999999999999999998


When flag is non-zero and k = 4 or 6, returns the elliptic invariants g_2 or g_3, such that y^2 = 4x^3 - g_2 x - g_3 is a Weierstrass equation for E.

The library syntax is GEN elleisnum(GEN w, long k, long flag, long prec).

#### elleta(w)

Returns the quasi-periods [eta_1,eta_2] associated to the lattice basis w = [omega_1, omega_2]. Alternatively, w can be an elliptic curve E as output by ellinit, in which case, the quasi periods associated to the period lattice basis E.omega (namely, E.eta) are returned.

  ? elleta([1, I])
%1 = [3.141592653589793238462643383, 9.424777960769379715387930149*I]


The library syntax is GEN elleta(GEN w, long prec).

#### ellfromj(j)

Returns the coefficients [a_1,a_2,a_3,a_4,a_6] of a fixed elliptic curve with j-invariant j.

The library syntax is GEN ellfromj(GEN j).

#### ellgenerators(E)

If E is an elliptic curve over the rationals, return a Z-basis of the free part of the Mordell-Weil group associated to E. This relies on the elldata database being installed and referencing the curve, and so is only available for curves over Z of small conductors. If E is an elliptic curve over a finite field F_q as output by ellinit, return a minimal set of generators for the group E(F_q).

The library syntax is GEN ellgenerators(GEN E).

#### ellglobalred(E)

Calculates the arithmetic conductor, the global minimal model of E and the global Tamagawa number c. E must be an ell structure as output by ellinit, defined over Q. The result is a vector [N,v,c,F,L], where

* N is the arithmetic conductor of the curve,

* v gives the coordinate change for E over Q to the minimal integral model (see ellminimalmodel),

* c is the product of the local Tamagawa numbers c_p, a quantity which enters in the Birch and Swinnerton-Dyer conjecture,

* F is the factorization of N over Z.

* L is a vector, whose i-th entry contains the local data at the i-th prime divisor of N, i.e. L[i] = elllocalred(E,F[i,1]), where the local coordinate change has been deleted, and replaced by a 0.

The library syntax is GEN ellglobalred(GEN E).

#### ellgroup(E,{p},{flag})

Let E be an ell structure as output by ellinit, defined over Q or a finite field F_q. The argument p is best left omitted if the curve is defined over a finite field, and must be a prime number otherwise. This function computes the structure of the group E(F_q) ~ Z/d_1Z x Z/d_2Z, with d_2 | d_1.

If the curve is defined over Q, p must be explicitly given and the function computes the structure of the reduction over F_p; the equation need not be minimal at p, but a minimal model will be more efficient. The reduction is allowed to be singular, and we return the structure of the (cyclic) group of non-singular points in this case.

If the flag is 0 (default), return [d_1] or [d_1, d_2], if d_2 > 1. If the flag is 1, return a triple [h,cyc,gen], where h is the curve cardinality, cyc gives the group structure as a product of cyclic groups (as per flag = 0). More precisely, if d_2 > 1, the output is [d_1d_2, [d_1,d_2],[P,Q]] where P is of order d_1 and [P,Q] generates the curve. Caution. It is not guaranteed that Q has order d_2, which in the worst case requires an expensive discrete log computation. Only that ellweilpairing(E, P, Q, d1) has order d_2.

  ? E = ellinit([0,1]);  \\ y^2 = x^3 + 0.x + 1, defined over Q
? ellgroup(E, 7)
%2 = [6, 2] \\ Z/6 x Z/2, non-cyclic
? E = ellinit([0,1] * Mod(1,11));  \\ defined over F_11
? ellgroup(E)   \\ no need to repeat 11
%4 = [12]
? ellgroup(E, 11)   \\ ... but it also works
%5 = [12]
? ellgroup(E, 13) \\ ouch, inconsistent input!
***   at top-level: ellgroup(E,13)
***                 ^--------------
*** ellgroup: inconsistent moduli in Rg_to_Fp:
11
13
? ellgroup(E, 7, 1)
%6 = [12, [6, 2], [[Mod(2, 7), Mod(4, 7)], [Mod(4, 7), Mod(4, 7)]]]


If E is defined over Q, we allow singular reduction and in this case we return the structure of the group of non-singular points, satisfying #E_{ns}(F_p) = p - a_p.

  ? E = ellinit([0,5]);
? ellgroup(E, 5, 1)
%2 = [5, [5], [[Mod(4, 5), Mod(2, 5)]]]
? ellap(E, 5)
%3 = 0 \\ additive reduction at 5
? E = ellinit([0,-1,0,35,0]);
? ellgroup(E, 5, 1)
%5 = [4, [4], [[Mod(2, 5), Mod(2, 5)]]]
? ellap(E, 5)
%6 = 1 \\ split multiplicative reduction at 5
? ellgroup(E, 7, 1)
%7 = [8, [8], [[Mod(3, 7), Mod(5, 7)]]]
? ellap(E, 7)
%8 = -1 \\ non-split multiplicative reduction at 7


The library syntax is GEN ellgroup0(GEN E, GEN p = NULL, long flag). Also available is GEN ellgroup(GEN E, GEN p), corresponding to flag = 0.

#### ellheegner(E)

Let E be an elliptic curve over the rationals, assumed to be of (analytic) rank 1. This returns a non-torsion rational point on the curve, whose canonical height is equal to the product of the elliptic regulator by the analytic Sha.

This uses the Heegner point method, described in Cohen GTM 239; the complexity is proportional to the product of the square root of the conductor and the height of the point (thus, it is preferable to apply it to strong Weil curves).

  ? E = ellinit([-157^2,0]);
? u = ellheegner(E); print(u[1], "\n", u[2])
69648970982596494254458225/166136231668185267540804
538962435089604615078004307258785218335/67716816556077455999228495435742408
? ellheegner(ellinit([0,1]))         \\ E has rank 0 !
***   at top-level: ellheegner(E=ellinit
***                 ^--------------------
*** ellheegner: The curve has even analytic rank.


The library syntax is GEN ellheegner(GEN E).

#### ellheight(E,x,{flag = 2})

Global Néron-Tate height of the point z on the elliptic curve E (defined over Q), using the normalization in Cremona's Algorithms for modular elliptic curves. E must be an ell as output by ellinit; it needs not be given by a minimal model although the computation will be faster if it is. flag selects the algorithm used to compute the Archimedean local height. If flag = 0, we use sigma and theta-functions and Silverman's trick (Computing heights on elliptic curves, Math. Comp. 51; note that Silverman's height is twice ours). If flag = 1, use Tate's 4^n algorithm. If flag = 2, use Mestre's AGM algorithm. The latter converges quadratically and is much faster than the other two.

The library syntax is GEN ellheight0(GEN E, GEN x, long flag, long prec). Also available is GEN ghell(GEN E, GEN x, long prec) (flag = 2).

#### ellheightmatrix(E,x)

x being a vector of points, this function outputs the Gram matrix of x with respect to the Néron-Tate height, in other words, the (i,j) component of the matrix is equal to ellbil(E,x[i],x[j]). The rank of this matrix, at least in some approximate sense, gives the rank of the set of points, and if x is a basis of the Mordell-Weil group of E, its determinant is equal to the regulator of E. Note that this matrix should be divided by 2 to be in accordance with certain normalizations. E is assumed to be integral, given by a minimal model.

The library syntax is GEN mathell(GEN E, GEN x, long prec).

#### ellidentify(E)

Look up the elliptic curve E, defined by an arbitrary model over Q, in the elldata database. Return [[N, M, G], C] where N is the curve name in Cremona's elliptic curve database, M is the minimal model, G is a Z-basis of the free part of the Mordell-Weil group E(Q) and C is the change of coordinates change, suitable for ellchangecurve.

The library syntax is GEN ellidentify(GEN E).

#### ellinit(x,{D = 1})

Initialize an ell structure, associated to the elliptic curve E. E is either

* a 5-component vector [a_1,a_2,a_3,a_4,a_6] defining the elliptic curve with Weierstrass equation Y^2 + a_1 XY + a_3 Y = X^3 + a_2 X^2 + a_4 X + a_6,

* a 2-component vector [a_4,a_6] defining the elliptic curve with short Weierstrass equation Y^2 = X^3 + a_4 X + a_6,

* a character string in Cremona's notation, e.g. "11a1", in which case the curve is retrieved from the elldata database if available.

The optional argument D describes the domain over which the curve is defined:

* the t_INT 1 (default): the field of rational numbers Q.

* a t_INT p, where p is a prime number: the prime finite field F_p.

* an t_INTMOD Mod(a, p), where p is a prime number: the prime finite field F_p.

* a t_FFELT, as returned by ffgen: the corresponding finite field F_q.

* a t_PADIC, O(p^n): the field Q_p, where p-adic quantities will be computed to a relative accuracy of n digits. We advise to input a model defined over Q for such curves. In any case, if you input an approximate model with t_PADIC coefficients, it will be replaced by a lift to Q (an exact model "close" to the one that was input) and all quantities will then be computed in terms of this lifted model, at the given accuracy.

* a t_REAL x: the field C of complex numbers, where floating point quantities are by default computed to a relative accuracy of precision(x). If no such argument is given, the value of realprecision at the time ellinit is called will be used.

This argument D is indicative: the curve coefficients are checked for compatibility, possibly changing D; for instance if D = 1 and an t_INTMOD is found. If inconsistencies are detected, an error is raised:

  ? ellinit([1 + O(5), 1], O(7));
***   at top-level: ellinit([1+O(5),1],O
***                 ^--------------------
*** ellinit: inconsistent moduli in ellinit: 7 != 5

If the curve coefficients are too general to fit any of the above domain categories, only basic operations, such as point addition, will be supported later.

If the curve (seen over the domain D) is singular, fail and return an empty vector [].

  ? E = ellinit([0,0,0,0,1]); \\ y^2 = x^3 + 1, over Q
? E = ellinit([0,1]);       \\ the same curve, short form
? E = ellinit("36a1");      \\ sill the same curve, Cremona's notations
? E = ellinit([0,1], 2)     \\ over F2: singular curve
%4 = []
? E = ellinit(['a4,'a6] * Mod(1,5));  \\ over F_5[a4,a6], basic support !


The result of ellinit is an ell structure. It contains at least the following information in its components:

a_1,a_2,a_3,a_4,a_6,b_2,b_4,b_6,b_8,c_4,c_6,Delta,j.

All are accessible via member functions. In particular, the discriminant is E.disc, and the j-invariant is E.j.

  ? E = ellinit([a4, a6]);
? E.disc
%2 = -64*a4^3 - 432*a6^2
? E.j
%3 = -6912*a4^3/(-4*a4^3 - 27*a6^2)


Further components contain domain-specific data, which are in general dynamic: only computed when needed, and then cached in the structure.

  ? E = ellinit([2,3], 10^60+7);  \\ E over F_p, p large
? ellap(E)
time = 4,440 ms.
%2 = -1376268269510579884904540406082
? ellcard(E);  \\ now instantaneous !
time = 0 ms.
? ellgenerators(E);
time = 5,965 ms.
? ellgenerators(E); \\ second time instantaneous
time = 0 ms.


See the description of member functions related to elliptic curves at the beginning of this section.

The library syntax is GEN ellinit(GEN x, GEN D = NULL, long prec).

#### ellisoncurve(E,z)

Gives 1 (i.e. true) if the point z is on the elliptic curve E, 0 otherwise. If E or z have imprecise coefficients, an attempt is made to take this into account, i.e. an imprecise equality is checked, not a precise one. It is allowed for z to be a vector of points in which case a vector (of the same type) is returned.

The library syntax is GEN ellisoncurve(GEN E, GEN z). Also available is int oncurve(GEN E, GEN z) which does not accept vectors of points.

#### ellj(x)

Elliptic j-invariant. x must be a complex number with positive imaginary part, or convertible into a power series or a p-adic number with positive valuation.

The library syntax is GEN jell(GEN x, long prec).

#### elllocalred(E,p)

Calculates the Kodaira type of the local fiber of the elliptic curve E at the prime p. E must be an ell structure as output by ellinit, and is assumed to have all its coefficients a_i in Z. The result is a 4-component vector [f,kod,v,c]. Here f is the exponent of p in the arithmetic conductor of E, and kod is the Kodaira type which is coded as follows:

1 means good reduction (type I_0), 2, 3 and 4 mean types II, III and IV respectively, 4+nu with nu > 0 means type I_nu; finally the opposite values -1, -2, etc. refer to the starred types I_0^*, II^*, etc. The third component v is itself a vector [u,r,s,t] giving the coordinate changes done during the local reduction; u = 1 if and only if the given equation was already minimal at p. Finally, the last component c is the local Tamagawa number c_p.

The library syntax is GEN elllocalred(GEN E, GEN p).

#### elllog(E,P,G,{o})

Given two points P and G on the elliptic curve E/F_q, returns the discrete logarithm of P in base G, i.e. the smallest non-negative integer n such that P = [n]G. See znlog for the limitations of the underlying discrete log algorithms. If present, o represents the order of G, see Section [Label: se:DLfun]; the preferred format for this parameter is [N, factor(N)], where N is the order of G.

If no o is given, assume that G generates the curve. The function also assumes that P is a multiple of G.

  ? a = ffgen(ffinit(2,8),'a);
? E = ellinit([a,1,0,0,1]);  \\ over F_{2^8}
? x = a^3; y = ellordinate(E,x)[1];
? P = [x,y]; G = ellmul(E, P, 113);
? ord = [242, factor(242)]; \\ P generates a group of order 242. Initialize.
? ellorder(E, G, ord)
%4 = 242
? e = elllog(E, P, G, ord)
%5 = 15
? ellmul(E,G,e) == P
%6 = 1


The library syntax is GEN elllog(GEN E, GEN P, GEN G, GEN o = NULL).

#### elllseries(E,s,{A = 1})

E being an elliptic curve, given by an arbitrary model over Q as output by ellinit, this function computes the value of the L-series of E at the (complex) point s. This function uses an O(N^{1/2}) algorithm, where N is the conductor.

The optional parameter A fixes a cutoff point for the integral and is best left omitted; the result must be independent of A, up to realprecision, so this allows to check the function's accuracy.

The library syntax is GEN elllseries(GEN E, GEN s, GEN A = NULL, long prec).

#### ellminimalmodel(E,{&v})

Return the standard minimal integral model of the rational elliptic curve E. If present, sets v to the corresponding change of variables, which is a vector [u,r,s,t] with rational components. The return value is identical to that of ellchangecurve(E, v).

The resulting model has integral coefficients, is everywhere minimal, a_1 is 0 or 1, a_2 is 0, 1 or -1 and a_3 is 0 or 1. Such a model is unique, and the vector v is unique if we specify that u is positive, which we do.

The library syntax is GEN ellminimalmodel(GEN E, GEN *v = NULL).

#### ellmodulareqn(N,{x},{y})

Return a vector [eqn,t] where eqn is a modular equation of level N, i.e. a bivariate polynomial with integer coefficients; t indicates the type of this equation: either canonical (t = 0) or Atkin (t = 1). This function currently requires the package seadata to be installed and is limited to N < 500, N prime.

Let j be the j-invariant function. The polynomial eqn satisfies the following functional equation, which allows to compute the values of the classical modular polynomial Phi_N of prime level N, such that Phi_N(j(tau), j(Ntau)) = 0, while being much smaller than the latter:

* for canonical type: P(f(tau),j(tau)) = P(N^s/f(tau),j(N tau)) = 0, where s = 12/gcd(12,N-1);

* for Atkin type: P(f(tau),j(tau)) = P(f(tau),j(N tau)) = 0.

In both cases, f is a suitable modular function (see below).

The following GP function returns values of the classical modular polynomial by eliminating f(tau) in the above two equations, for N <= 31 or N belongs to {41,47,59,71}.

  classicaleqn(N, X='X, Y='Y)=
{
my(E=ellmodulareqn(N), P=E[1], t=E[2], Q, d);
if(poldegree(P,'y)>2,error("level unavailable in classicaleqn"));
if (t == 0,
my(s = 12/gcd(12,N-1));
Q = 'x^(N+1) * substvec(P,['x,'y],[N^s/'x,Y]);
d = N^(s*(2*N+1)) * (-1)^(N+1);
,
Q = subst(P,'y,Y);
d = (X-Y)^(N+1));
polresultant(subst(P,'y,X), Q) / d;
}


More precisely, let W_N(tau) = ({-1})/({N tau}) be the Atkin-Lehner involution; we have j(W_N(tau)) = j(N tau) and the function f also satisfies:

* for canonical type: f(W_N(tau)) = N^s/f(tau);

* for Atkin type: f(W_N(tau)) = f(tau).

Furthermore, for an equation of canonical type, f is the standard eta-quotient f(tau) = N^s (eta(N tau) / eta(tau) )^{2 s}, where eta is Dedekind's eta function, which is invariant under Gamma_0(N).

The library syntax is GEN ellmodulareqn(long N, long x = -1, long y = -1), where x, y are variable numbers.

#### ellmul(E,z,n)

Computes [n]z, where z is a point on the elliptic curve E. The exponent n is in Z, or may be a complex quadratic integer if the curve E has complex multiplication by n (if not, an error message is issued).

  ? Ei = ellinit([1,0]); z = [0,0];
? ellmul(Ei, z, 10)
%2 = [0]     \\ unsurprising: z has order 2
? ellmul(Ei, z, I)
%3 = [0, 0]  \\ Ei has complex multiplication by Z[i]
%4 = [0, 0]  \\ an alternative syntax for the same query
? Ej  = ellinit([0,1]); z = [-1,0];
? ellmul(Ej, z, I)
***   at top-level: ellmul(Ej,z,I)
***                 ^--------------
*** ellmul: not a complex multiplication in ellmul.
%6 = [1 - w, 0]


The simple-minded algorithm for the CM case assumes that we are in characteristic 0, and that the quadratic order to which n belongs has small discriminant.

The library syntax is GEN ellmul(GEN E, GEN z, GEN n).

#### ellneg(E,z)

Opposite of the point z on elliptic curve E.

The library syntax is GEN ellneg(GEN E, GEN z).

#### ellorder(E,z,{o})

Gives the order of the point z on the elliptic curve E, defined over Q or a finite field. If the curve is defined over Q, return (the impossible value) zero if the point has infinite order.

  ? E = ellinit([-157^2,0]);  \\ the "157-is-congruent" curve
? P = [2,2]; ellorder(E, P)
%2 = 2
? P = ellheegner(E); ellorder(E, P) \\ infinite order
%3 = 0
? E = ellinit(ellfromj(ffgen(5^10)));
? ellcard(E)
%5 = 9762580
? P = random(E); ellorder(E, P)
%6 = 4881290
? p = 2^160+7; E = ellinit([1,2], p);
? N = ellcard(E)
%8 = 1461501637330902918203686560289225285992592471152
? o = [N, factor(N)];
? for(i=1,100, ellorder(E,random(E)))
time = 260 ms.


The parameter o, is now mostly useless, and kept for backward compatibility. If present, it represents a non-zero multiple of the order of z, see Section [Label: se:DLfun]; the preferred format for this parameter is [ord, factor(ord)], where ord is the cardinality of the curve. It is no longer needed since PARI is now able to compute it over large finite fields (was restricted to small prime fields at the time this feature was introduced), and caches the result in E so that it is computed and factored only once. Modifying the last example, we see that including this extra parameter provides no improvement:

  ? o = [N, factor(N)];
? for(i=1,100, ellorder(E,random(E),o))
time = 260 ms.


The library syntax is GEN ellorder(GEN E, GEN z, GEN o = NULL). The obsolete form GEN orderell(GEN e, GEN z) should no longer be used.

#### ellordinate(E,x)

Gives a 0, 1 or 2-component vector containing the y-coordinates of the points of the curve E having x as x-coordinate.

The library syntax is GEN ellordinate(GEN E, GEN x, long prec).

#### ellperiods(w, {flag = 0})

Let w describe a complex period lattice (w = [w_1,w_2] or an ellinit structure). Returns normalized periods [W_1,W_2] generating the same lattice such that tau := W_1/W_2 has positive imaginary part and lies in the standard fundamental domain for {SL}_2(Z).

If flag = 1, the function returns [[W_1,W_2], [eta_1,eta_2]], where eta_1 and eta_2 are the quasi-periods associated to [W_1,W_2], satisfying eta_1 W_2 - eta_2 W_1 = 2 i Pi.

The output of this function is meant to be used as the first argument given to ellwp, ellzeta, ellsigma or elleisnum. Quasi-periods are needed by ellzeta and ellsigma only.

The library syntax is GEN ellperiods(GEN w, long flag , long prec).

#### ellpointtoz(E,P)

If E/C ~ C/Lambda is a complex elliptic curve (Lambda = E.omega), computes a complex number z, well-defined modulo the lattice Lambda, corresponding to the point P; i.e. such that P = [wp_Lambda(z),wp'_Lambda(z)] satisfies the equation y^2 = 4x^3 - g_2 x - g_3, where g_2, g_3 are the elliptic invariants.

If E is defined over R and P belongs to E(R), we have more precisely, 0 \leq Re(t) < w1 and 0 <= Im(t) < Im(w2), where (w1,w2) are the real and complex periods of E.

  ? E = ellinit([0,1]); P = [2,3];
? z = ellpointtoz(E, P)
%2 = 3.5054552633136356529375476976257353387
? ellwp(E, z)
%3 = 2.0000000000000000000000000000000000000
? ellztopoint(E, z) - P
%4 = [6.372367644529809109 E-58, 7.646841173435770930 E-57]
? ellpointtoz(E, [0]) \\ the point at infinity
%5 = 0


If E/Q_p has multiplicative reduction, then E/\bar{Q_p} is analytically isomorphic to \bar{Q}_p^*/q^Z (Tate curve) for some p-adic integer q. The behaviour is then as follows:

* If the reduction is split (E.tate[2] is a t_PADIC), we have an isomorphism phi: E(Q_p) ~ Q_p^*/q^Z and the function returns phi(P) belongs to Q_p.

* If the reduction is not split (E.tate[2] is a t_POLMOD), we only have an isomorphism phi: E(K) ~ K^*/q^Z over the unramified quadratic extension K/Q_p. In this case, the output phi(P) belongs to K is a t_POLMOD.

  ? E = ellinit([0,-1,1,0,0], O(11^5)); P = [0,0];
? [u2,u,q] = E.tate; type(u) \\ split multiplicative reduction
? ellmul(E, P, 5)  \\ P has order 5
%3 = [0]
? z = ellpointtoz(E, [0,0])
%4 = 3 + 11^2 + 2*11^3 + 3*11^4 + O(11^5)
? z^5
%5 = 1 + O(11^5)
? E = ellinit(ellfromj(1/4), O(2^6)); x=1/2; y=ellordinate(E,x)[1];
? z = ellpointtoz(E,[x,y]); \\ t_POLMOD of t_POL with t_PADIC coeffs
? liftint(z) \\ lift all p-adics
%8 = Mod(8*u + 7, u^2 + 437)


The library syntax is GEN zell(GEN E, GEN P, long prec).

#### ellpow(E,z,n)

Deprecated alias for ellmul.

The library syntax is GEN ellmul(GEN E, GEN z, GEN n).

#### ellrootno(E,{p})

E being an ell structure over Q as output by ellinit, this function computes the local root number of its L-series at the place p (at the infinite place if p = 0). If p is omitted, return the global root number. Note that the global root number is the sign of the functional equation and conjecturally is the parity of the rank of the \idx{Mordell-Weil group}. The equation for E needs not be minimal at p, but if the model is already minimal the function will run faster.

The library syntax is long ellrootno(GEN E, GEN p = NULL).

#### ellsearch(N)

This function finds all curves in the elldata database satisfying the constraint defined by the argument N:

* if N is a character string, it selects a given curve, e.g. "11a1", or curves in the given isogeny class, e.g. "11a", or curves with given condutor, e.g. "11";

* if N is a vector of integers, it encodes the same constraints as the character string above, according to the ellconvertname correspondance, e.g. [11,0,1] for "11a1", [11,0] for "11a" and [11] for "11";

* if N is an integer, curves with conductor N are selected.

If N is a full curve name, e.g. "11a1" or [11,0,1], the output format is [N, [a_1,a_2,a_3,a_4,a_6], G] where [a_1,a_2,a_3,a_4,a_6] are the coefficients of the Weierstrass equation of the curve and G is a Z-basis of the free part of the \idx{Mordell-Weil group} associated to the curve.

  ? ellsearch("11a3")
%1 = ["11a3", [0, -1, 1, 0, 0], []]
? ellsearch([11,0,3])
%2 = ["11a3", [0, -1, 1, 0, 0], []]


If N is not a full curve name, then the output is a vector of all matching curves in the above format:

  ? ellsearch("11a")
%1 = [["11a1", [0, -1, 1, -10, -20], []],
["11a2", [0, -1, 1, -7820, -263580], []],
["11a3", [0, -1, 1, 0, 0], []]]
? ellsearch("11b")
%2 = []


The library syntax is GEN ellsearch(GEN N). Also available is GEN ellsearchcurve(GEN N) that only accepts complete curve names (as t_STR).

#### ellsigma(L,{z = 'x},{flag = 0})

Computes the value at z of the Weierstrass sigma function attached to the lattice L as given by ellperiods(,1): including quasi-periods is useful, otherwise there are recomputed from scratch for each new z. sigma(z, L) = z prod_{omega belongs to L^*} (1 - (z)/(omega))e^{(z)/(omega) + (z^2)/(2omega^2)}. It is also possible to directly input L = [omega_1,omega_2], or an elliptic curve E as given by ellinit (L = E.omega).

  ? w = ellperiods([1,I], 1);
? ellsigma(w, 1/2)
%2 = 0.47494937998792065033250463632798296855
? E = ellinit([1,0]);
? ellsigma(E) \\ at 'x, implicitly at default seriesprecision
%4 = x + 1/60*x^5 - 1/10080*x^9 - 23/259459200*x^13 + O(x^17)


If flag = 1, computes an arbitrary determination of log(sigma(z)).

The library syntax is GEN ellsigma(GEN L, GEN z = NULL, long flag, long prec).

#### ellsub(E,z1,z2)

Difference of the points z1 and z2 on the elliptic curve corresponding to E.

The library syntax is GEN ellsub(GEN E, GEN z1, GEN z2).

#### elltaniyama(E, {d = seriesprecision})

Computes the modular parametrization of the elliptic curve E/Q, where E is an ell structure as output by ellinit. This returns a two-component vector [u,v] of power series, given to d significant terms (seriesprecision by default), characterized by the following two properties. First the point (u,v) satisfies the equation of the elliptic curve. Second, let N be the conductor of E and Phi: X_0(N)\to E be a modular parametrization; the pullback by Phi of the Néron differential du/(2v+a_1u+a_3) is equal to 2iPi f(z)dz, a holomorphic differential form. The variable used in the power series for u and v is x, which is implicitly understood to be equal to exp(2iPi z).

The algorithm assumes that E is a strong Weil curve and that the Manin constant is equal to 1: in fact, f(x) = sum_{n > 0} ellan(E, n) x^n.

The library syntax is GEN elltaniyama(GEN E, long precdl).

#### elltatepairing(E, P, Q, m)

Computes the Tate pairing of the two points P and Q on the elliptic curve E. The point P must be of m-torsion.

The library syntax is GEN elltatepairing(GEN E, GEN P, GEN Q, GEN m).

#### elltors(E,{flag = 0})

If E is an elliptic curve defined over Q, outputs the torsion subgroup of E as a 3-component vector [t,v1,v2], where t is the order of the torsion group, v1 gives the structure of the torsion group as a product of cyclic groups (sorted by decreasing order), and v2 gives generators for these cyclic groups. E must be an ell structure as output by ellinit, defined over Q.

  ?  E = ellinit([-1,0]);
?  elltors(E)
%1 = [4, [2, 2], [[0, 0], [1, 0]]]


Here, the torsion subgroup is isomorphic to Z/2Z x Z/2Z, with generators [0,0] and [1,0].

If flag = 0, find rational roots of division polynomials.

If flag = 1, use Lutz-Nagell (much slower).

If flag = 2, use Doud's algorithm: bound torsion by computing #E(F_p) for small primes of good reduction, then look for torsion points using Weierstrass wp function (and Mazur's classification). For this variant, E must be an ell.

The library syntax is GEN elltors0(GEN E, long flag). Also available is GEN elltors(GEN E) for elltors(E, 0).

#### ellweilpairing(E, P, Q, m)

Computes the Weil pairing of the two points of m-torsion P and Q on the elliptic curve E.

The library syntax is GEN ellweilpairing(GEN E, GEN P, GEN Q, GEN m).

#### ellwp(w,{z = 'x},{flag = 0})

Computes the value at z of the Weierstrass wp function attached to the lattice w as given by ellperiods. It is also possible to directly input w = [omega_1,omega_2], or an elliptic curve E as given by ellinit (w = E.omega).

  ? w = ellperiods([1,I]);
? ellwp(w, 1/2)
%2 = 6.8751858180203728274900957798105571978
? E = ellinit([1,1]);
? ellwp(E, 1/2)
%4 = 3.9413112427016474646048282462709151389

One can also compute the series expansion around z = 0:

  ? E = ellinit([1,0]);
? ellwp(E)              \\ 'x implicitly at default seriesprecision
%5 = x^-2 - 1/5*x^2 + 1/75*x^6 - 2/4875*x^10 + O(x^14)
? ellwp(E, x + O(x^12)) \\ explicit precision
%6 = x^-2 - 1/5*x^2 + 1/75*x^6 + O(x^9)


Optional flag means 0 (default): compute only wp(z), 1: compute [wp(z),wp'(z)].

The library syntax is GEN ellwp0(GEN w, GEN z = NULL, long flag, long prec). For flag = 0, we also have GEN ellwp(GEN w, GEN z, long prec), and GEN ellwpseries(GEN E, long v, long precdl) for the power series in variable v.

#### ellzeta(w,{z = 'x})

Computes the value at z of the Weierstrass zeta function attached to the lattice w as given by ellperiods(,1): including quasi-periods is useful, otherwise there are recomputed from scratch for each new z. zeta(z, L) = (1)/(z) + z^2sum_{omega belongs to L^*} (1)/(omega^2(z-omega)). It is also possible to directly input w = [omega_1,omega_2], or an elliptic curve E as given by ellinit (w = E.omega). The quasi-periods of zeta, such that zeta(z + aomega_1 + bomega_2) = zeta(z) + aeta_1 + beta_2 for integers a and b are obtained as eta_i = 2zeta(omega_i/2). Or using directly elleta.

  ? w = ellperiods([1,I],1);
? ellzeta(w, 1/2)
%2 = 1.5707963267948966192313216916397514421
? E = ellinit([1,0]);
? ellzeta(E, E.omega[1]/2)
%4 = 0.84721308479397908660649912348219163647

One can also compute the series expansion around z = 0 (the quasi-periods are useless in this case):

  ? E = ellinit([0,1]);
? ellzeta(E) \\ at 'x, implicitly at default seriesprecision
%4 = x^-1 + 1/35*x^5 - 1/7007*x^11 + O(x^15)
? ellzeta(E, x + O(x^20)) \\ explicit precision
%5 = x^-1 + 1/35*x^5 - 1/7007*x^11 + 1/1440257*x^17 + O(x^18)


The library syntax is GEN ellzeta(GEN w, GEN z = NULL, long prec).

#### ellztopoint(E,z)

E being an ell as output by ellinit, computes the coordinates [x,y] on the curve E corresponding to the complex number z. Hence this is the inverse function of ellpointtoz. In other words, if the curve is put in Weierstrass form y^2 = 4x^3 - g_2x - g_3, [x,y] represents the Weierstrass wp-function and its derivative. More precisely, we have x = wp(z) - b_2/12, y = wp'(z) - (a_1 x + a_3)/2. If z is in the lattice defining E over C, the result is the point at infinity [0].

The library syntax is GEN pointell(GEN E, GEN z, long prec).

#### genus2red(Q,P,{p})

Let Q,P be polynomials with integer coefficients. Determines the reduction at p > 2 of the (proper, smooth) genus 2 curve C/Q, defined by the hyperelliptic equation y^2+Qy = P. (The special fiber X_p of the minimal regular model X of C over Z.) If p is omitted, determines the reduction type for all (odd) prime divisors of the discriminant.

This function rewritten from an implementation of Liu's algorithm by Cohen and Liu (1994), genus2reduction-0.3, see http://www.math.u-bordeaux1.fr/~ liu/G2R/.

CAVEAT. The function interface may change: for the time being, it returns [N,FaN, T, V] where N is either the local conductor at p or the global conductor, FaN is its factorization, y^2 = T defines a minimal model over Z[1/2] and V describes the reduction type at the various considered p. Unfortunately, the program is not complete for p = 2, and we may return the odd part of the conductor only: this is the case if the factorization includes the (impossible) term 2^{-1}; if the factorization contains another power of 2, then this is the exact local conductor at 2 and N is the global conductor.

  ? default(debuglevel, 1);
? genus2red(0,x^6 + 3*x^3 + 63, 3)
(potential) stable reduction: [1, []]
reduction at p: [III{9}] page 184, [3, 3], f = 10
%1 = [59049, Mat([3, 10]), x^6 + 3*x^3 + 63, [3, [1, []],
["[III{9}] page 184", [3, 3]]]]
? [N, FaN, T, V] = genus2red(x^3-x^2-1, x^2-x);  \\ X_1(13), global reduction
p = 13
(potential) stable reduction: [5, [Mod(0, 13), Mod(0, 13)]]
reduction at p: [I{0}-II-0] page 159, [], f = 2
? N
%3 = 169
? FaN
%4 = Mat([13, 2])   \\ in particular, good reduction at 2 !
? T
%5 = x^6 + 58*x^5 + 1401*x^4 + 18038*x^3 + 130546*x^2 + 503516*x + 808561
? V
%6 = [[13, [5, [Mod(0, 13), Mod(0, 13)]], ["[I{0}-II-0] page 159", []]]]


We now first describe the format of the vector V = V_p in the case where p was specified (local reduction at p): it is a triple [p, stable, red]. The component stable = [type, vecj] contains information about the stable reduction after a field extension; depending on types, the stable reduction is

* 1: smooth (i.e. the curve has potentially good reduction). The Jacobian J(C) has potentially good reduction.

* 2: an elliptic curve E with an ordinary double point; vecj contains j mod p, the modular invariant of E. The (potential) semi-abelian reduction of J(C) is the extension of an elliptic curve (with modular invariant j mod p) by a torus.

* 3: a projective line with two ordinary double points. The Jacobian J(C) has potentially multiplicative reduction.

* 4: the union of two projective lines crossing transversally at three points. The Jacobian J(C) has potentially multiplicative reduction.

* 5: the union of two elliptic curves E_1 and E_2 intersecting transversally at one point; vecj contains their modular invariants j_1 and j_2, which may live in a quadratic extension of F_p are need not be distinct. The Jacobian J(C) has potentially good reduction, isomorphic to the product of the reductions of E_1 and E_2.

* 6: the union of an elliptic curve E and a projective line which has an ordinary double point, and these two components intersect transversally at one point; vecj contains j mod p, the modular invariant of E. The (potential) semi-abelian reduction of J(C) is the extension of an elliptic curve (with modular invariant j mod p) by a torus.

* 7: as in type 6, but the two components are both singular. The Jacobian J(C) has potentially multiplicative reduction.

The component red = [NUtype, neron] contains two data concerning the reduction at p without any ramified field extension.

The NUtype is a t_STR describing the reduction at p of C, following Namikawa-Ueno, The complete classification of fibers in pencils of curves of genus two, Manuscripta Math., vol. 9, (1973), pages 143-186. The reduction symbol is followed by the corresponding page number in this article.

The second datum neron is the group of connected components (over an algebraic closure of F_p) of the Néron model of J(C), given as a finite abelian group (vector of elementary divisors).

If p = 2, the red component may be omitted altogether (and replaced by [], in the case where the program could not compute it. When p was not specified, V is the vector of all V_p, for all considered p.

* A lower index is denoted between braces: for instance, \kbd{[I{ 2}-II-5]} means [I_2-II-5].
* If K and K' are Kodaira symbols for singular fibers of elliptic curves, [K-K'-m] and [K'-K-m] are the same.
* [K-K'--1] is [K'-K-alpha] in the notation of Namikawa-Ueno.
* The figure [2I_0-m] in Namikawa-Ueno, page 159, must be denoted by [2I_0-(m+1)].
The library syntax is GEN genus2red(GEN Q, GEN P, GEN p = NULL).