### 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
@3

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
@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_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

@3Algorithms 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 30digits. If the

SEA algorithm becomes available, heuristically in ~{O}(log
q)^4, and primes of the order of 200digits 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)

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

@3* N is the arithmetic conductor of the curve,

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

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

@3* F is the factorization of N over Z.

@3* 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])

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.
@3Caution. 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)]]]
@3

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). 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 a trick due to J.Silverman. 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

@3* 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,

@3* 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,

@3* a character string in Cremona's notation, e.g.
"11a1", in which
elldata database if available.

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

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

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

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

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

@3* a
will be computed to a relative accuracy of n digits.

@3* 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
@3
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 !
@3

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

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:

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

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

@3In 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:

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

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

@3Furthermore, 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,
computes a complex number z (modulo the lattice Lambda)
corresponding to the point P; i.e.such that P = [wp(z),wp'(z)]
in the standard Weierstrass model (z\not belongs to Lambda).
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:

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

@3* 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];
ellpointtoz(e,[x,y])

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:

@3* 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";

@3* 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";

@3* 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], []]
@3

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(E,{z = 'x},{flag = 0})

Computes the value at z of the Weierstrass sigma 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.
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 w = [omega_1,omega_2],
or an elliptic curve E as given by
ellinit.

? 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 E, 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 parametrization (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 = ellperiods([1,I]);
? ellwp(w, 1/2)
%2 = 6.8751858180203728274900957798105571978
? E = ellinit([1,1]);
? ellwp(E, 1/2)
%4 = 3.9413112427016474646048282462709151389
@3
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(E,{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. 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
@3
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)
@3

The library syntax is
GEN ellzeta(GEN E, 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, [x,y] represents the Weierstrass wp-function\sidx{Weierstrass
wp-function} and its derivative. 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) genus2
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.

@3This 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/.

@3CAVEAT. 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 consideredp. 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", []]]]
@3

We now first describe the format of the vector V = V_p in the case where
p was specified (local reduction atp): 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

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

@3* 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* 3: a projective line with two ordinary double points. The Jacobian
J(C) has potentially multiplicative reduction.

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

@3* 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.

@3* 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.

@3* 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

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.

@3* A lower index is denoted between braces: for instance, \kbd{[I{
2}-II-5]} means
[I_2-II-5].

@3* If K and K' are Kodaira symbols for singular fibers of elliptic
curves,
[K-K'-m] and
[K'-K-m] are the same.

@3*
[K-K'--1]  is
[K'-K-alpha] in the notation of
Namikawa-Ueno.

@3* 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).