betaFeedback

WorksMathematics

ECPack.wl: A Mathematica Package for Elliptic Curves over the Rationals and Finite Fields

Abstract

We present a Mathematica package entitled ECPack.wl, where we implement many important properties and commands relevant to the study of elliptic curves over the rationals and finite fields, namely Q\mathbb{Q} and Fq\mathbb{F}_q, where q=prq=p^r and pp is prime. By streamlining the analysis of general elliptic curves and their transformations, ECPack.wl offers foundational computational tools for applications in high-energy physics, including elliptic Feynman integrals. This package significantly extends the functionalities of a package due to McGee in so far as we are able to study all versions of elliptic curves, such as the long Weierstrass, quartic and Legendre forms. We implement suitable transformations that are required for the general case, as well as those associated with fields of characteristic 2 and 3. Furthermore, the package computes many curve properties, such as point arithmetic, minimality checks, rank bounds and analytic rank, group structure, invariants, and the Weil and Tate pairings, over both Q\mathbb{Q} and Fp\mathbb{F}_p, as well as the Kodaira classification of the singular fibres of one-parameter families of elliptic curves, with the associated F-theory data. The package and its accompanying notebooks are available at https://github.com/DhamakedarDarsh/Mathematica-Code-and-worked-out-notebooks-for-Elliptic-Curves

Program Summary

Program Title: ECPack.wl, version 1.0

Repository Link: https://github.com/DhamakedarDarsh/Mathematica-Code-and-worked-out-notebooks-for-Elliptic-Curves

Licensing Provisions: GNU General Public License

Programming Language: Wolfram Mathematica version 13.2 or higher

Introduction

In the recent past, elliptic curves, elliptic functions, elliptic integrals, and modular forms and their L-functions have begun to enter theoretical physics. For instance, in the calculation of certain Feynman integrals, elliptic and modular structures arise; hence, this category of Feynman integrals is often referred to as elliptic Feynman integrals. To calculate these integrals, we must study elliptic and modular structures. A recent collection of articles may be found in [1], and for instance in Chapter 13 of the standard textbook [2]. Furthermore, they arise in other areas of theoretical high-energy physics, such as string theory; see, e.g. [3].

In view of these applications, it is useful to study these structures systematically. In this article we focus on elliptic curves and introduce ECPack.wl, a Mathematica package for studying elliptic curves over the rationals and over finite fields. Note that other topics will be studied in our subsequent articles. Although many physics applications ultimately lead to elliptic curves over C\mathbb{C}, here we confine ourselves to the rationals and finite fields as a first step. The transformations between cubic, Weierstrass, quartic, and Legendre forms are already useful in that broader setting, so this package is indirectly motivated by physics as well as by arithmetic geometry.

The subject of elliptic curves is one of the jewels of nineteenth-century mathematics, originating with Abel, Gauss, Jacobi, and Legendre as noted in the Introduction chapter of ref. [4]. These curves are associated with modular forms, topology, complex analysis, group theory, number theory, and modern cryptography. An elliptic curve over C\mathbb{C} is a smooth algebraic curve of genus one in CP2\mathbb{CP}^{2} together with a distinguished point, usually taken as the point at infinity. Elliptic curves can have points with coordinates in any field, such as Fq\mathbb{F}_{q}, Q\mathbb{Q}, R\mathbb{R}, or C\mathbb{C}.[5] They are defined by an equation given by:

y2+a1xy+a3y=x3+a2x2+a4x+a6, the long Weierstrass equation(1)y^{2}+a_{1}xy+a_{3}y=x^{3}+a_{2}x^{2}+a_{4}x+a_{6},\ \text{the long Weierstrass equation} \tag*{(1)}

Our purpose is to learn the use of elliptic curve technology from basic principles and to study various manifestations of these that is often found in standard textbooks. Keeping in mind that this topic falls outside a typical university course syllabus, we wished to approach it through problem-solving and from the perspective of using computer algebra, especially the Mathematica platform.

To our knowledge, there is only one package by John McGee[6], which deals with elliptic curves and introduces several relevant topics, such as a linear combination of the two points, the order of the points, the group order, Hasse’s bound, the jj-invariant of the curve, Bachet’s duplication formula, as well as cryptography with ElGamal encoding and decoding using elliptic curve operators. The author has given a wishlist at the end of his accompanying notebooks, which lists Computation of the Weil Pairing (P,Q)↦ei2kπ/n(P,Q)\mapsto e^{i2k\pi/n} and Implementation of the Schoof–Elkies–Atkin algorithm for ∣E(Fq)∣|E(\mathbb{F}_{q})|, etc, to our knowledge, none of them have been made available to the public. Miller’s algorithm and the Weil and Tate pairings are implemented in ECPack (Section 7). In this work, we begin by writing an independent package that, on the one hand, reproduces the computations demonstrated in the notebook of McGee [6] and, whenever possible, offers comparisons, and, on the other hand, significantly enhances it. Our aim in this work is to comprehensively study elliptic curves over rational and finite fields. Our package offers several extensions, such as

  1. Transformations and Coordinates Cubic to Weierstrass, quartic to Weierstrass, long to short Weierstrass, as well as Legendre to Weierstrass conversions, and coordinate conversions. The commands pertinent to transformations work for all elliptic curves regardless of the field over which they are defined.

  1. Core Arithmetic and Equivalences Checking whether a point is on a curve or not, checking exact projective equivalence of two points, the chord and tangent operation, point addition, point multiplication by a scalar value, and point order.

  1. Minimal Models and Discriminants Computing the torsion subgroup of an elliptic curve, finding rational torsion points using the Nagell-Lutz theorem, finding independent generators for an elliptic curve, calculating a basic upper bound on a curve’s rank, searching for points on a curve within a numerical bound, and Bachet’s duplication.

  1. Heights and Pairings Computing the naive logarithmic height of a point, computing the canonical height using iterative limits, computing the height pairing of two points, computing the height matrix for a given list of points, and checking whether a set of points is independent based on their height matrix determinant or not.

  1. Finite Fields, ElGamal Cryptography and Pairings Adding two points modulo prime pp, multiplying a point by scalar nn modulo prime pp, embedding an integer message onto the curve using Koblitiz encoding, performing ElGamal encryption/encoding, and performing ElGamal decryption/decoding. Evaluating Miller’s function, computing the Weil pairing and the reduced Tate pairing over Fp\mathbb{F}_{p} and Fpr\mathbb{F}_{p^{r}}, and finding a basis of the full nn-torsion subgroup.

Elliptic Families and Kodaira Classification

Orders of vanishing of c4c_4, c6c_6 and Δ\Delta along a point of the base, the Kodaira type and Euler number of the singular fibre of a family of elliptic curves over Q(t)\mathbb{Q}(t), including the fibre at t=∞t = \infty, the list of all singular fibres with the check that the Euler numbers add up to 12n12n, the split or non-split character of InI_n and IVIV fibres, the jj-function of a family, F-theory gauge algebras, scaling dimensions of Coulomb-branch parameters, Tate forms with prescribed vanishing orders, and the universal families with an NN-torsion point.

Figure 1.1 gives a schematic overview of the package: the functionality that is already available in the package of McGee [6] (as described above) is shaded, and everything else is new.

Overview of ECPack.wl package functionality

Figure 1.1. Overview of ECPack.wl. Any curve is first brought to Weierstrass form, then analyzed over Q\mathbb{Q}, locally (reduction modulo pp), over finite fields, or used in cryptography. Shaded boxes indicate functionality that is also described for the package of McGee [6]; all other boxes are new.

We are guided by the very useful and accessible book by Lozano-Robledo [7] which allows us to give a solid structure to our code.

The first offering we have in this package is that we do not confine ourselves to the short Weierstrass form of the elliptic curve. For physical applications, one needs the quartic and Legendre forms, albeit over C\mathbb{C}. Nevertheless, our code now allows the study of elliptic curves in the following forms: cubic, long and short Weierstrass, quartic, and Legendre. We also code the requisite transformations, which are valid as long as one is not dealing with fields of characteristic 2 and 3.

The availability of good and bad reduction will also assist in evaluating the L-series associated with elliptic curves.

We also offer a realization of Schoof’s point counting algorithm, which determines the trace of Frobenius modulo small primes and counts the points of a curve over a prime field Fp\mathbb{F}_p with pp far beyond the reach of enumeration.

At appropriate points, we refer to the accompanying notebooks, which collect textbook-style test cases from Lozano-Robledo, Husemöller, Washington, Silverman, Silverman–Tate, McGee, and a set of general curves. These notebooks are meant to help readers see how the commands behave on representative inputs and to keep the main text focused on the ideas behind the package.

The rest of the article is organized as follows. Section 2 lists the forms in which an elliptic curve can be given and the maps to Weierstrass form. Section 3 studies the group of rational points, its torsion, rank, and heights, and Section 4 studies the curve over finite fields, including point counting. Section 5 treats reduction modulo pp and the minimal model, and Section 6 replaces the primes by the points of a parameter space and classifies the singular fibres of one-parameter families by Kodaira’s table. § 8 turns to cryptography and pairings. The appendices recall the characteristic of a field (Appendix § 11) and the Frobenius endomorphism (Appendix § 12), and contain the package’s user manual (Appendix § 13) and notebook guide (Appendix § 21). We demonstrate that using our notebooks can significantly reduce tedium, and solutions can be readily obtained. Furthermore, we provide a list of all commands embedded in the code, which can be retrieved in the notebook using the ? command.

Various Forms of an Elliptic Curve

In applications, an elliptic curve rarely arrives in the long Weierstrass form: curves that appear in the study of elliptic Feynman integrals can be given as a plane cubic or as a quartic, and families of curves are often written in the Legendre form. A first task of any package is therefore to recognize these forms and to bring each of them to a Weierstrass equation, on which all later computations are carried out. In this section we start by defining the elliptic curve and recall the forms accepted by ECPack, namely the general cubic, the long and short Weierstrass forms, the quartic and the Legendre form, and indicate how they are related. The transformations themselves are implemented by the commands listed at the end of the section.

Definition 1. An elliptic curve over C\mathbb{C} is a smooth algebraic curve in CP2\mathbb{C}P^2 of genus one together with one marked point, usually taken as the point at infinity.[2] The arithmetic of elliptic curves concerns itself with the points of a nonsingular cubic y2=x3+ax+by^2 = x^3 + ax + b with coordinates in a field, such as Fp\mathbb{F}_p, Q\mathbb{Q}, R\mathbb{R}, or C\mathbb{C}.[4, 5]

The General Cubic Form

An elliptic curve over Q\mathbb{Q} is a smooth cubic projective curve EE, with at least one rational point O∈E(Q)\mathcal{O} \in E(\mathbb{Q}). This point is the identity element of the group law defined over elliptic curves. In the projective plane, it is given by a cubic polynomial F(X,Y,Z)=0F(X,Y,Z)=0 with rational coefficients a,b,c,…∈Qa,b,c,\ldots\in\mathbb{Q}, such that EE is smooth.

F(X,Y,Z)=aX3+bX2Y+cXY2+dY3+eX2Z+fXYZ+gY2Z+hXZ2+jYZ2+kZ3=0.(2)F(X,Y,Z) = aX^3+bX^2Y+cXY^2+dY^3+eX^2Z+fXYZ+gY^2Z+hXZ^2+jYZ^2+kZ^3 = 0. \tag*{(2)}

Regardless, we often consider just affine charts of EE, e.g., those points of the form [X,Y,1][X,Y,1], and study instead the affine curve given by,

aX3+bX2Y+cXY2+dY3+eX2+fXY+gY2+hX+jY+k=0.(3)aX^3+bX^2Y+cXY^2+dY^3+eX^2+fXY+gY^2+hX+jY+k = 0. \tag*{(3)}

This is the general cubic form of an elliptic curve. Note that here, we left out some points of EE at infinity (i.e., those points [X,Y,0][X,Y,0]).

The General Weierstrass Equation: The Long Weierstrass Form

y2+a1xy+a3y=x3+a2x2+a4x+a6(4)y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6 \tag*{(4)}

With ai∈Qa_i \in\mathbb{Q}.

The Short Weierstrass Form

A curve EE over a field KK of characteristic (see Appendix § 11.1) different from 2 or 3, where A,B∈KA,B \in K, is given by a Weierstrass equation,

y2=x3+Ax+B.(5)y^2=x^3+Ax+B. \tag*{(5)}

This curve is non-singular if and only if

4A3+27B2≠0.(6)4A^3+27B^2 \ne0. \tag*{(6)}

It also has a unique point at infinity [0:1:0][0:1:0], which is called the origin O\mathcal{O} or the point at infinity of $E.

Quartic Form

We will meet elliptic curves defined by equations of the form

v2=au4+bu3+cu2+du+e,(7)v^2 = au^4 + bu^3 + cu^2 + du + e, \tag*{(7)}

with a≠0a \ne0. If we have a point (p,q)(p,q) lying on the curve with p,q∈Kp,q \in K, then the equation, when it is nonsingular, can be transformed into a Weierstrass equation by an invertible change of variables that uses rational functions with coefficients in the field KK. Note that an elliptic curve EE defined over a field KK always has a point in E(K)E(K), namely ∞\infty, whose projective coordinates (0:1:0)(0:1:0) certainly lie in KK. Therefore, if we are going to transform a curve CC into Weierstrass form in such a way that all coefficients of the rational functions describing the transformation lie in KK, then we need to start with a point on CC that has coordinates in KK.[8]

The quartic form can also be expressed as follows

y2=(x−x1)(x−x2)(x−x3)(x−x4),(8)y^2 = (x-x_1)(x-x_2)(x-x_3)(x-x_4), \tag*{(8)}

If all roots of the quartic polynomial on the right-hand side are distinct, this defines a smooth elliptic curve.[2]

Legendre Form

An elliptic curve in Legendre form over K(λ)K(\lambda) is defined by equations of the form

y2=x(x−1)(x−λ),(9)y^2 = x(x-1)(x-\lambda), \tag*{(9)}

where KK is a field of characteristic different from 2. The points {(0,0),(1,0),(λ,0)}\{(0,0),(1,0),(\lambda,0)\} are the three 2-torsion points on EλE_\lambda for each value of λ∈K−{0,1}\lambda\in K-\{0,1\}.

Note that here λ\lambda is treated as an affine parameter, λ∈K\lambda\in K, so only λ=0,1\lambda=0,1 are excluded. If we compactify the parameter space by adjoining the point at infinity, then λ\lambda is viewed as a projective parameter on P1(K)=K∪{∞}\mathbb{P}^1(K)=K\cup\{\infty\}. In that setting, the smooth Legendre family is parametrized by

λ∈P1(K)−{0,1,∞}.\lambda\in\mathbb{P}^1(K)-\{0,1,\infty\}.
Relevant ECPack commands (each name links to its entry in Appendix § 13. )
Reading and displaying a curve: ECPExtractCoefficients, ECPFormattedEquation, ECPToWeierstrassForm, ECPParseAffineCurve, ECPParseHomogeneousCurve, ECPPolynomialHomogeneous, ECPPolynomialTransform, ECPSetEC
Cubic, quartic and Legendre forms to Weierstrass form: ECPCubicToWeierstrass, ECPCubicToWeierstrassCharTwoThree, ECPQuarticToWeierstrass, ECPLegendreToWeierstrass
Long and short forms; normal forms in characteristic 2 and 3: ECPToShortWeierstrass, ECPShortWeierstrassForm, ECPToShortWeierstrassFp, ECPNormalFormCharTwoThree
Isomorphisms and point coordinates: ECPTransformWeierstrass, ECPComposeTransformations, ECPToShortCoordinates, ECPFromShortCoordinates, ECPToShortCoordinatesFp, ECPFromShortCoordinatesFp, ECPToLongCoordinates
Invariants: ECPWInvariants, ECPWeierstrassDiscriminant, ECPShortDiscriminant, ECPJInvariant

Table 1.

Elliptic Curves over Rational Fields

Once a curve has been brought to Weierstrass form by the transformations of Section 2, the first field over which we study it is Q\mathbb{Q}. The set of rational points of an elliptic curve is not merely a set but an abelian group, and many commands of ECPack (point addition and multiplication, torsion points, generators, heights) implement aspects of this structure. In this section we first recall the group law on E(Q)E(\mathbb{Q}), then describe the structure of the group, namely its torsion subgroup and its rank, and finally introduce the canonical height and the Néron–Tate pairing, which allow one to decide whether a given set of rational points is independent. We work with the short Weierstrass equation y2=x3+Ax+By^2=x^3+Ax+B, to which every curve over Q\mathbb{Q} can be reduced.

The Group Law on E(Q)E(\mathbb{Q})

Let E:y2=x3+Ax+BE:y^2=x^3+Ax+B with A,B∈QA,B\in\mathbb{Q}, and

E(Q)={(x,y)∈Q2:y2=x3+Ax+B}∪{O},(10)E(\mathbb{Q})=\{(x,y)\in\mathbb{Q}^2:y^2=x^3+Ax+B\}\cup\{\mathcal{O}\}, \tag*{(10)}

where O=[0:1:0]O = [0 : 1 : 0] is the point at infinity. E(Q)E(\mathbb{Q}) carries a group structure whose operation is the addition of points described below.

Chord and tangent. For two distinct points P,Q∈E(Q)P, Q \in E(\mathbb{Q}), the line through PP and QQ meets EE in a third point RR; the sum P+QP + Q is the reflection of RR across the xx-axis (Figure 3.1a). If P=QP = Q, the line is replaced by the tangent to EE at PP, which meets the curve at a new point whose reflection is 2P2P (Figure 3.1b). The vertical line through PP and −P-P meets EE in no third affine point. To define P+(−P)P + (-P) we therefore adjoin the point OO “at infinity”, which lies on every vertical line, so that P+(−P)=OP + (-P) = O (Figure 3.1c).[5]

The group law on an elliptic curve

Figure 3.1. The group law on an elliptic curve: (a) addition of two distinct points, (b) adding a point to itself, (c) the vertical line through PP and −P-P, which explains the role of the point at infinity.

Formulas. Let P=(x1,y1)P = (x_1, y_1) and Q=(x2,y2)Q = (x_2, y_2), and let the line through them be L:y=λx+νL : y = \lambda x + \nu, with

λ={y2−y1x2−x1,if P≠Q,3x12+A2y1,if P=Q,ν=y1−λx1.(11)\lambda= \begin{cases} \dfrac{y_2-y_1}{x_2-x_1}, & \text{if } P \ne Q,\\ \dfrac{3x_1^2+A}{2y_1}, & \text{if } P = Q, \end{cases} \qquad\nu= y_1-\lambda x_1. \tag*{(11)}

Then P+Q=(x3,y3)P + Q = (x_3, y_3) with

x3=λ2−x1−x2,y3=−(λx3+ν),(12)x_3 = \lambda^2-x_1-x_2,\qquad y_3 = -(\lambda x_3+\nu), \tag*{(12)}

and −(x,y)=(x,−y)-(x, y) = (x, -y). A vertical chord (x1=x2,y1=−y2)(x_1 = x_2, y_1 = -y_2) gives OO.

Theorem 1 [5] With this addition, E(Q)E(\mathbb{Q}) is an abelian group with identity OO: it is closed under addition, the operation is associative and commutative, P+O=PP + O = P and P+(−P)=OP + (-P) = O for all P∈E(Q)P \in E(\mathbb{Q}).

Bachet’s duplication formula. For P=QP = Q the formulas above reduce to Bachet’s duplication formula (1621), found while expressing an integer as the difference of a square and a cube in rational numbers,

y2−x3=c,c∈Z.(13)y^2-x^3=c,\qquad c\in\mathbb{Z}. \tag*{(13)}

If (x,y)∈Q2(x,y)\in\mathbb{Q}^2 with y≠0y\ne0 is a solution, then

(x4−8cx−x6−20cx3+8c24y2,)(14)\left(\frac{x^4-8cx-x^6-20cx^3+8c^2}{4y^2},\frac{}{} \right) \tag*{(14)}

is also a rational solution. Hence if c∉{1,−432}c\notin\{1,-432\} and xy≠0xy\ne0, the integer cc can be written as a difference of a square and a cube of nonzero rational numbers in infinitely many ways.[9]

Structure of E(Q)E(\mathbb{Q}): Torsion and Rank

Theorem 2 (E(Q)E(\mathbb{Q}): Mordell–Weil Group) [7] E(Q)E(\mathbb{Q}) is a finitely generated abelian group. In other words, there are points P1,…,PnP_1,\ldots,P_n such that any other point Q∈E(Q)Q\in E(\mathbb{Q}) can be expressed as a linear combination

Q=a1P1+a2P2+⋯+anPn,for some ai∈Z.Q=a_1P_1+a_2P_2+\cdots+a_nP_n,\qquad\text{for some }a_i\in\mathbb{Z}.

By the Mordell–Weil theorem and the structure theory of finitely generated abelian groups,

E(Q)≅E(Q)torsion⊕ZRE,E(Q)torsion={P∈E(Q)∣nP=O for some n∈N}.(15)E(\mathbb{Q}) \cong E(\mathbb{Q})_{\mathrm{torsion}} \oplus\mathbb{Z}^{R_E}, \qquad E(\mathbb{Q})_{\mathrm{torsion}} = \{P \in E(\mathbb{Q}) \mid nP = O \text{ for some } n \in\mathbb{N}\}. \tag*{(15)}

The decomposition is not canonical. The torsion subgroup is the finite group of points of finite order. The free part ZRE\mathbb{Z}^{R_E}, with RE≥0R_E \ge0, is generated by RER_E independent points of infinite order, that is, points PP with nP≠OnP \ne O for all nonzero n∈Zn \in\mathbb{Z}. The integer RER_E is the rank of E/QE/\mathbb{Q}. The rational torsion points of an example curve are shown in Figure 3.2.

The rational torsion points of $y^2=x^3+1$

Figure 3.2. The rational torsion points of y2=x3+1y^2=x^3+1, where P=(2,3)P=(2,3) generates E(Q)torsion≅Z/6ZE(\mathbb{Q})_{\mathrm{torsion}}\cong\mathbb{Z}/6\mathbb{Z}; the point 6P=O6P=O at infinity is not shown.

Theorem 3 (Mazur) [7] For an elliptic curve E/QE/\mathbb{Q}, the E(Q)torsionE(\mathbb{Q})_{\mathrm{torsion}} is isomorphic to exactly one of the following groups:

Z/NZwith 1≤N≤10 or N=12,\mathbb{Z}/N\mathbb{Z} \qquad\text{with } 1 \le N \le10 \text{ or } N=12,
Z/2Z⊕Z/2MZwith 1≤M≤4.\mathbb{Z}/2\mathbb{Z} \oplus\mathbb{Z}/2M\mathbb{Z} \qquad\text{with } 1 \le M \le4.

In particular, if the order of a rational point P∈E(Q)P \in E(\mathbb{Q}) is greater than 12, then PP has infinite order, and E(Q)E(\mathbb{Q}) contains infinitely many distinct rational points.

Although the rank RER_E cannot be read off from the equation, it admits upper bounds when EE has a rational point of order 2. Let ν(n)\nu(n) be the number of distinct primes dividing a nonzero integer nn, so that ν(360)=3\nu(360)=3 and ν(±1)=0\nu(\pm1)=0.

Theorem 4 (Rank bound) [7] Let E:y2=x3+ax2+bxE:y^2=x^3+ax^2+bx with a,b∈Za,b\in\mathbb{Z}. Then

RE≤ν(a2−4b)+ν(b)−1.(16)R_E \le\nu(a^2-4b)+\nu(b)-1. \tag*{(16)}

More generally, if E/QE/\mathbb{Q} has a nontrivial rational 2-torsion point, then RE≤m+2α−1R_E \le m+2\alpha-1, where mm and α\alpha are the numbers of primes at which EE has multiplicative and additive bad reduction, respectively.

Proposition 1 [7] If E:y2=(x−e1)(x−e2)(x−e3)E:y^2=(x-e_1)(x-e_2)(x-e_3) with e1,e2,e3∈Ze_1,e_2,e_3\in\mathbb{Z}, then RE≤2ν(ΔE)R_E\le2\nu(\Delta_E).

A rational 2-torsion point exists exactly when the cubic has a rational root, and moving that root to x=0x=0 puts EE in the form of Theorem 4. The command ECPRankBound evaluates all bounds that apply and returns the smallest. These are upper bounds only: for y2=x3−xy^2=x^3-x the bound is 0 and the rank is 0, whereas for y2=x3−1156xy^2=x^3-1156x the bound is 3 and the rank is 2 [7]. For a curve without a rational point of order 2, such as 37a1, the command returns Missing["NoRational2Torsion"]. The command ECPRankUpperBound is only a heuristic and not a theorem (it overestimates the rank of y2=x3−xy^2=x^3-x).

Heights and Linear Independence of Rational Points

The material follows [7]. Rational points P1,…,Pm∈E(Q)P_1,\ldots,P_m\in E(\mathbb{Q}) are linearly independent if

n1P1+n2P2+⋯+nmPm=T,(17)n_1P_1+n_2P_2+\cdots+n_mP_m=T, \tag*{(17)}

with ni∈Zn_i \in\mathbb{Z} and TT a torsion point, forces n1=⋯=nm=0n_1=\cdots=n_m=0. To test this, we use heights. The height of mn∈Q\frac{m}{n}\in\mathbb{Q}, with gcd⁡(m,n)=1\gcd(m,n)=1, is h(mn)=log⁡(max⁡{∣m∣,∣n∣})h\left(\frac{m}{n}\right)=\log(\max\{|m|,|n|\}), and for a point P=(x,y)∈E(Q)P=(x,y)\in E(\mathbb{Q}) we set H(P)=h(x)H(P)=h(x). The canonical height of P∈E(Q)P\in E(\mathbb{Q}) is

h^(P)=12lim⁡N→∞H(2NP)4N,(18)\hat{h}(P)=\frac{1}{2}\lim_{N\to\infty}\frac{H(2^N P)}{4^N}, \tag*{(18)}

where 2NP2^N P is computed with the group law. For P,Q∈E(Q)P,Q\in E(\mathbb{Q}) and m∈Zm\in\mathbb{Z} it satisfies

h^(P+Q)+h^(P−Q)=2h^(P)+2h^(Q),h^(mP)=m2h^(P),h^(P)≥0,(19)\hat{h}(P+Q)+\hat{h}(P-Q)=2\hat{h}(P)+2\hat{h}(Q),\qquad\hat{h}(mP)=m^2\hat{h}(P),\qquad\hat{h}(P)\geq0, \tag*{(19)}

with h^(P)=0\hat{h}(P)=0 if and only if PP is a torsion point. The Néron–Tate pairing is defined by

⟨P,Q⟩=12(h^(P+Q)−h^(P)−h^(Q)).(20)\langle P,Q\rangle=\frac{1}{2}\left(\hat{h}(P+Q)-\hat{h}(P)-\hat{h}(Q)\right). \tag*{(20)}

It is symmetric and bilinear, ⟨P,P⟩=h^(P)\langle P,P\rangle=\hat{h}(P), and so ⟨P,P⟩=0\langle P,P\rangle=0 exactly for torsion points: this distinguishes torsion points from points of infinite order. (This is the normalisation used by ECPHeightPairing, see Appendix § 13.) For points P1,…,PrP_1,\ldots,P_r the elliptic height matrix is

H=(⟨Pi,Pj⟩)1≤i,j≤r.(21)\mathcal{H}=\left(\langle P_i,P_j\rangle\right)_{1\leq i,j\leq r}. \tag*{(21)}

Theorem 5 [7]

(a) If det⁡(H)≠0\det(\mathcal{H})\neq0, the points {Pi}i=1r\{P_i\}_{i=1}^r are linearly independent and the rank of E(Q)E(\mathbb{Q}) is at least rr.

(b) If det⁡(H)=0\det(\mathcal{H})=0 and 0≠(n1,…,nr)∈Zr0\neq(n_1,\ldots,n_r)\in\mathbb{Z}^r lies in ker⁡(H)\ker(\mathcal{H}), then the points are linearly dependent and ∑k=1rnkPk=T\sum_{k=1}^r n_kP_k=T for a torsion point T∈E(Q)T\in E(\mathbb{Q}).

Relevant ECPack commands (each name links to its entry in Appendix § 13).

Point arithmetic: ECPAdd, ECPMultiply, ECPChordAndTangent, ECPBachetDuplication, ECPOnCurveQ, ECPPointQ, ECPAreProjectivelyEquivalent

Torsion and point orders: ECPFindTorsionPoints, ECPTorsionSubgroup, ECPPointOrder, ECPFindPointOrder

Searching for points, generators and rank: ECPSearchPoints, ECPFindGenerators, ECPAnalyticRank

Heights, pairings and independence: ECPNaiveHeight, ECPCanonicalHeight, ECPHeightPairing, ECPHeightMatrix, ECPIndependentQ

Prime divisors and rank bounds: ECPPrimeDivisorCount, ECPRankBound, ECPLocalData, ECPRankUpperBound

Elliptic Curves over Finite Fields

Elliptic curves over finite fields are one of the places where the geometry of the curve and the arithmetic of its points meet in a concrete way. Over Q\mathbb{Q}, one often studies individual rational points and the group law on the curve. Over a finite field Fq\mathbb{F}_q, the picture changes: the set of points is finite, and an important question becomes not whether the points exist, but how many there are. This counting problem plays a central role in algorithmic number theory and elliptic curve cryptography.

Curve structure

An elliptic curve over Fq\mathbb{F}_q, where q=prq=p^r for a prime pp, in short Weierstrass form[8] is as follows

E:y2=x3+Ax+B,A,B∈Fq,(22)E:\qquad y^2=x^3+Ax+B,\qquad A,B\in\mathbb{F}_q, \tag*{(22)}

For a nonsingular curve[8]

4A3+27B2≠0.(23)4A^3+27B^2\neq0. \tag*{(23)}

Equivalently, the discriminant[8]

Δ=−16(4A3+27B2)(24)\Delta=-16(4A^3+27B^2) \tag*{(24)}

is nonzero as well.

E(Fq)E(\mathbb{F}_q) is the set of all affine points of EE whose coordinates belong to Fq\mathbb{F}_q, together with the point at infinity:

E(Fq)={(x,y)∈Fq2:y2=x3+Ax+B}∪{O}.(25)E(\mathbb{F}_q)=\{(x,y)\in\mathbb{F}_q^2:y^2=x^3+Ax+B\}\cup\{\mathcal{O}\}. \tag*{(25)}

Note that

  • When a curve is defined over Fq\mathbb{F}_q, it means that its defining equation has coefficients AA, BB in Fq\mathbb{F}_q.

  • A point is rational over Fq\mathbb{F}_q if its coordinates lie in Fq\mathbb{F}_q.

  • A curve defined over Fq\mathbb{F}_q can also have points whose coordinates lie in a larger field. Thus, for every n≥1n \ge1 (see Appendix § 11.2),

E(Fq)⊆E(Fqn).(26)E(\mathbb{F}_q) \subseteq E(\mathbb{F}_{q^n}). \tag*{(26)}

Advanced Point Counting

A simple heuristic suggests that Nq=#E(Fq)N_q = \#E(\mathbb{F}_q) the number of Fq\mathbb{F}_q-rational points on EE should be close to q+1q+1, since for each x∈Fqx \in\mathbb{F}_q there are at most two possible values of yy, and the point at infinity contributes one extra point.

Definition 2 (The Frobenius Endomorphism) [5] (see Appendix § 12) Suppose EE is defined over the finite field Fq\mathbb{F}_q:

ϕq:E→E,ϕq(x,y)=(xq,yq)(27)\phi_q : E \to E,\qquad\phi_q(x,y) = (x^q,y^q) \tag*{(27)}

is the natural map associated with the finite-field structure, and it encodes the curve’s arithmetic very efficiently. From this point of view, point counting is closely related to understanding how Frobenius acts on the curve. This is the reason the trace aqa_q appears so naturally in both theory and computation.

The Trace of Frobenius [5] (see Appendix § 12.2): The quantity

aq=q+1−#E(Fq)(28)a_q = q + 1 - \#E(\mathbb{F}_q) \tag*{(28)}

is called the trace of Frobenius, because one way to calculate it is to use the Frobenius map to obtain a linear transformation on a certain vector space Vℓ(E)V_\ell(E) that is associated with the Tate module. Then aqa_q is the trace of that linear transformation.

Theorem 6 (Hasse’s theorem) [8] makes this precise:

∣Nq−(q+1)∣≤2q,\left|N_q - (q+1)\right| \le2\sqrt{q},

So, although the exact count depends on the curve, it is always constrained to lie in a fairly small interval around $q+1.

It is often convenient to package the deviation from the expected value into the trace of Frobenius,

aq=q+1−Nq.a_q = q + 1 - N_q.

Then Hasse’s bound becomes simply ∣aq∣≤2q\lvert a_q\rvert\le2\sqrt{q}.

For small fields, one can count points directly by checking each x∈Fqx \in\mathbb{F}_q and determining whether the right-hand side of the curve equation is a quadratic residue. This works well for small examples and for verifying formulas by hand, but it quickly becomes too slow when qq is large. This is where advanced point-counting algorithms come into play.

Schoof’s Algorithm

Schoof’s algorithm [10] provides a breakthrough technique for computing NqN_q. Using this technique, we need not directly compute the trace of Frobenius aqa_q; instead, we compute the trace of Frobenius modulo many small primes ℓ≠char⁡(Fq)\ell\ne\operatorname{char}(\mathbb{F}_q) and then recover aqa_q via the Chinese Remainder Theorem. So, the problem becomes one of studying how Frobenius acts on the ℓ\ell-torsion subgroup E[ℓ]E[\ell]. Because on the ℓ\ell-torsion points, E[ℓ]E[\ell], Frobenius satisfies ϕq2−aqϕq+q=0\phi_q^2-a_q\phi_q+q=0. Modulo ℓ\ell, this becomes a finite computation.

For each small prime ℓ≠char⁡(Fq)\ell\ne\operatorname{char}(\mathbb{F}_q), Schoof determines

aq(modℓ).a_q \pmod{\ell}.

The congruences for aqa_q, obtained modulo different primes ℓ\ell, are combined using the Chinese Remainder Theorem. Since the moduli are pairwise coprime, the combined modulus is the product of the individual moduli. Once this product of small primes ℓ\ell is larger than the width of Hasse’s interval 4q4\sqrt{q}, Hasse’s bound ∣aq∣≤2q\lvert a_q\rvert\le2\sqrt{q} determines a unique value of aqa_q, since there can be only one integer in the Hasse interval satisfying all the congruences. Finally,

#E(Fq)=q+1−aq.(29)\#E(\mathbb{F}_q) = q + 1 - a_q. \tag*{(29)}

The computation modulo ℓ\ell. Let q=pq=p be prime, E:y2=x3+Ax+BE:y^2=x^3+Ax+B and ℓ≠p\ell\ne p an odd prime. The xx-coordinates of the nonzero points of E[ℓ]E[\ell] are the roots of the division polynomial ψℓ∈Fp[x]\psi_\ell\in\mathbb{F}_p[x], of degree (ℓ2−1)/2(\ell^2-1)/2. All computations are carried out in the ring Fp[x]/(ψℓ)\mathbb{F}_p[x]/(\psi_\ell), in which P=(x,y)P=(x,y) is a generic point of E[ℓ]E[\ell] and the Frobenius acts as ϕ(P)=(xp,(x3+Ax+B)(p−1)/2y)\phi(P)=(x^p,(x^3+Ax+B)^{(p-1)/2}y). With qˉ=p mod ℓ\bar{q}=p\bmod\ell, one adds ϕ2(P)\phi^2(P) and [qˉ]P[\bar{q}]P with the chord-and-tangent formulas of Section 3 and looks for τ∈{1,…,ℓ−1}\tau\in\{1,\ldots,\ell-1\} with

ϕ2(P)+[qˉ]P=[τ]ϕ(P);(30)\phi^2(P)+[\bar{q}]P=[\tau]\phi(P); \tag*{(30)}

then ap≡τ(modℓ)a_p\equiv\tau\pmod\ell. If ϕ2(P)\phi^2(P) and [qˉ]P[\bar{q}]P have the same xx-coordinate for some P≠OP\ne O, then ϕ2(P)=±[qˉ]P\phi^2(P)=\pm[\bar{q}]P and there are two cases: either ap≡0a_p\equiv0, or qˉ≡w2(modℓ)\bar{q}\equiv w^2\pmod\ell is a square, ϕ(P)=±[w]P\phi(P)=\pm[w]P and ap≡±2w(modℓ)a_p\equiv\pm2w\pmod\ell, the sign being read off from the yy-coordinates. For ℓ=2\ell=2 the answer is simpler: apa_p is even if and only if x3+Ax+Bx^3+Ax+B has a root in Fp\mathbb{F}_p, that is, if and only if gcd⁡(xp−x,x3+Ax+B)≠1\gcd(x^p-x,x^3+Ax+B)\ne1. All powers xpx^p are computed by repeated squaring modulo ψℓ\psi_\ell, and the primes ℓ\ell needed to exceed 4p4\sqrt{p} are of size O(log⁡p)O(\log p), so the running time is polynomial in log⁡p\log p.

Implementation in ECPack. ECPSchoofPointCount implements the algorithm above for a curve over a prime field Fp\mathbb{F}_p in any of the accepted forms, with arithmetic modulo ψℓ\psi_\ell done by the polynomial routines of the Wolfram Language over Z/pZ\mathbb{Z}/p\mathbb{Z}. It uses the primes ℓ=2,3,5,…\ell=2,3,5,\ldots (omitting ℓ=p\ell=p) until their product exceeds 4p4\sqrt{p}, combines the residues with the Chinese Remainder Theorem, and checks the result against Hasse’s bound. The enumeration used by ECPSEAPointCount is limited to p≲106p\lesssim10^6, whereas Schoof’s algorithm handles much larger primes, here p=1012+39p=10^{12}+39:

In[83]:= ECPSchoofPointCount[{2, 3}, 1000000000039]
Out[83]= 1000000769568

Here ap=−769528a_p=-769528, and the result can be checked independently by verifying that #E(Fp)⋅P=O\#E(\mathbb{F}_p)\cdot P=O for random points PP with ECPMultiplyFp.

Relevant ECPack commands (each name links to its entry in Appendix § 13).
Point counting, group structure and point orders: ECPSchoofPointCount, ECPSEAPointCount, ECPGroupFp, ECPPointOrderFp
Point arithmetic and membership: ECPAddFp, ECPMultiplyFp, ECPPointQFp
Arithmetic in Fpr\mathbb{F}_{p^r}: ECPFiniteFieldInfo, ECPFqAdd, ECPFqMultiply, ECPFqInverse, ECPFqElement, ECPFqVector
Models and invariants over Fq\mathbb{F}_q: ECPToShortWeierstrassFp, ECPJInvariant

Table 4 (PDF p. 10).

Curve Reductions

When an elliptic curve is defined over Q\mathbb{Q}, it is natural to ask what the curve looks like after reducing its coefficients modulo a prime pp. This idea is simple but one of the most useful bridges between global and local arithmetic. What actually happens is that, suppose we have an elliptic curve defined over Q\mathbb{Q}; reducing it modulo a prime pp produces an elliptic curve over Fp\mathbb{F}_p. A curve may behave very nicely over Q\mathbb{Q}, yet its reduction modulo a given prime pp, which is an elliptic curve over Fp\mathbb{F}_p, can reveal subtle singular behavior. In this way, reduction modulo pp gives a local snapshot of the curve, and studying these snapshots prime by prime is a standard part of the arithmetic theory of elliptic curves.

Minimal Model

Before reducing the curve, one usually tries to choose the simplest possible model. Since the same elliptic curve can be written by many equivalent Weierstrass equations, it is important to work with a model that does not carry unnecessary powers of primes in its discriminant. This leads to the notion of a minimal Weierstrass model.

Definition 3 (Minimal Weierstrass Model) [7] Let E/QE/\mathbb{Q} be an elliptic curve. A Weierstrass equation for EE is called minimal if, among all integral Weierstrass equations for the same curve, its discriminant has minimal pp-adic valuation at every prime pp.

Once a minimal model is chosen, one reduces the coefficients modulo pp and obtains a curve over Fp\mathbb{F}_p. If the reduced equation is still non-singular, then the curve has good reduction at pp. If the reduced equation becomes singular, then the curve has bad reduction. The discriminant is the key quantity here: if the discriminant does not vanish modulo pp, then the reduced curve remains smooth; if it does vanish, the curve acquires a singular point.

Definition 4 (Reduction Modulo pp) [8] Let

E:y2=x3+Ax+B(31)E: y^2 = x^3 + Ax + B \tag*{(31)}

be an elliptic curve with A,B∈ZA, B \in\mathbb{Z}. The reduction of EE modulo pp is the curve over Fp\mathbb{F}_p obtained by reducing the coefficients AA and BB modulo $p.

For a short Weierstrass equation, the discriminant is

Δ=−16(4A3+27B2).(32)\Delta= -16(4A^3 + 27B^2). \tag*{(32)}

Thus, the first test for reduction is very direct:

Δ≠0(modp)⟹good reduction at p.(33)\Delta\ne0 \pmod{p} \quad\Longrightarrow\quad\text{good reduction at }p. \tag*{(33)}
Δ=0(modp)⟹bad reduction at p.(34)\Delta= 0 \pmod{p} \quad\Longrightarrow\quad\text{bad reduction at }p. \tag*{(34)}

In practice, for a model that is minimal at pp, the singularity can be refined further by looking at the invariant c4c_4.

Δ≡0(modp)butc4≠0(modp)⟹multiplicative reduction at p.(35)\Delta\equiv0 \pmod{p} \quad\text{but} \quad c_4 \ne0 \pmod{p} \quad\Longrightarrow\quad\text{multiplicative reduction at }p. \tag*{(35)}
Δ≡0(modp)andc4=0(modp)⟹additive reduction at p.(36)\Delta\equiv0 \pmod{p} \quad\text{and} \quad c_4 = 0 \pmod{p} \quad\Longrightarrow\quad\text{additive reduction at }p. \tag*{(36)}

This distinction is important because it tells us not only that the curve has degenerated, but also how it has degenerated.

Theorem 7 (Good Reduction Criterion) [11] If an elliptic curve has a minimal Weierstrass model at a prime pp, then the reduced curve over Fp\mathbb{F}_p is smooth if and only if the discriminant is nonzero modulo pp. In that case, the curve has good reduction at pp.

A very useful consequence of good reduction is that torsion points of order prime to pp behave well under reduction. More precisely, if E/QE/\mathbb{Q} has good reduction at pp and mm is not divisible by pp, then the reduction map gives an injective homomorphism [8]

E(Q)[m]⟶E~(Fp).E(\mathbb{Q})[m] \longrightarrow\widetilde{E}(\mathbb{F}_p).

So, at good primes, finite-order rational points do not collapse unexpectedly when reduced modulo pp. This is one reason why reduction is so useful in explicit computations.

If the reduced curve is singular, one often refines the discussion using Kodaira symbols. In the simplest language, I0I_0 corresponds to good reduction, InI_n to multiplicative reduction, and the symbols IIII, IIIIII, IVIV, In∗I_n^*, II∗II^*, III∗III^*, IV∗IV^* describe the various additive cases. This classification is more detailed than what is needed for a first pass, but it shows that reduction modulo pp is not merely a yes-or-no question; it carries structured information about the geometry of the curve.

The reduction process can be carried out explicitly on individual curves: one first finds a minimal model, computes the discriminant, and reduces modulo a chosen prime to inspect whether the reduction is good, multiplicative, or additive.

From a computational standpoint, ECPack is well-suited to this topic. It can help you find a minimal model, compute the discriminant, reduce the curve modulo a chosen prime, and inspect whether the reduction is good, multiplicative, or additive. That makes it easier to move between the abstract definition and an actual curve written in code. It is also helpful when one wants to compare several primes at once, because the package can quickly show which primes are bad and which ones preserve smooth reduction. In that sense, the package turns reduction theory into something one can test and experiment with directly.

Relevant ECPack commands (each name links to its entry in Appendix § 13).

Table 5.

Minimal models: ECPIsMinimal, ECPIsMinimalShort, ECPMinimalQ, ECPMinimalModel, ECPMinimalModelShort, ECPFindLocalReduction, ECPToMinimalPoint, ECPFromMinimalPoint, ECPTransformWeierstrass

Discriminant and invariants: ECPWeierstrassDiscriminant, ECPWInvariants, ECPShortDiscriminant, ECPJInvariant

Local data: Tate’s algorithm and conductor: ECPTate, ECPLocalData, ECPConductor

The reduced curve over Fp\mathbb{F}_p: ECPToShortWeierstrassFp, ECPGroupFp, ECPSchoofPointCount, ECPSEAPointCount

Elliptic Families and Kodaira Classification

This section, based on [12, 13, 14, 15], provides only the introductory overview needed for the package commands. If the coefficients of a Weierstrass equation depend on a parameter tt, then one gets a one-parameter family of elliptic curves. The zeros of the discriminant mark the singular fibres of the family, and Kodaira’s symbols provide a compact way to describe their local types. In the package, this information is used by commands that list singular fibres, report Euler numbers, and translate a fibre type into the associated gauge-algebra data when that dictionary is relevant.

Typeord c4c_4ord c6c_6ord Δ\DeltaEuler number
I0I_0≥0\ge0≥0\ge00000
InI_n (n≥1n \ge1)0000nnnn
IIII≥1\ge1112222
IIIIII11≥2\ge23333
IVIV≥2\ge2224444
I0∗I_0^*≥2\ge2≥3\ge36666
In∗I_n^* (n≥1n \ge1)2233n+6n+6n+6n+6
IV∗IV^*≥3\ge3448888
III∗III^*33≥5\ge59999
II∗II^*≥4\ge45510101010

Table 1 (PDF p. 12). Kodaira’s table: the type of a singular fibre from the orders of vanishing of c4c_4, c6c_6 and Δ\Delta at a point where the Weierstrass equation is minimal.

A minimal model at a point t0t_0 is detected by the vanishing orders of the invariants c4c_4, c6c_6, and Δ\Delta. For a first reading, it is enough to remember that the fibre is smooth when Δ(t0)≠0\Delta(t_0) \ne0, and that the symbols InI_n, IIII, IIIIII, IVIV, In∗I_n^*, II∗II^*, III∗III^*, and IV∗IV^* are the standard names used by the commands in this package. The same local data can also be viewed at t=∞t = \infty by passing to s=1/ts = 1/t, which is why the package can treat families over P1\mathbb{P}^1 uniformly.

The related command ECPFibreList returns the singular fibres and their Euler numbers, while ECPFibreAt inspects a fibre at a chosen parameter value and ECPGaugeAlgebra records the corresponding gauge-algebra dictionary when needed.

Relevant ECPack commands (each name links to its entry in Appendix § 13).

Kodaira classification: ECPKodairaType, ECPFibreAt, ECPFibreAtInfinity, ECPFibreList

Miscellaneous: ECPJFunction, ECPCoulombDimension, ECPGaugeAlgebra, ECPTateForm, ECPTorsionFamily

Cryptography and Algebraic Pairings

The two preceding sections studied the finite groups E(Fq)E(\mathbb{F}_q) and the curves obtained from a curve over Q\mathbb{Q} by reduction modulo pp. These finite groups are also the setting of elliptic-curve cryptography, which uses the group law over Fq\mathbb{F}_q directly, and of pairings, which relate the additive group E(Fq)E(\mathbb{F}_q) to the multiplicative group Fq×\mathbb{F}_q^{\times}. In this section we first recall the discrete logarithm problem on an elliptic curve and the ElGamal protocol, which ECPack implements over prime fields. We then describe Miller’s algorithm and the Weil and Tate pairings, which are implemented over Fp\mathbb{F}_p and Fpr\mathbb{F}_{p^r}, together with a routine that produces a basis of the full nn-torsion subgroup.

Elliptic Curve Cryptography and ElGamal Encryption

Elliptic curves became especially important in modern cryptography because they offer a very efficient group law, while the inverse problem remains difficult in practice. Over a finite field, point addition and scalar multiplication can be performed quickly, but recovering the scalar from a given multiple of a point is believed to be computationally hard. This asymmetry is the starting point for elliptic curve cryptography (ECC) [16, 17, 8, 18].

A central problem here is the Elliptic Curve Discrete Logarithm Problem (ECDLP). Suppose PP is a point on an elliptic curve and Q=nPQ = nP for some unknown integer nn. The ECDLP asks for the recovery of nn from PP and QQ. For suitably chosen curves, no efficient general method is known for solving this problem [8], which is why elliptic curves are useful for secure communication. In contrast, the forward operation P↦nPP \mapsto nP is easy to compute, especially with double-and-add methods and related fast scalar-multiplication algorithms.

A standard application is the elliptic-curve version of the ElGamal protocol [19, 16]. In this setting, a public point PP is chosen on the curve, together with a public point Q=dPQ = dP, where dd is the secret key. To encrypt a message, one first encodes the message as a point MM on the curve and then chooses a random integer kk. The ciphertext is the pair

C1=kP,C2=M+kQ.(37)C_1 = kP,\qquad C_2 = M + kQ. \tag*{(37)}

Since Q=dPQ = dP, the legitimate receiver can recover the message by computing

M=C2−dC1.(38)M = C_2 - dC_1. \tag*{(38)}

The security of this procedure depends on the difficulty of recovering dd from PP and QQ. The group law makes encryption and decryption efficient, while the underlying discrete logarithm problem makes unauthorized recovery difficult. ECPack implements Koblitz’s embedding of an integer message as a point on the curve [16] together with ElGamal encryption and decryption over prime fields. The parameters used in the manual are two values: the routines are meant for experimentation with the arithmetic, not for secure communication.

Pairings and Miller’s Algorithm

In more advanced cryptographic constructions, one needs a bilinear pairing. A pairing takes two points of an elliptic curve and returns an element of the multiplicative group of the field, so that the additive group law of the curve is converted into a multiplicative one in a controlled way. Throughout this subsection EE is defined over Fq\mathbb{F}_q, q=prq = p^r, and nn is a positive integer prime to pp. Over an algebraic closure, E[n]≅(Z/nZ)2E[n] \cong(\mathbb{Z}/n\mathbb{Z})^2, and we write μn\mu_n for the group of nn-th roots of unity.

The Weil Pairing. The most classical pairing is the Weil pairing.

Definition 5 (Weil Pairing) [8] The Weil pairing is a map

en:E[n]×E[n]→μn(39)e_n : E[n] \times E[n] \to\mu_n \tag*{(39)}

with the following properties:

(a) bilinearity: en(aP,bQ)=en(P,Q)abe_n(aP,bQ) = e_n(P,Q)^{ab} for integers a,ba,b and P,Q∈E[n]P,Q \in E[n];

(b) alternating: en(P,P)=1e_n(P,P) = 1, and hence en(Q,P)=en(P,Q)−1e_n(Q,P) = e_n(P,Q)^{-1};

(c) non-degeneracy: if en(P,Q)=1e_n(P,Q) = 1 for all Q∈E[n]Q \in E[n], then P=OP = \mathcal{O}.

If P,QP,Q is a basis of E[n]E[n], then en(P,Q)e_n(P,Q) is a primitive nn-th root of unity. In particular, if the full nn-torsion subgroup is contained in E(Fq)E(\mathbb{F}_q), then μn⊂Fq\mu_n \subset\mathbb{F}_q, that is, nn divides q−1q - 1.

Miller’s Function and Miller’s Algorithm [20]. The Weil pairing is computed with Miller’s algorithm, whose basic object is a rational function on EE. For a point PP and an integer n≥1n \ge1, let fn,Pf_{n,P} be a rational function with divisor

div⁡fn,P=n(P)−([n]P)−(n−1)(O),(40)\operatorname{div} f_{n,P} = n(P) - ([n]P) - (n - 1)(O), \tag*{(40)}

normalised as in Miller’s algorithm; for P∈E[n]P \in E[n] this divisor is n(P)−n(O)n(P) - n(O). Let ℓT,R\ell_{T,R} denote the line through TT and RR (the tangent if T=RT=R) and vSv_S the vertical line through SS. Comparing divisors, one finds

fi+j,P=fi,Pfj,Pℓ[i]P,[j]Pv[i+j]P,(41)f_{i+j,P} = f_{i,P} f_{j,P} \frac{\ell_{[i]P,[j]P}}{v_{[i+j]P}}, \tag*{(41)}

which is the geometric chord-and-tangent construction of Section 3 in the language of divisors. Miller’s algorithm evaluates fn,P(Q)f_{n,P}(Q) at a point Q≠OQ \ne O by applying (41) along the binary expansion of nn (double-and-add). At each step, only the values of the line and of the vertical line at QQ are computed, so the function itself is never written down, and the cost is O(log⁡n)O(\log n) operations in Fq\mathbb{F}_q [20]. The evaluation fails if QQ is a zero or a pole of one of the intermediate functions, for instance when QQ lies in the subgroup generated by PP.

For P,Q∈E[n]P,Q \in E[n] the Weil pairing is given by

en(P,Q)=(−1)nfn,P(Q)fn,Q(P).(42)e_n(P,Q) = (-1)^n \frac{f_{n,P}(Q)}{f_{n,Q}(P)}. \tag*{(42)}

Both values in (42) are defined and nonzero exactly when PP and QQ are independent; if one of them lies in the cyclic group generated by the other, the pairing equals 1.

The Tate Pairing [21, 22, 8]. The second pairing in common use is the Tate pairing. It is defined on E(Fq)[n]×E(Fq)/nE(Fq)E(\mathbb{F}_q)[n] \times E(\mathbb{F}_q)/nE(\mathbb{F}_q) and takes values in Fq∗/(Fq∗)n\mathbb{F}_q^*/(\mathbb{F}_q^*)^n. If nn divides q−1q-1, one makes the value unique by raising it to the power (q−1)/n(q-1)/n, which gives the reduced Tate pairing

tn(P,Q)=fn,P(Q)(q−1)/n∈μn.(43)t_n(P,Q) = f_{n,P}(Q)^{(q-1)/n} \in\mu_n. \tag*{(43)}

It is bilinear and non-degenerate but, unlike the Weil pairing, it is not alternating, so tn(P,P)t_n(P,P) need not equal 1. Its evaluation requires only one Miller function rather than two. The condition n∣q−1n \mid q-1 is the reason why one often has to pass to an extension field: the smallest kk with n∣qk−1n \mid q^k-1 is called the embedding degree of nn [23, 22].

Implementation in ECPack. ECPack evaluates the Miller function with ECPMillerFp, and computes the Weil pairing (42) and the reduced Tate pairing with ECPWeilPairingFp and ECPTatePairingFp. All three work over Fp\mathbb{F}_p and over Fpr\mathbb{F}_{p^r}, in every characteristic for which the pairing is defined, and for a curve in any of the accepted forms. The routine ECPTorsionBasisFp finds a basis {P,Q}\{P,Q\} of E[n]E[n] inside E(Fq)E(\mathbb{F}_q), with PP of exact order nn and en(P,Q)e_n(P,Q) a primitive nn-th root of unity; this requires E[n]⊂E(Fq)E[n] \subset E(\mathbb{F}_q). For the curve y2=x3+2y^2=x^3+2 over F7\mathbb{F}_7, one has 9 points and E(F7)≅Z/3×Z/3E(\mathbb{F}_7) \cong\mathbb{Z}/3 \times\mathbb{Z}/3, so E[3]⊂E(F7)E[3] \subset E(\mathbb{F}_7) and 3∣7−13 \mid7-1:

In[80]:= ECPTorsionBasisFp[3, {0, 2}, 7]
Out[80]= {{0, 4}, {5, 1}}

In[81]:= ECPWeilPairingFp[3, {0, 4}, {5, 1}, {0, 2}, 7]
Out[81]= 2

In[82]:= {ECPWeilPairingFp[3, {0, 4}, {0, 4}, {0, 2}, 7], ECPWeilPairingFp[3, {5, 1}, {0, 4}, {0, 2}, 7]}
Out[82]= {1, 4}

Since 23≡1(mod7)2^3 \equiv1 \pmod7 and 2≠12 \ne1, the value e3(P,Q)=2e_3(P,Q)=2 is a primitive cube root of unity, as it must be for a basis. The pairing is alternating, e3(P,P)=1e_3(P,P)=1, and e3(Q,P)=4=2−1e_3(Q,P)=4=2^{-1} modulo 7.

Relevant ECPack commands (each name links to its entry in Appendix § 13).

Group law over Fp\mathbb{F}_p: ECPAddFp, ECPMultiplyFp, ECPPointOrderFp, ECPGroupFp

Message embedding and ElGamal: ECPFFindPointFp, ECPElGamalEncodeFp, ECPElGamalDecodeFp

Miller’s algorithm and pairings: ECPMillerFp, ECPWeilPairingFp, ECPTatePairingFp, ECPTorsionBasisFp

Future Directions

We plan to extend ECPack.wl in the following directions.

  1. Torsion via Doud’s Algorithm. ECPFindTorsionPoints uses the Nagell–Lutz theorem, which requires factoring the discriminant and falls back to a bounded search for large ∣Δ∣|\Delta|. Doud’s algorithm [24] instead bounds the torsion order by point counts modulo primes of good reduction and tests the nn-division points of the analytic parametrization by ℘\wp for rationality; we intend to implement it, with exact verification of the candidates.

  1. Sharper Rank Bounds. The bounds of § 4.2 need a rational point of order 2. Computing the 2-Selmer group gives RE≤dim⁡F2Sel⁡(2)(E/Q)−dim⁡F2E(Q)[2]R_E \le\dim_{\mathbb{F}_2}\operatorname{Sel}^{(2)}(E/\mathbb{Q})-\dim_{\mathbb{F}_2}E(\mathbb{Q})[2] for every curve over Q\mathbb{Q}, with equality exactly when Sha⁡(E/Q)[2]=0\operatorname{Sha}(E/\mathbb{Q})[2]=0 [25, 26].

  1. Elliptic Curves over C\mathbb{C}. We plan commands for the lattice Λ\Lambda, the periods, g2g_2, g3g_3, the modular parameter τ\tau and the uniformization C/Λ→E(C)\mathbb{C}/\Lambda\to E(\mathbb{C}), which is the case relevant to elliptic Feynman integrals and is also needed in item 1.

  1. Further Extensions. A genuine Schoof–Elkies–Atkin point count (ECPSEAPointCount is currently an enumeration), canonical heights through local heights [27], the Tamagawa numbers and real period for a numerical check of the BSD formula, isogenies (Vélu), the Shioda–Tate formula for families, and further cryptographic protocols such as ECDH and ECDSA.

Acknowledgements

During the preparation of this work, we have used the AI assistants Claude (Anthropic) and ChatGPT (OpenAI) to help refine and test the Wolfram Language code of the package and to check test cases. All mathematical content, the package design, and the final code, examples, and text were reviewed by the authors.

Characteristic and Finite Fields

The main text refers to the characteristic of a field and to the fields Fpr\mathbb{F}_{p^r} without defining them, although these notions decide which of the transformations and algorithms of ECPack apply to a given curve. This appendix collects the definitions and explains how Fpr\mathbb{F}_{p^r} is represented inside the package.

Characteristic

The characteristic of a field KK is the smallest n≥1n \ge1 with n⋅1=0n \cdot1=0, or 0 if no such nn exists. It is always 0 or a prime: if n=abn=ab with a,b>1a,b>1, then (a⋅1)(b⋅1)=0(a\cdot1)(b\cdot1)=0 would give zero divisors. Thus char⁡Q=char⁡R=char⁡C=0\operatorname{char}\mathbb{Q}=\operatorname{char}\mathbb{R}=\operatorname{char}\mathbb{C}=0 and char⁡Fpr=p\operatorname{char}\mathbb{F}_{p^r}=p. The short Weierstrass form y2=x3+Ax+By^2=x^3+Ax+B requires char⁡K≠2,3\operatorname{char}K\ne2,3 (completing the square and the cube divides by 2 and 3); in characteristic 2 and 3 one must use the normal forms of ECPNormalFormCharTwoThree and ECPToShortWeierstrassFp.

Prime Fields and Prime Field Extensions

For a prime pp, Fp=Z/pZ\mathbb{F}_p=\mathbb{Z}/p\mathbb{Z} is a field, while Z/nZ\mathbb{Z}/n\mathbb{Z} is not for composite nn (e.g. 2⋅3≡0(mod6)2\cdot3\equiv0\pmod6). Over Fp\mathbb{F}_p all coefficients, coordinates and group-law computations are carried out modulo pp.

For q=prq=p^r with r≥2r\ge2, Fq\mathbb{F}_q is not Z/qZ\mathbb{Z}/q\mathbb{Z}. It is constructed as Fp[x]/(f)\mathbb{F}_p[x]/(f) for any irreducible f∈Fp[x]f\in\mathbb{F}_p[x] of degree rr, and it is unique up to isomorphism; Fq⊆Fqn\mathbb{F}_q\subseteq\mathbb{F}_{q^n} for all n≥1n\ge1, and Fq×\mathbb{F}_q^\times is cyclic. For example, ω2+ω+1\omega^2+\omega+1 has no root in F2\mathbb{F}_2, so

F4=F2[ω]/(ω2+ω+1)={0,1,ω,ω2},ω2=ω+1.(44)\mathbb{F}_4=\mathbb{F}_2[\omega]/(\omega^2+\omega+1)=\{0,1,\omega,\omega^2\},\qquad\omega^2=\omega+1. \tag*{(44)}

ECPack represents Fpr\mathbb{F}_{p^r} as Fp[x]/(f)\mathbb{F}_p[x]/(f) and writes nonzero elements as powers gkg^k of a primitive element gg, so that multiplication is addition of exponents modulo q−1q-1 (see ECPFiniteFieldInfo). Since E(Fq)⊆E(Fqn)E(\mathbb{F}_q)\subseteq E(\mathbb{F}_{q^n}) and both are finite, every curve over Fq\mathbb{F}_q has a finite group of points over each Fqn\mathbb{F}_{q^n}.

Relevant ECPack commands. ECPNormalFormCharTwoThree, ECPubicToWeierstrassCharTwoThree, ECPToShortWeierstrassFp, ECPJInvariant, ECPFiniteFieldInfo, ECPFqAdd, ECPFqMultiply, ECPFqInverse, ECPFqElement, ECPFqVector, ECPGroupFp, ECPAddFp, ECPPointQFp.

The Frobenius Endomorphism

Let E/FqE/\mathbb{F}_q be given by y2=x3+Ax+By^2=x^3+Ax+B with A,B∈FqA,B\in\mathbb{F}_q, q=prq=p^r, and let F‾q\overline{\mathbb{F}}_q be an algebraic closure. An endomorphism of EE is a morphism E→EE\to E fixing O\mathcal{O} (hence a group homomorphism). For example, the multiplication maps [n]:P↦nP[n]:P\mapsto nP are endomorphisms, with ker⁡[n]=E[n]\ker[n]=E[n].

Frobenius on the Field and on the Curve

In characteristic pp the map a↦apa\mapsto a^p is a ring homomorphism, since (a+b)p=ap+bp(a+b)^p=a^p+b^p (the binomial coefficients (pk)\binom{p}{k}, 0<k<p0<k<p, vanish mod pp). Its iterate a↦aqa\mapsto a^q fixes exactly Fq\mathbb{F}_q:

Fq={a∈F‾q:aq=a}.(45)\mathbb{F}_q=\{a\in\overline{\mathbb{F}}_q:a^q=a\}. \tag*{(45)}

The qq-power Frobenius of the curve is

ϕq:E→E,(x,y)↦(xq,yq),ϕq(O)=O.(46)\phi_q:E\to E,\qquad(x,y)\mapsto(x^q,y^q),\qquad\phi_q(\mathcal{O})=\mathcal{O}. \tag*{(46)}

It maps EE to itself: raising y2=x3+Ax+By^2=x^3+Ax+B to the qq-th power and using Aq=AA^q=A, Bq=BB^q=B gives (yq)2=(xq)3+Axq+B(y^q)^2=(x^q)^3+Ax^q+B. The group law is given by rational functions with coefficients in Fq\mathbb{F}_q, which commute with ϕq\phi_q, so ϕq(P+Q)=ϕq(P)+ϕq(Q)\phi_q(P+Q)=\phi_q(P)+\phi_q(Q) and ϕq\phi_q is an endomorphism. By the characterization above,

E(Fqn)={P∈E(F‾q):ϕqn(P)=P}=ker⁡(ϕqn−1).(47)E(\mathbb{F}_{q^n})=\{P\in E(\overline{\mathbb{F}}_q):\phi_q^n(P)=P\}=\ker(\phi_q^n-1). \tag*{(47)}

The Frobenius endomorphism on finite-field points can be used to describe fixed points over extension fields and to relate point counts over Fqn\mathbb{F}_{q^n} to the kernel of ϕqn−1\phi_q^n-1.

Trace of Frobenius and Point Counts

Theorem 8 Let aq=q+1−#E(Fq)a_q=q+1-\#E(\mathbb{F}_q).

(a) ϕq2−aqϕq+q=0\phi_q^2-a_q\phi_q+q=0 in End⁡(E)\operatorname{End}(E).

(b) Writing X2−aqX+q=(X−α)(X−β)X^2-a_qX+q=(X-\alpha)(X-\beta), one has ∣α∣=∣β∣=q|\alpha|=|\beta|=\sqrt{q} and #E(Fqn)=qn+1−αn−βn\#E(\mathbb{F}_{q^n})=q^n+1-\alpha^n-\beta^n for all n≥1n\geq1. In particular ∣aq∣≤2q|a_q|\leq2\sqrt{q} (Hasse).

Sketch. ϕq\phi_q has degree qq and ϕq−1\phi_q-1 is separable, so by (B.3), #E(Fq)=deg⁡(ϕq−1)=(ϕq−1)(ϕ^q−1)=1−(ϕq+ϕ^q)+q\#E(\mathbb{F}_q)=\deg(\phi_q-1)=(\phi_q-1)(\widehat{\phi}_q-1)=1-(\phi_q+\widehat{\phi}_q)+q, with ϕ^q\widehat{\phi}_q the dual isogeny. Hence aq=ϕq+ϕ^qa_q=\phi_q+\widehat{\phi}_q and ϕqϕ^q=q\phi_q\widehat{\phi}_q=q, which gives (a); (b) follows from #E(Fqn)=deg⁡(ϕqn−1)\#E(\mathbb{F}_{q^n})=\deg(\phi_q^n-1) and the Weil bound on α\alpha. See Silverman [11] (Ch. V) or Washington [8] (Ch. 4).

Action on Torsion and the Tate Module

For ℓ≠p\ell\ne p prime, E[ℓn]≅(Z/ℓnZ)2E[\ell^n]\cong(\mathbb{Z}/\ell^n\mathbb{Z})^2, and ϕq\phi_q acts on each E[ℓn]E[\ell^n] compatibly. The Tate module

Tℓ(E)=lim←⁡nE[ℓn]≅Zℓ2,Vℓ(E)=Tℓ(E)⊗ZℓQℓ≅Qℓ2,(48)T_\ell(E)=\varprojlim_n E[\ell^n]\cong\mathbb{Z}_\ell^2,\qquad V_\ell(E)=T_\ell(E)\otimes_{\mathbb{Z}_\ell}\mathbb{Q}_\ell\cong\mathbb{Q}_\ell^2, \tag*{(48)}

organises these actions into a single 2×22\times2 matrix over Qℓ\mathbb{Q}_\ell whose characteristic polynomial is X2−aqX+qX^2-a_qX+q, i.e. tr⁡ϕq=aq\operatorname{tr}\phi_q=a_q, det⁡ϕq=q\det\phi_q=q. Restricting to E[ℓ]E[\ell] gives aq mod ℓa_q\bmod\ell, which is the quantity computed by Schoof’s algorithm in § 5.3; aqa_q is then recovered by the Chinese Remainder Theorem together with Hasse’s bound.

Relevant ECPack commands. ECPGroupFp, ECPAddFp, ECPMultiplyFp, ECPPointOrderFp, ECPSchoofPointCount, ECPSEAPointCount.

User Manual

All public commands of the package ECPack begin with the prefix ECP (variables with $ECP$), so that all of them can be listed with Names["ECPackECP*"]. The package is loaded with Get["ECPack.wl"]. Each entry below provides the call forms, arguments, returned value, remarks, and one example in the style of a Mathematica notebook. Unless stated otherwise, curve may be a long model $\{a_1,a_2,a_3,a_4,a_6\}$, a short pair $\{A,B\}$, an equation, a polynomial in $x,y$, a curve Association such as $ECPCurrentEC`, or Automatic (the session curve). The examples use the curves 37a1: y2+y=x3−xy^2+y=x^3-x (rank 1, conductor 37), y2=x3−36xy^2=x^3-36x (CM, torsion Z/2×Z/2\mathbb{Z}/2\times\mathbb{Z}/2) and y2=x3+73y^2=x^3+73.

Index of Commands

Commands marked {sup}†` can take a long time to compute for some inputs; the reason is given in their entries below.

ECPAdd Add two rational points on a curve.

ECPAddFp Add two points over Fp\mathbb{F}_p or Fpr\mathbb{F}_{p^r} (short form: odd pp; long form: any pp).

ECPAnalyticRank{sup}†` Analytic rank, root number and conductor, assuming BSD.

ECPAreProjectivelyEquivalent Test whether two projective points are proportional.

ECPBachetDuplication Bachet’s duplication formula: x(2P)x(2P) as a rational function of x(P)x(P).

ECPCanonicalHeight{sup}†` Canonical (Néron–Tate) height of a point.

ECPChordAndTangent Third intersection point of the tangent line at PP with the cubic.

ECPComposeTransformations Compose two Weierstrass isomorphisms {u,r,s,t}\{u,r,s,t\}.

ECPConductor{sup}†` Conductor NN of an integral Weierstrass model.

ECPCoulombDimension Scaling dimension 12/(12−ord⁡Δ)12/(12-\operatorname{ord}\Delta) of a Kodaira singularity.

ECPCubicToWeierstrass Reduce a plane cubic with a known rational point to Weierstrass form (characteristic 0 or >3>3).

ECPCubicToWeierstrassCharTwoThree Same, given an inflection point, in characteristic 2 or 3 (also over Fpr\mathbb{F}_{p^r}).

ECPElGamalDecodeFp Decrypt an ElGamal ciphertext over Fp\mathbb{F}_p (prime fields only).

ECPElGamalEncodeFp Encrypt a message by elliptic-curve ElGamal over Fp\mathbb{F}_p (prime fields only).

ECPExtractCoefficients Read {a1,a2,a3,a4,a6}\{a_1,a_2,a_3,a_4,a_6\} off a curve in any form.

ECPFibreAt Kodaira fibre of a family over Q(t)\mathbb{Q}(t) at a point t0t_0.

ECPFibreAtInfinity Kodaira fibre at t=∞t=\infty of a family over P1\mathbb{P}^1.

ECPFibreList All singular fibres of a family over P1\mathbb{P}^1, with the Euler-number check.

ECPFindGenerators{sup}†` Heuristic search for independent generators of the Mordell–Weil group.

ECPFindLocalReduction Local Laska–Kraus reduction step at a prime pp.

ECPFindPointFp Koblitz-embed a message as a curve point over Fp\mathbb{F}_p (prime fields only).

ECPFindPointOrder Order of a point by bounded search (Mazur’s bound by default).

ECPFindPointOrderFp{sup}†Same asECPPointOrderFp`: exact order of a point over Fp\mathbb{F}_p or Fpr\mathbb{F}_{p^r}.

ECPFindTorsionPoints{sup}†` All rational torsion points (Nagell–Lutz).

ECPFiniteFieldInfo Describe the field polynomial and generator used for Fpr\mathbb{F}_{p^r}.

ECPFormattedEquation Display the long Weierstrass equation.

ECPFqAdd Add two elements of Fpr\mathbb{F}_{p^r}.

ECPFqElement Build a field element from its coordinate vector.

ECPFqInverse Multiplicative inverse in Fpr\mathbb{F}_{p^r}.

ECPFqMultiply Multiply two elements of Fpr\mathbb{F}_{p^r}.

ECPFqVector Coordinate vector of a field element.

ECPFromMinimalPoint Inverse of ECPToMinimalPoint.

ECPFromShortCoordinates Map a point on the short model back to the long model.

ECPFromShortCoordinatesFp Finite-field analogue of ECPFromShortCoordinates.

ECPGaugeAlgebra FF-theory gauge algebra of a Kodaira type (split or non-split).

ECPGroupFp{sup}†` The group E(Fq)E(\mathbb{F}_q) of points over Fp\mathbb{F}_p or Fpr\mathbb{F}_{p^r}.

ECPHeightMatrix{sup}†` Pairwise height-pairing matrix (its determinant is the regulator).

ECPHeightPairing{sup}†` Néron–Tate height pairing of two points.

ECPIndependentQ{sup}†` Test independence of points via the height-matrix determinant.

ECPIsMinimal Test true Weierstrass minimality of a long model.

ECPIsMinimalShort Test minimality of a short model (or dispatch to ECPIsMinimal).

ECPJFunction jj-invariant c43/Δc_4^3/\Delta of a family as a rational function.

ECPJInvariant jj-invariant over Q\mathbb{Q}, Fp\mathbb{F}_p or Fpr\mathbb{F}_{p^r}.

ECPKodairaType Kodaira type and Euler number from the orders of c4,c6,Δc_4,c_6,\Delta.

ECPLegendreToWeierstrass Convert Legendre form to short Weierstrass form.

ECPLocalData{sup}†` Tate’s-algorithm data at every bad prime.

ECPMillerFp Miller’s function fn,Pf_{n,P} evaluated at a point QQ over Fp\mathbb{F}_p or Fpr\mathbb{F}_{p^r}.

ECPMinimalModel{sup}†` Global minimal (long) Weierstrass model.

ECPMinimalModelShort Minimal model for a short Weierstrass pair.

ECPMinimalQ Test minimality at one prime or globally.

ECPMultiply Scalar multiplication of a rational point.

ECPMultiplyFp Scalar multiplication over Fp\mathbb{F}_p or Fpr\mathbb{F}_{p^r}.

ECPNaiveHeight Naive logarithmic height of a point.

ECPNormalFormCharTwoThree Normal form of a long model in characteristic 2 or 3 (also over Fpr\mathbb{F}_{p^r}).

ECPOnCurveQ Test whether a point lies on a given curve.

ECPParseAffineCurve Normalise a curve to {polynomial,{x,y}}\{\text{polynomial},\{x,y\}\}. ECPParseHomogeneousCurve Homogenise a cubic with respect to zz. ECPPointOrder Order of a rational point. ECPPointOrderFp{sup}†Order of a point over $\mathbb{F}_p$ or $\mathbb{F}_{p^r}$ via Lagrange’s theorem.ECPPointQMembership test for a point on a curve (coordinates as two arguments).ECPPointQFpMembership test over $\mathbb{F}_p$ or $\mathbb{F}_{p^r}$.ECPPolynomialHomogeneousExact homogeneity test.ECPPolynomialTransformLinear change of variables in a polynomial.ECPPrimeDivisorCountNumber $\nu(n)$ of distinct primes dividing $n$, or dividing $\Delta$ of a curve.ECPQuarticToWeierstrassConvert $y^2 = \text{quartic}$ to short Weierstrass form.ECPRankBound{sup}† Proven upper bound for the rank of a curve with a rational point of order 2. ECPRankUpperBound{sup}†Heuristic (non-rigorous) rank estimate from the discriminant.ECPSchoofPointCount{sup}† Number of points over Fp\mathbb{F}_p by Schoof’s algorithm (large pp). ECPSEAPointCount{sup}†Exact point count by enumeration over $\mathbb{F}_p$ ($p \lesssim 10^6$) or $\mathbb{F}_{p^r}$.ECPSearchPointsBounded rational-point search.ECPSetECSet the global session curve.ECPShortDiscriminantDiscriminant $-16(4A^3 + 27B^2)$ of a short model.ECPShortWeierstrassFormGives short form curve with integer coefficients.ECPTateTate’s algorithm at one prime.ECPTateFormCoefficients with prescribed vanishing orders at $t = 0$ (F-theory Tate form).ECPTatePairingFp{sup}† Reduced Tate pairing tn(P,Q)t_n(P,Q) over Fp\mathbb{F}_p or Fpr\mathbb{F}_{p^r}. ECPToLongCoordinates Map coordinates of a transformed model back to the long model. ECPToMinimalPoint Map a point under a Weierstrass isomorphism {u,r,s,t}\{u,r,s,t\}. ECPTorsionBasisFp{sup}†Basis of the full $n$-torsion subgroup $E[n] \subset E(\mathbb{F}_q)$.ECPTorsionFamilyUniversal curve with a rational $N$-torsion point (Tate–Kubert form), $N = 4,\ldots,7$.ECPTorsionSubgroup{sup}† Torsion subgroup (order, structure, generators, points). ECPToShortCoordinates Map a point on the long model to the short model. ECPToShortCoordinatesFp Finite-field analogue of ECPToShortCoordinates (prime field). ECPToShortWeierstrass Reduce a long model to short Weierstrass form (characteristic 0 or >3>3). ECPToShortWeierstrassFp Reduce a long model to its simplest form over Fp\mathbb{F}_p or Fpr\mathbb{F}_{p^r} (any pp). ECPToWeierstrassForm Read {a1,…,a6}\{a_1,\ldots,a_6\} off a cubic already in Weierstrass shape. ECPTransformWeierstrass Apply the isomorphism {u,r,s,t}\{u,r,s,t\} to the coefficients. ECPWeierstrassDiscriminant Full discriminant Δ\Delta of a long model. ECPWeilPairingFp Weil pairing en(P,Q)e_n(P,Q) over Fp\mathbb{F}_p or Fpr\mathbb{F}_{p^r}. ECPWInvariants The invariants b2,b4,b6,b8,c4,c6b_2,b_4,b_6,b_8,c_4,c_6 and Δ\Delta.

ECPShortWierstrass is kept as a legacy alias of ECPShortWeierstrassForm. The package also defines the variables $ECPVersion (the version string, "1.0"), $ECPCurrentEC (the session curve set by ECPSetEC), $ECPNagellLutzDiscLimit (the largest ∣Δ∣|\Delta| for exact Nagell-Lutz in ECPFindTorsionPoints) and $ECPFqTableLimit (the largest qq for which the arithmetic tables of Fq\mathbb{F}_q are built).

Function Descriptions

ECPAdd

Usage: ECPAdd[P1, P2, curve]

Arguments. P1, P2: points {x,y}\{x,y\} or Infinity in the coordinates of curve; curve: any curve form.

Returns. The point P1+P2P_1 + P_2 in the same coordinates as curve, as {x,y}\{x,y\} or Infinity.

Notes & restrictions. Both points and the curve are validated once at the entry point; the core uses the doubling formula if P1=P2P_1 = P_2 and the chord formula otherwise (a vertical chord gives Infinity).

Example.(0,0) + (1,0) on 37a1
In[4]:=ECPAdd[\{0, 0\}, \{1, 0\}, \{0, 0, 1, -1, 0\}]
Out[4]=\{-1, -1\}

Table 1 (PDF p. 18).

ECPAddFp

Usage: ECPAddFp[P1, P2, a, p] ECPAddFp[P1, P2, curve, p] ECPAddFp[P1, P2, curve, \{p, r\}] Arguments. P1, P2: points or Infinity (integer coordinates need not be reduced mod pp). a: the xx-coefficient of y2=x3+ax+by^2=x^3+ax+b (short overload, odd pp only; bb is not needed, so membership is not tested). curve: any curve form (long overload; it checks that both points lie on the curve; every prime allowed). {p,r}\{p,r\}: extension field, r≥2r\ge2.

Returns. The sum over Fp\mathbb{F}_p with coordinates in [0,p)[0,p), or Infinity. Over Fpr\mathbb{F}_{p^r} coordinates are written 0 or gkg^k.

Notes & restrictions. Points that do not lie on one common curve mod pp raise a message and return $Failed. Over an extension field give the full curve and field elements in the notation of ECPFiniteFieldInfo.

Example. (5,1)+(6,3)(5,1)+(6,3)

In[5]:= ECPAddFp[{5, 1}, {6, 3}, 2, 17]
Out[5]= {10, 6}

ECPAnalyticRank

Usage: ECPAnalyticRank[model] ECPAnalyticRank[model, prec]

Arguments. model: an integral long model {a1,…,a6}\{a_1,\ldots,a_6\} (short pairs, equations and Automatic are also accepted). prec (default 40): working precision.

Returns. An Association with keys "Rank" (order of vanishing of L(E,s)L(E,s) at s=1s=1), "Parity" (the root number ±1\pm1) and "Conductor".

Notes & restrictions. The rank is the true Mordell–Weil rank only assuming the Birch–Swinnerton-Dyer conjecture (proved for analytic rank ≤1\le1). By the parity conjecture the root number alone decides whether the rank is even or odd. Precision below the internal minimum raises a message. The slowest command: its computation may take time (minutes for conductor N≳105N\gtrsim10^5), since it needs of order N\sqrt{N} coefficients ana_n and many high-precision incomplete gamma functions. A lower prec speeds it up.

Example. analytic rank, root number and conductor of 37a1

In[6]:= ECPAnalyticRank[{0, 0, 1, -1, 0}]
Out[6]= <|"Rank" -> 1, "Parity" -> -1, "Conductor" -> 37|>

ECPAreProjectivelyEquivalent

Usage: ECPAreProjectivelyEquivalent[P, Q]

Arguments. P, Q: length-3 lists of numbers or symbols, the projective coordinates [x:y:z][x:y:z].

Returns. True if Q=λPQ=\lambda P for some λ≠0\lambda\ne0, False otherwise.

Notes & restrictions. The zero vector is equivalent to nothing, not even itself. The test does not check that the points lie on any curve.

Example. proportional projective points

In[7]:= ECPAreProjectivelyEquivalent[{1, 2, 3}, {2, 4, 6}]
Out[7]= True

ECPBachetDuplication

Usage: ECPBachetDuplication[x, curve] ECPBachetDuplication[{x, y}, curve] ECPBachetDuplication[Infinity, curve]

Arguments. x: a number or a symbol. {x,y}\{x,y\}: a point of the curve (checked). curve: any curve form.

Returns. For a bare xx: x(2P)=x4−b4x2−2b6x−b84x3+b2x2+2b4x+b6x(2P)=\frac{x^4-b_4x^2-2b_6x-b_8}{4x^3+b_2x^2+2b_4x+b_6} (for y2=x3+Ax+By^2=x^3+Ax+B: x4−2Ax2−8Bx+A24(x3+Ax+B)\frac{x^4-2Ax^2-8Bx+A^2}{4(x^3+Ax+B)}; for y2=x3+cy^2=x^3+c: x4−8cx4(x3+c)\frac{x^4-8cx}{4(x^3+c)}). For a point: the whole point 2P2P.

Notes & restrictions. The result is Infinity when 2P=O2P=\mathcal{O} (for a numeric xx at a 2-torsion point). The whole-point form agrees with ECPMultiply[2, P, curve].

Example. the whole point 2P2P

In[8]:= ECPBachetDuplication[{-3, 9}, {-36, 0}]
Out[8]= {25/4, -35/8}

ECPCanonicalHeight

Usage: ECPCanonicalHeight[P, curve] ECPCanonicalHeight[P, curve, maxIter]

Arguments. P: a rational point on curve, or Infinity. curve: any curve form. maxIter (default 8): number of doublings in the limit h^(P)=12lim⁡nh(2nP)/4n\hat{h}(P)=\frac{1}{2}\lim_{n}h(2^nP)/4^n, where hh is the naive height of ECPNaiveHeight.

Returns. A machine-precision real number. Torsion points and Infinity give exactly 0.

Notes & restrictions. The value is an approximation (only maxIter doublings), so different maxIter may disagree in the last digits; this is why ECPIndependentQ uses a loose default tolerance. Normalisation: the package follows the convention of Silverman’s Arithmetic of Elliptic Curves, in which h^\hat{h} is half of the value tabulated in Silverman–Tate, Cremona and the LMFDB. Its computation may take time for points of large height, since each doubling roughly quadruples the number of digits in the coordinates.

Example. the generator (0,0)(0,0) of 37a1 (half of Cremona’s value 0.0511)

In[9]:= ECPCanonicalHeight[{0, 0}, {0, 0, 1, -1, 0}]
Out[9]= 0.0255553

ECPChordAndTangent

Usage: ECPChordAndTangent[P, curve] ECPChordAndTangent[P, curve, vars]

Arguments. P: projective point {x,y,z}\{x,y,z\} on the cubic. curve: any curve form (homogenised internally). vars: the three variable names (default: inferred).

Returns. A projective point: the third point where the tangent at PP meets the cubic, before any reflection. It is the chord-and-tangent doubling, not 2P2P in the group law.

Notes & restrictions. If PP is a flex the function returns PP itself; at a 2-torsion point the tangent is vertical and the result is the point at infinity. The computation is an exact projective parametrisation and does not depend on the chart.

Example. third intersection of the tangent at (0:0:1)(0:0:1)

In[10]:= ECPChordAndTangent[{0, 0, 1}, y^2 z + y z^2 - x^3 + x z^2, {x, y, z}]
Out[10]= {1, -1, 1}

ECPComposeTransformations

Usage: ECPComposeTransformations[{u1,r1,s1,t1}, {u2,r2,s2,t2}]

Arguments. Two isomorphisms, each a length-4 list with u≠0u\ne0, for x=u2x′+rx=u^2x^\prime+r, y=u3y′+u2sx′+ty=u^3y^\prime+u^2sx^\prime+t.

Returns. One list {u,r,s,t}\{u,r,s,t\} equal to applying the first and then the second transformation.

Notes & restrictions. Composition is not commutative; the order of the arguments is the order of application. u=0u=0 raises a message and returns $Failed.

Example. compose two isomorphisms

In[11]:= ECPComposeTransformations[{2, 1, 3, 4}, {5, 6, 7, 8}]
Out[11]= {10, 25, 17, 140}

ECPConductor

Usage: ECPConductor[model]

Arguments. model: an integral long model {a1,…,a6}\{a_1,\ldots,a_6\}.

Returns. The integer N=∏ppfpN=\prod_p p^{f_p} over the conductor exponents fpf_p found by Tate’s algorithm.

Notes & restrictions. Built on ECPLocalData. A non-integral model raises a message and returns $Failed. Its computation may take time, since it factorises Δ\Delta, which is slow when ∣Δ∣\lvert\Delta\rvert has large prime factors.

Example. conductor of 37a1

In[12]:= ECPConductor[{0, 0, 1, -1, 0}]
Out[12]= 37

ECPCoulombDimension

Usage: ECPCoulombDimension[ordDelta]

Arguments. ordDelta: an integer with 1<ord⁡Δ<121 < \operatorname{ord}\Delta< 12.

Returns. The scaling dimension 12/(12−ord⁡Δ)12/(12-\operatorname{ord}\Delta) of the Coulomb-branch parameter at a Kodaira singularity with that order of vanishing of Δ\Delta (Argyres–Douglas and Minahan–Nemeschansky: II→6/5II \to6/5, III→4/3III \to4/3, IV→3/2IV \to3/2, I0∗→2I_0^* \to2, IV∗→3IV^* \to3, III∗→4III^* \to4, II∗→6II^* \to6).

Notes & restrictions. Meaningful only for the types that are not InI_n or In∗I_n^*, that is, for ord⁡Δ∈{2,3,4,6,8,9,10}\operatorname{ord}\Delta\in\{2,3,4,6,8,9,10\}.

Example. the seven values

In[93]:= ECPCoulombDimension[#] & /@ {2, 3, 4, 6, 8, 9, 10}
Out[93]= {6/5, 4/3, 3/2, 2, 3, 4, 6}

ECPCubicToWeierstrass

Usage: ECPCubicToWeierstrass[P, curve] ECPCubicToWeierstrass[P, curve, opts]

Arguments. P: a rational point {x0,y0,z0}\{x_0,y_0,z_0\} of the cubic. curve: a homogeneous cubic in three variables, or an affine cubic (homogenised with respect to zz). opts: "Form" ("Long", default, or "Short") and the algorithm/equivalence options.

Returns. The long Weierstrass polynomial y2+a1xy+a3y−(x3+a2x2+a4x+a6)y^2+a_1xy+a_3y-(x^3+a_2x^2+a_4x+a_6); with "Form" -> "Short" the equation Y2=X3+AX+BY^2=X^3+AX+B. The option "Equivalence" -> True also prints the transformation used.

Notes & restrictions. PP need not be a flex. For characteristic 2 or 3 use ECPCubicToWeierstrassCharTwoThree. A point that is not on the cubic, or an invalid option, raises a message and returns $Failed.

Example. cubic with the rational point (0:0:1)

In[13]:= ECPCubicToWeierstrass[{0, 0, 1}, y^2 z + y z^2 - x^3 + x z^2]
Out[13]= 7 x^2 - x^3 + y + 4 x y + y^2

ECPCubicToWeierstrassCharTwoThree

Usage: ECPCubicToWeierstrassCharTwoThree[F, P, p] ECPCubicToWeierstrassCharTwoThree[F, P, {p, r}]

Arguments. F: a homogeneous cubic in x,y,zx,y,z. P: a flex of FF (the point [0:1:0][0:1:0] of a Weierstrass cubic always works). p: 2 or 3; {p,r}: work over Fpr\mathbb{F}_{p^r}.

Returns. An Association with "WeierstrassCoefficients", "Transformation" and auxiliary data (over Fpr\mathbb{F}_{p^r} also "Scaling").

Notes & restrictions. A purely linear change of coordinates anchored at the supplied flex; the usual completion of the square or cube would divide by 2 or 3.

Example. cubic over F_3 with the flex (0:1:0)

In[14]:= ECPCubicToWeierstrassCharTwoThree[y^2 z - x^3 - x z^2 - z^3, {0, 1, 0}, 3]
Out[14]= <|"WeierstrassCoefficients" -> {0, 0, 0, 1, 1}, "Transformation" -> {{1,
0, 0}, {0, 1, 0}, {0, 0, 1}}, "AuxiliaryPoints" -> <|"Q" -> {1, 0, 0}, "P" -> {0,
1, 0}, "R" -> {0, 0, 1}|>, "Characteristic" -> 3|>

ECPElGamalDecodeFp

Usage. ECPElGamalDecodeFp[s, {C1,C2}, a, p] ECPElGamalDecodeFp[s, {C1,C2}, curve, p, kappa]

Arguments. s: the private key. {C1,C2}: the ciphertext from ECPElGamalEncodeFp. a or curve: the curve. p: odd prime. kappa (default 100): the Koblitz parameter used at encoding time.

Returns. The plaintext integer mm.

Notes & restrictions. Computes M=C2−sC1M = C_2 - sC_1 and inverts the embedding x=mκ+jx = m\kappa+ j. A wrong kappa silently recovers a wrong integer. A field {p,r}\{p,r\} with r≥2r \ge2 raises a message.

Example. decrypt with the secret key s=57s = 57 (round trip returns 42)

In[15]:= ECPElGamalDecodeFp[57, ECPElGamalEncodeFp[42, {{0, 8530}, {1753, 557}}, 2, 3, 10007, 4923], 2, 10007]
Out[15]= 42

ECPElGamalEncodeFp

Usage. ECPElGamalEncodeFp[m, {P,B}, a, b, p, n] ECPElGamalEncodeFp[m, {P,B}, curve, p, n, kappa]

Arguments. m: non-negative integer. {P,B}: base point and public key B=sPB = sP. a,b or curve: the curve. p: odd prime. n: bound for the ephemeral kk (normally the order of PP). kappa (default 100): Koblitz parameter.

Returns. The ciphertext {C1,C2}\{C_1,C_2\} with C1=kPC_1 = kP, C2=M+kBC_2 = M+kB, where MM is the Koblitz point embedding mm.

Notes & restrictions. Requires κ(m+1)<p\kappa(m+1) < p. The ephemeral key kk is drawn at random from [⌊n/4⌋,n−1][\lfloor n/4\rfloor,n-1], so the ciphertext changes from one call to the next. Toy primes only in this manual.

Example. encrypt m=42m = 42 on y2=x3+2x+3y^2 = x^3 + 2x + 3 over F10007\mathbb{F}_{10007} with P=(0,8530)P = (0,8530) of order 4923 and B=57P=(1753,557)B = 57P = (1753,557); the ciphertext depends on the random kk, so we check it by decrypting

In[16]:= c = ECPElGamalEncodeFp[42, {{0, 8530}, {1753, 557}}, 2, 3, 10007, 4923];
ECPElGamalDecodeFp[57, c, 2, 10007]
Out[16]= 42

ECPExtractCoefficients

Usage. ECPExtractCoefficients[curve]

Arguments. curve: a polynomial, an equation, a coefficient list or an Association; variables xx, yy or XX, YY.

Returns. The five long coefficients.

Notes & restrictions. A singular curve raises a message and returns $Failed; this is the check every other command relies on.

Example. read the coefficients off an equation

In[17]:= ECPExtractCoefficients[y^2 + y == x^3 - x]
Out[17]= {0, 0, 1, -1, 0}

ECPFibreAt

Usage. ECPFibreAt[curve, t, t0]

Arguments. curve: a family over Q(t)\mathbb{Q}(t) in any accepted form (long {a1,…,a6}\{a_1,\ldots,a_6\} with coefficients that are polynomials in tt, short {A,B}\{A,B\}, an equation in x,yx,y, an Association). t: the parameter (a symbol). t0: a number, or Infinity (then ECPFibreAtInfinity is used).

Returns. An Association with the keys "Location", "Degree", "Type" (Kodaira symbol), "Euler", "Orders" ({ord⁡c4,ord⁡c6,ord⁡Δ}\{\operatorname{ord} c_4,\operatorname{ord} c_6,\operatorname{ord} \Delta\}), "Split", "SplitCriterion", "GaugeAlgebra" and "ScalingDimension".

Notes & restrictions. The model must be minimal at t0t_0; otherwise the type is reported as "non-minimal". "Split" is decided over Q\mathbb{Q} for the types In\mathrm{I}_n (n≥1n \ge1) and IV\mathrm{IV} by testing whether "SplitCriterion" (−c6-c_6 at the point for In\mathrm{I}_n, the leading coefficient of −c6/864-c_6/864 for IV\mathrm{IV}) is a rational square; for symbolic models it is Missing["Symbolic"] and "SplitCriterion" is the expression that must be a square. For other types it is Missing["NotApplicable"]. The invariants c4c_4, c6c_6, Δ\Delta must be polynomials in tt; a singular family raises a message.

Example. the E8E_8 Tate form has a fibre of type II∗\mathrm{II}^* at t=0t=0

In[89]:= Lookup[ECPFibreAt[ECPTateForm[{1, 2, 3, 4, 5}, t], t, 0], {"Type",
"Euler", "GaugeAlgebra", "ScalingDimension"}]
Out[89]= {"II*", 10, "e8", 6}

ECPFibreAtInfinity

Usage: ECPFibreAtInfinity[curve, t] ECPFibreAtInfinity[curve, t, n]

Arguments. curve, tt as for ECPFibreAt; nn: a positive integer or Automatic (default).

Returns. The same Association as ECPFibreAt, for the fibre at t=∞t=\infty of a family over P1\mathbb{P}^1 whose coefficients satisfy deg⁡ai≤in\deg a_i \le in (n=1n=1: rational elliptic surface, n=2n=2: K3).

Notes & restrictions. The fibre is classified in s=1/ts=1/t with the weights s4nc4s^{4n}c_4, s6nc6s^{6n}c_6, s12nΔs^{12n}\Delta. With Automatic, nn is the smallest value that makes the model regular at infinity; give nn explicitly to use a larger one. A value of nn that is too small raises a message.

Example. the universal curve with a point of order 6 has an I2\mathrm{I}_2 fibre at infinity

In[90]:= Lookup[ECPFibreAtInfinity[ECPTorsionFamily[6, d]["Coefficients"], d],
{"Type", "Euler"}]
Out[90]= {"I2", 2}

ECPFibreList

Usage: ECPFibreList[curve, t] ECPFibreList[curve, t, n]

Arguments. curve, tt, nn as for ECPFibreAtInfinity.

Returns. An Association with the keys "n", "Fibres" (one record as in ECPFibreAt for every irreducible factor of Δ\Delta over Q\mathbb{Q}, with "Degree" its number of points, followed by the fibre at Infinity), "TotalEuler", "ExpectedEuler" (= 12n12n) and "ConsistentQ".

Notes & restrictions. "ConsistentQ" is True when the Euler numbers add up to 12n12n, a strong check that the model is minimal and the classification is right. For an irreducible factor of degree larger than one the "Location" is that polynomial (its roots all carry the same fibre type) and "Split" is Missing["NeedsExtension"].

Example. the family with a point of order 6 has fibres I6\mathrm{I}_6, I3\mathrm{I}_3, I2\mathrm{I}_2, I1\mathrm{I}_1

In[91]:= Sort[Lookup[#, {"Type", "Location"}] & /@ ECPFibreList[ECPTorsionFamily[6,
d]["Coefficients"], d]["Fibres"]]
Out[91]= {{"I1", -1/9}, {"I2", Infinity}, {"I3", -1}, {"I6", 0}}

In[92]:= Lookup[ECPFibreList[ECPTorsionFamily[6, d]["Coefficients"], d], {"n",
"TotalEuler", "ExpectedEuler", "ConsistentQ"}]
Out[92]= {1, 12, 12, True}

ECPFIndGenerators

Usage: ECPFIndGenerators[{AA, BB}] ECPFIndGenerators[curve, opts]

Arguments. curve: any curve form; the search runs on the integral short model and results are translated back. opts: "SearchBound" (default 50), "Verbose" (default False).

Returns. An Association with "Rank" (the number of independent points found, a lower bound for the rank), "Generators", "Torsion", "RankBound" and diagnostic data. The key "RankBound" is the heuristic estimate of ECPRankUpperBound, not a proven bound; for a proven bound use ECPRankBound (which gives 3 for the example below).

Notes & restrictions. A bounded heuristic, not a 2-descent: generators outside the search range are missed and the rank is not proven. The generators returned generate the free part of the Mordell–Weil group (modulo torsion), not the torsion subgroup. Its computation may take time, since a canonical height is computed for every point found; the cost grows with "SearchBound". In the example below, the generator (−2,−8)=(−3,9)+(6,0)(-2,-8)=(-3,9)+(6,0) differs from the point (−3,9)(-3,9) used elsewhere in this manual by a torsion point, so both have the same canonical height.

Example. independent generators, short form

In[18]:= ECPFindGenerators[{-36, 0}, "SearchBound" -> 30]
Out[18]= <|"Rank" -> 1, "Generators" -> {{-2, -8}}, "Torsion" -> {Infinity, {-6,
0}, {0, 0}, {6, 0}}, "RankBound" -> 2, "Curve" -> {-36, 0}, "HeightMatrix" ->
{{0.444313}}, "Determinant" -> 0.444313, "Time" -> 62.1973|>

ECPFindLocalReduction

Usage: ECPFindLocalReduction[{a1,...,a6}, p]

Arguments. A long model with integer coefficients and a prime pp.

Returns. A list {u,r,s,t}\{u,r,s,t\} that reduces the model at pp by one step; the identity {1,0,0,0}\{1,0,0,0\} if the model is already minimal at pp.

Notes & restrictions. One step at one prime; ECPMinimalModel iterates it over all primes.

Example. Laska-Kraus step at the prime 2

In[19]:= ECPFindLocalReduction[{0, 0, 0, -576, 0}, 2]
Out[19]= {2, 0, 0, 0}

ECPFindPointFp

Usage: ECPFindPointFp[m, a, b, p] ECPFindPointFp[m, curve, p, kappa]

Arguments. mm: non-negative integer message. a,b or curve: the curve over an odd prime field. pp: odd prime. kappa (default 100).

Returns. A point {x,y}\{x,y\} with x=mκ+jx=m\kappa+j for the smallest successful jj.

Notes & restrictions. Requires κ(m+1)<p\kappa(m+1)<p. {p,r}\{p,r\} with r≥2r\ge2 raises a message.

Example. embed the message 3 as a point (Koblitz)

In[20]:= ECPFindPointFp[3, 2, 3, 10007]
Out[20]= {300, 349}

ECPFindPointOrder

Usage: ECPFindPointOrder[point, a, b] ECPFindPointOrder[point, curve, maxOrder]

Arguments. point: {x,y}\{x,y\} or Infinity. a,b or curve. maxOrder (default 12).

Returns. The smallest n≤maxOrdern\le\text{maxOrder} with nP=OnP=O, otherwise Infinity.

Notes & restrictions. Brute force; compare ECPPointOrderFp, which is exact over Fp\mathbb{F}_p.

Example. order of the 2-torsion point (0,0), short coefficients a, b

In[21]:= ECPFindPointOrder[{0, 0}, -36, 0]
Out[21]= 2

ECPFindPointOrderFp

Usage: ECPFindPointOrderFp[point, curve, p] ECPFindPointOrderFp[point, curve, {p, r}]

Arguments. A point or Infinity on the curve mod pp; any curve form (a short pair needs pp odd); a prime pp or {p,r}\{p,r\}.

Returns. The exact order of the point: the smallest divisor of N=#E(Fq)N = \#E(\mathbb{F}_q) that kills it.

Notes & restrictions. Same algorithm as ECPPointOrderFp (the group order comes from ECPSEAPointCount, so about p≤106p \le10^6, or q≤q \le $ECPFqTableLimit$). Returns $Failed with a message for a non-prime, a singular curve or a point off the curve.

Example. order of (5,1)(5,1) on y2=x3+2x+2y^2 = x^3 + 2x + 2 over F17\mathbb{F}_{17}

In[98]:= ECPFindPointOrderFp[{5, 1}, {2, 2}, 17]

Out[98]= 19

ECPFindTorsionPoints

Usage: ECPFindTorsionPoints[curve]

Arguments. curve: any curve form.

Returns. A list of all rational torsion points, Infinity first, in the coordinates of curve.

Notes & restrictions. Nagell–Lutz: a nonzero torsion point has integral coordinates with y=0y = 0 or y2∣Δy^2 \mid\Delta. For non-integral coefficients or ∣Δ∣>|\Delta| > $ECPNagellLutzDiscLimit$ the function falls back to a bounded search and says so; the result is then not guaranteed complete. Its computation may take time when ∣Δ∣|\Delta| is large, since Δ\Delta is factorised and all its divisors are listed.

Example. Nagell-Lutz on y2=x3−36xy^2 = x^3 - 36x

In[22]:= ECPFindTorsionPoints[{-36, 0}]

Out[22]= {Infinity, {-6, 0}, {0, 0}, {6, 0}}

ECPFiniteFieldInfo

Usage: ECPFiniteFieldInfo[{p, r}]

Arguments. {p,r}\{p,r\}: a prime and r≥2r \ge2.

Returns. The field polynomial f(x)f(x) over Fp\mathbb{F}_p (so Fpr≅Fp[x]/(f)\mathbb{F}_{p^r} \cong\mathbb{F}_p[x]/(f)) and the meaning of the generator gg (the class of xx, a primitive element).

Notes & restrictions. Elements are written 00 or gkg^k (g0g^0 prints as 11). On input any Laurent polynomial in gg with integer coefficients is accepted (1+g, 2 g^3+1, g^-1), an integer nn means nn mod pp, and any single symbol may replace gg.

Example. how F8\mathbb{F}_8 is represented

In[23]:= ECPFiniteFieldInfo[{2, 3}]

Out[23]= <|"p" -> 2, "r" -> 3, "q" -> 8, "FieldPolynomial" -> 1 + x + x^3, "Generator" -> "g, the class of x modulo FieldPolynomial; g is a primitive element (it generates F_q*)", "Elements" -> "0 and g^k for k = 0..q-2 (g^0 prints as 1)"|>

ECPFormattedEquation

Usage: ECPFormattedEquation[curve]

Arguments. curve: long {a1,…,a6}\{a_1,\ldots,a_6\}, short {A,B}\{A,B\}, Association, equation, polynomial or Automatic.

Returns. The equation y2+a1xy+a3y=x3+a2x2+a4x+a6y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6 as an Equal expression.

Notes & restrictions. Display only; use ECPExtractCoefficients to go the other way.

Example. display the long Weierstrass equation

In[24]:= ECPFormattedEquation[{0, 0, 1, -1, 0}]

Out[24]= y + y^2 == -x + x^3

ECPFqAdd

Usage: ECPFqAdd[a, b, {p, r}]

Arguments. Field elements in the 0/gk0/g^k notation (or polynomials in gg); r≥2r \ge2.

Returns. The sum, as 00 or gkg^k.

Notes & restrictions. Uses the discrete-log tables, so q=pr≤q = p^r \le $ECPFqTableLimit.

Example. g+g2g + g^2 in F_8

In[25]:= ECPFqAdd[g, g^2, {2, 3}]

Out[25]= g^4

ECPFqElement

Usage: ECPFqElement[{c0, ..., c(r-1)}, {p, r}]

Arguments. The coefficients ci∈Fpc_i \in F_p and the field {p,r}\{p,r\}.

Returns. The element c0+c1g+⋯+cr−1gr−1c_0 + c_1g + \cdots+ c_{r-1}g^{r-1} in 0/gk0/g^k notation.

Notes & restrictions. Inverse of ECPFqVector.

Example. the element with coordinates 1,1,0

In[26]:= ECPFqElement[{1, 1, 0}, {2, 3}]

Out[26]= g^3

ECPFqInverse

Usage: ECPFqInverse[a, {p, r}]

Arguments. A nonzero element aa and the field {p,r}\{p,r\}.

Returns. a−1a^{-1} as gkg^k.

Notes & restrictions. Zero has no inverse and raises a message.

Example. inverse of gg in F_8

In[27]:= ECPFqInverse[g, {2, 3}]

Out[27]= g^6

ECPFqMultiply

Usage: ECPFqMultiply[a, b, {p, r}]

Arguments. Field elements and the field {p,r}\{p,r\}.

Returns. The product, as 00 or gkg^k.

Notes & restrictions. Multiplication is addition of exponents modulo q−1q - 1.

Example. g3 g5g^3\ g^5 in F_8

In[28]:= ECPFqMultiply[g^3, g^5, {2, 3}]

Out[28]= g

ECPFqVector

Usage: ECPFqVector[a, {p, r}]

Arguments. A field element and the field {p,r}\{p,r\}.

Returns. The list {c0,…,cr−1}\{c_0,\ldots,c_{r-1}\} over FpF_p with a=∑cigia = \sum c_i g^i.

Notes & restrictions. Inverse of ECPFqElement.

Example. coordinates of g3g^3 over F_2

In[29]:= ECPFqVector[g^3, {2, 3}]

Out[29]= {1, 1, 0}

ECPFromMinimalPoint

Usage: ECPFromMinimalPoint[{X,Y}, {u,r,s,t}]

Arguments. A point on the transformed model and the isomorphism that produced it (e.g. the "Transformation" of ECPMinimalModel).

Returns. The point {x,y}\{x,y\} on the original model: x=u2X+rx=u^2X+r, y=u3Y+u2sX+ty=u^3Y+u^2sX+t.

Notes & restrictions. Exact inverse of ECPToMinimalPoint; u=0u=0 raises a message.

Example. and back again

In[30]:= ECPFromMinimalPoint[ECPMinimalPoint[{-12, 72}, ECPMinimalModel[{0, 0, 0, -576, 0}]["Transformation"]], ECPMinimalModel[{0, 0, 0, -576, 0}]["Transformation"]]
Out[30]= {-12, 72}

ECPFromShortCoordinates

Usage: ECPFromShortCoordinates[{X,Y}, curve] ECPFromShortCoordinates[Infinity, curve]

Arguments. A point on the short model Y2=X3+AX+BY^2=X^3+AX+B of ToShortWeierstrass[curve]; curve is the original long curve.

Returns. The point on curve: the inverse of X=x+b2/12X=x+b_2/12, Y=y+(a1x+a3)/2Y=y+(a_1x+a_3)/2.

Notes & restrictions. Exact inverse of ECPToShortCoordinates. A point not on the short model raises a message.

Example. the inverse map

In[31]:= ECPFromShortCoordinates[{0, 1/2}, {0, 0, 1, -1, 0}]
Out[31]= {0, 0}

ECPFromShortCoordinatesFp

Usage: ECPFromShortCoordinatesFp[{X,Y}, curve, p]

Arguments. A point on the model returned by ECPToShortWeierstrassFp[curve, p]; the original long curve; a prime pp.

Returns. The corresponding point of the original curve mod pp.

Notes & restrictions. Works in every characteristic, unlike ECPFromShortCoordinates.

Example. and back again

In[32]:= ECPFromShortCoordinatesFp[ECPToShortCoordinatesFp[{0, 0}, {0, 0, 1, -1, 0}, 7], {0, 0, 1, -1, 0}, 7]
Out[32]= {0, 0}

ECPGaugeAlgebra

Usage: ECPGaugeAlgebra[type] ECPGaugeAlgebra[type, split]

Arguments. type: a Kodaira symbol as a string ("I3", "IV*", . . .). split: True or False where it matters (default Automatic).

Returns. The F-theory gauge algebra as a string: InI_n: su⁡(n)\operatorname{su}(n) / sp⁡(⌊n/2⌋)\operatorname{sp}(\lfloor n/2\rfloor); IVIV: su⁡(3)\operatorname{su}(3) / su⁡(2)\operatorname{su}(2); In∗I_n^*: so⁡(2n+8)\operatorname{so}(2n+8) / so⁡(2n+7)\operatorname{so}(2n+7); IV∗IV^*: e6e6 / f4f4; IIIIII and I2I_2: su⁡(2)\operatorname{su}(2); III∗III^*: e7e7; II∗II^*: e8e8.

Notes & restrictions. I0∗I_0^* depends on the monodromy cover (so⁡(8)\operatorname{so}(8), so⁡(7)\operatorname{so}(7) or g2g_2), and IIII, I0I_0, I1I_1 carry no gauge algebra. When split is omitted, an unresolved case is returned as an “either/or” string.

Example. split and non-split IV∗IV^*, and an unresolved I5I_5

In[94]:= {ECPGaugeAlgebra["IV*", True], ECPGaugeAlgebra["IV*", False], ECPGaugeAlgebra["I5"]}
Out[94]= {"e6", "f4", "su(5) or sp(2)"}

ECPGroupFp

Usage: ECPGroupFp[curve, p] ECPGroupFp[curve, {p, r}] ECPGroupFp[a, b, p]

Arguments. curve: short, long, Association, equation or Automatic. p or {p, r}: the field, q=pr≤q = p^r \leq $ECPFqTableLimit. a,b: the short curve y2=x3+ax+by^2 = x^3 + ax + b.

Returns. An Association with "Field", "Curve", "Order", "Invariants" {n1,n2}\{n_1,n_2\} with n1∣n2n_1 \mid n_2 and E(Fq)≅Z/n1×Z/n2E(\mathbb{F}_q) \cong\mathbb{Z}/n_1 \times\mathbb{Z}/n_2, "Structure" (a string), "Generators" (one point if cyclic, two otherwise) and "Points" (all points, Infinity first).

Notes & restrictions. Works in every characteristic. Over Fp\mathbb{F}_p points are integer pairs; over Fpr\mathbb{F}_{p^r} coordinates are 0 or gkg^k. Its computation may take time for large qq, since every point of E(Fq)E(\mathbb{F}_q) is listed.

Example. a non-cyclic group over F_7

In[33]:= ECPGroupFp[{-1, 0}, 7]["Structure"]
Out[33]= "Z/2 x Z/4"

ECPHeightMatrix

Usage: ECPHeightMatrix[points, curve]

Arguments. A list of points on curve; curve: any curve form.

Returns. The symmetric matrix Mij=⟨Pi,Pj⟩M_{ij} = \langle P_i, P_j \rangle.

Notes & restrictions. Torsion points give zero rows; dependent points give a determinant near 0. Its computation may take time, since kk points need about 3k23k^2 canonical heights.

Example. height matrix; its determinant is the regulator

In[34]:= ECPHeightMatrix[{{2, 9}, {3, 10}}, {0, 73}]
Out[34]= {{0.46197, -0.488523}, {-0.488523, 0.996347}}

ECPHeightPairing

Usage: ECPHeightPairing[P1, P2, curve]

Arguments. Two points on curve; curve: any curve form.

Returns. The real number ⟨P1,P2⟩=12(h^(P1+P2)−h^(P1)−h^(P2))\langle P_1, P_2\rangle= \frac{1}{2}\bigl(\hat{h}(P_1 + P_2) - \hat{h}(P_1) - \hat{h}(P_2)\bigr), so that ⟨P,P⟩=h^(P)\langle P, P\rangle= \hat{h}(P) exactly as returned by ECPCanonicalHeight.

Notes & restrictions. Inherits the approximation and the normalisation of ECPCanonicalHeight. Its computation may take time, since it needs three canonical heights.

Example. pairing of (2,9) and (3,10) on y2=x3+73y^2 = x^3 + 73

In[35]:= ECPHeightPairing[{2, 9}, {3, 10}, {0, 73}]
Out[35]= -0.488523

ECPIndependentQ

Usage: ECPIndependentQ[points, curve] ECPIndependentQ[points, curve, tol]

Arguments. A list of points; curve; tol (default 0.01): determinant threshold.

Returns. True if det ECPHeightMatrix >> tol, else False.

Notes & restrictions. Any torsion point, or two multiples of one point, makes the set dependent. A negative tol raises a message. Its computation may take time, since it builds the full height matrix.

Example. (2,9), (3,10) are independent

In[36]:= ECPIndependentQ[{{2, 9}, {3, 10}}, {0, 73}]
Out[36]= True

ECPIsMinimal

Usage: ECPIsMinimal[{a1,...,a6}] ECPIsMinimal[curve]

Arguments. Any curve form (a short pair {A, B} is read as {0, 0, 0, A, B}).

Returns. True iff the long model is a global minimal (Laska–Kraus) model over Z\mathbb{Z}.

Notes & restrictions. The right test for a long model; ECPMinimalQ on a short pair can be fooled at p=2,3p = 2, 3.

Example. 37a1 has squarefree discriminant, so it is minimal

In[37]:= ECPIsMinimal[{0, 0, 1, -1, 0}]

Out[37]= True

ECPIsMinimalShort

Usage: ECPIsMinimalShort[{A,B}] ECPIsMinimalShort[curve]

Arguments. A short pair, or any curve form.

Returns. For a short pair: minimality among short models (via ECPMinimalQ); for long input: the same as ECPIsMinimal.

Notes & restrictions. A short pair can pass this test and still be non-minimal as a Weierstrass model at p=2,3p = 2, 3.

Example. y2=x3−576xy^2 = x^3 - 576x is not minimal (u=2u = 2 removes 242^4, 262^6)

In[38]:= ECPIsMinimalShort[{-576, 0}]

Out[38]= False

ECPJFunction

Usage: ECPJFunction[curve]

Arguments. curve: a family in any accepted form, with coefficients that may contain symbols.

Returns. The jj-invariant c4/Δc_4/\Delta as a simplified rational function of the parameters.

Notes & restrictions. ECPJInvariant is meant for numeric curves; its singularity test cannot decide symbolic discriminants, which is why this command exists. A family with Δ=0\Delta= 0 raises a message.

Example. the jj-function of the Legendre family

In[95]:= Simplify[ECPJFunction[{0, -(1 + t), 0, t, 0}] == 256 (t^2 - t + 1)^3/(t^2 (t - 1)^2)]

Out[95]= True

ECPJInvariant

Usage: ECPJInvariant[curve] ECPJInvariant[curve, p] ECPJInvariant[curve, {p, r}]

Arguments. curve: any curve form (also bare coefficients). pp: optional prime modulus; {p,r}\{p,r\}: Fpr\mathbb{F}_{p^r}.

Returns. j=c4/Δj = c_4/\Delta, reduced mod pp or computed in Fpr\mathbb{F}_{p^r} if a modulus is given.

Notes & restrictions. The short-form overload modulo pp excludes p=2p = 2.

Example. curve = Automatic uses the session curve

In[39]:= ECPJInvariant[Automatic]

Out[39]= 110592/37

ECPKodairaType

Usage: ECPKodairaType[{ordC4, ordC6, ordDelta}]

Arguments. The orders of vanishing of c4c_4, c6c_6 and Δ\Delta at a point: non-negative integers (or Infinity).

Returns. {type, EulerNumber} from Kodaira’s table (Table 1); the Euler number equals ord Δ\Delta.

Notes & restrictions. The table is the characteristic-0 one, so it is valid over Q(t)\mathbb{Q}(t) and C(t)\mathbb{C}(t). The result is {"non-minimal", Indeterminate} when ord c4≥4c_4 \ge4 and ord c6≥6c_6 \ge6, and {"unclassified", Indeterminate} for inconsistent orders.

Example.

In[88]:= {ECPKodairaType[{2, 3, 8}], ECPKodairaType[{4, 6, 12}]}

Out[88]= {{"I2*", 8}, {"non-minimal", Indeterminate}}

ECPLegendreToWeierstrass

Usage: ECPLegendreToWeierstrass[lambda]

Arguments. lambda: a number or symbol, λ≠0,1\lambda\ne0, 1.

Returns. A pair {A, B} such that y2=x3+Ax+By^2 = x^3 + Ax + B is isomorphic to y2=x(x−1)(x−λ)y^2 = x(x - 1)(x - \lambda) (scaling A=−27c4A = -27c_4, B=−54c6B = -54c_6).

Notes & restrictions. Requires characteristic 0 or >3> 3.

Example. Legendre form y2=x(x−1)(x−3)y^2 = x(x-1)(x-3)

In[40]:= ECPLegendreToWeierstrass[3]

Out[40]= {-3024, -34560}

ECPLocalData

Usage: ECPLocalData[model]

Arguments. An integral long model.

Returns. An Association mapping each prime dividing Δ\Delta to the Association that ECPTate[model, p] returns.

Notes & restrictions. Equivalent to calling ECPTate once per prime factor of Δ\Delta. Its computation may take time, since it factorises Δ\Delta, which is slow when ∣Δ∣|\Delta| has large prime factors.

Example. reduction data at every bad prime

In[41]:= ECPLocalData[{0, 0, 0, -36, 0}]

Out[41]= <|2 -> <|"f" -> 6, "type" -> "I2*", "model" -> {0, 6, 0, -24, -64}, "split" -> None|>, 3 -> <|"f" -> 2, "type" -> "I0*", "model" -> {0, 0, 0, -36, 0}, "split" -> None|>|>

ECPMillerFp

Usage: ECPMillerFp[n, P, Q, curve, field]

Arguments. nn: a positive integer. PP, QQ: points on curve over the field, with Q≠OQ \ne\mathcal{O}. curve: short {A, B} (odd pp), long {a1, ..., a6}, an Association or an equation. field: a prime pp or {p, r}; over Fpr\mathbb{F}_{p^r}, r≥2r \ge2, field elements are written 0 or gkg^k (see ECPFiniteFieldInfo).

Returns. The value fn,P(Q)∈Fqf_{n,P}(Q) \in\mathbb{F}_q of Miller’s function, where div⁡fn,P=n(P)−([n]P)−(n−1)(O)\operatorname{div} f_{n,P} = n(P) - ([n]P) - (n - 1)(\mathcal{O}), normalised as in Miller’s algorithm: at every step the line through TT and PP is divided by the vertical line through T+PT + P. An integer for r=1r = 1, 0 or gkg^k for r≥2r \ge2.

Notes & restrictions. Double-and-add loop. Returns $Failed with a message if QQ is a zero or a pole of an intermediate function (for example when QQ lies in the group generated by PP). If P=OP = \mathcal{O} the result is 1. Works in every characteristic, including 2 and 3.

Example. f3,P(Q)f_{3,P}(Q) for P=(0,4)P = (0, 4), Q=(5,1)Q = (5, 1) on y2=x3+2y^2 = x^3 + 2 over F7\mathbb{F}_7

In[78]:= ECPMillerFp[3, {0, 4}, {5, 1}, {0, 2}, 7]

Out[78] = 4

ECPMinimalModel

Usage: ECPMinimalModel[{a1,...,a6}] ECPMinimalModel[curve, opts]

Arguments. Any curve form (short {A, B} is read as {0, 0, 0, A, B}).

Returns. An Association with "MinimalCoefficients" (normalised so a1a_1, a3∈{0,1}a_3 \in\{0,1\}, a2∈{−1,0,1}a_2 \in\{-1,0,1\}), "Equation", "Transformation" ({u,r,s,t}\{u,r,s,t\} from the input to the minimal model), "Discriminant", "OldDiscriminant" and "IsMinimal".

Notes & restrictions. Iterates ECPFindLocalReduction over all primes dividing Δ\Delta; feed "Transformation" to ECPToMinimalPoint to carry points along. Its computation may take time, since it factorises Δ\Delta, which is slow when ∣Δ∣|\Delta| has large prime factors.

Example of a minimal model with the transformation used

Figure 1. Example. minimal model, with the transformation used In[42]:= ECPMinimalModel[{0, 0, 0, -576, 0}] Out[42]= <|"MinimalCoefficients" -> {0, 0, 0, -36, 0}, "Equation" -> y^2 == -36 x + x^3, "Transformation" -> {2, 0, 0, 0}, "Discriminant" -> 2985984, "OldDiscriminant" -> 12230590464, "IsMinimal" -> True|>

ECPMinimalModelShort

Usage: ECPMinimalModelShort[{A,B}] ECPMinimalModelShort[curve]

Arguments. A short pair, or any curve form.

Returns. For short input: the minimal short model (removes p4∣Ap^4 \mid A, p6∣Bp^6 \mid B). For long input: the result of ECPMinimalModel.

Notes & restrictions. The shape of the Association depends on the kind of input; test for "MinimalCoefficients" when writing generic code.

Example of a minimal short model

Figure 2. Example. minimal short model In[43]:= ECPMinimalModelShort[{-576, 0}] Out[43]= <|"MinimalCoefficients" -> {-36, 0}, "Equation" -> y^2 == -36 x + x^3, "TransformationScale" -> 2, "Discriminant" -> 2985984, "OldDiscriminant" -> 12230590464, "IsMinimal" -> True|>

ECPMinimalQ

Usage: ECPMinimalQ[{A,B}, p] ECPMinimalQ[{A,B}] ECPMinimalQ[{a1,...,a6}, p] ECPMinimalQ[{a1,...,a6}]

Arguments. A short pair or a long model, optionally a prime pp.

Returns. True/False. Short overload: not both p4∣Ap^4 \mid A and p6∣Bp^6 \mid B. Long overload: true Laska–Kraus minimality.

Notes & restrictions. Short-model minimality is weaker than Weierstrass minimality at p=2,3p=2,3: for instance y2=x3+16y^2=x^3+16 passes the short test but reduces to y2+y=x3y^2+y=x^3. Use ECPIsMinimal for the true test.

Example of a local test at the prime 2

Figure 3. Example. local test at the prime 2 In[44]:= ECPMinimalQ[{-576, 0}, 2] Out[44]= False

Remark (choosing a minimality test). ECPIsMinimal, ECPIsMinimalShort and ECPMinimalQ are not interchangeable. ECPIsMinimal always applies the Laska–Kraus test and answers whether the model is a global minimal Weierstrass model; it takes no prime and a short pair {A,B}\{A,B\} is read as {0,0,0,A,B}\{0,0,0,A,B\}. ECPMinimalQ can test at a single prime pp (or globally if pp is omitted). On a long model it agrees with ECPIsMinimal; on a short pair it only checks that p4∣Ap^4 \mid A and p6∣Bp^6 \mid B do not both hold, which is minimality among short models. ECPMinimalShort uses this short-model rule for a short pair and equals ECPIsMinimal for long input. The two notions differ at p=2,3p=2,3: y2=x3+16y^2=x^3+16 passes the short test, yet it is not minimal as a Weierstrass model (it reduces to y2+y=x3y^2+y=x^3), so ECPIsMinimal[{0, 16}] is False while ECPMinimalQ[{0, 16}] is True. Use ECPIsMinimal whenever the true answer matters, and ECPMinimalQ[curve, p] for a local check at one prime, preferably on a long model.

ECPMultiply

Usage: ECPMultiply[n, P, curve]

Arguments. nn: an integer (any sign; 0 gives Infinity). PP: a point or Infinity. curve: any curve form.

Returns. The point nPnP by double-and-add, in the coordinates of curve.

Notes & restrictions. Negative nn uses −P=(x,−y−a1x−a3)-P=(x,-y-a_1x-a_3).

Example. 4 (0,0) on 37a1

In[45]:= ECPMultiply[4, {0, 0}, {0, 0, 1, -1, 0}]

Out[45]= {2, -3}

ECPMultiplyFp

Usage: ECPMultiplyFp[n, P, a, p] ECPMultiplyFp[n, P, curve, p] ECPMultiplyFp[n, P, curve, {p, r}]

Arguments. nn: an integer of either sign. PP, aa/curve, pp: as in ECPAddFp.

Returns. nPnP as {x,y}\{x,y\} or Infinity.

Notes & restrictions. Double-and-add on top of ECPAddFp.

Example. 3 (5,1)

In[46]:= ECPMultiplyFp[3, {5, 1}, 2, 17]

Out[46]= {10, 6}

ECPNaiveHeight

Usage: ECPNaiveHeight[{x, y}]

Arguments. A rational point (only xx is used).

Returns. log⁡max⁡(∣num⁡(x)∣,∣den⁡(x)∣,1)\log\max(|\operatorname{num}(x)|,|\operatorname{den}(x)|,1).

Notes & restrictions. The base case of the limit in ECPCanonicalHeight; not itself a group invariant. A symbolic xx raises a message.

Example. log⁡max⁡(∣num⁡(x)∣,∣den⁡(x)∣)\log\max(|\operatorname{num}(x)|,|\operatorname{den}(x)|) for x=−3x=-3

In[47]:= ECPNaiveHeight[{-3, 9}]

Out[47]= 1.09861

ECPNormalFormCharTwoThree

Usage: ECPNormalFormCharTwoThree[curve, p] ECPNormalFormCharTwoThree[curve, {p, r}]

Arguments. curve: any curve form. pp: 2 or 3; {p,r}\{p,r\}: work over Fpr\mathbb{F}_{p^r}.

Returns. An Association with "NormalForm", "Transformation", "Case" (a string naming the ordinary or supersingular normal form used) and "Characteristic". For p=2p=2: y2+xy=x3+a2x2+a6y^2+xy=x^3+a_2x^2+a_6 or y2+a3y=x3+a4x+a6y^2+a_3y=x^3+a_4x+a_6; for p=3p=3: y2=x3+a2x2+a6y^2=x^3+a_2x^2+a_6 or y2=x3+a4x+a6y^2=x^3+a_4x+a_6.

Notes & restrictions. Over Fpr\mathbb{F}_{p^r} the result also has "FieldOrder" and, for p=2p=2 ordinary, a "Gamma" of absolute trace 1 (a2∈{0,γ}a_2\in\{0,\gamma\}).

Example. characteristic 2

In[48]:= ECPNormalFormCharTwoThree[{1, 0, 1, 1, 1}, 2]

Out[48]= <|"NormalForm" -> {1, 1, 0, 0, 1}, "Transformation" -> {1, 1, 0, 0}, "Case" -> "ordinary (a1 != 0): y^2+xy=x^3+a2 x^2+a6", "Characteristic" -> 2|>

ECPOnCurveQ

Usage: ECPOnCurveQ[P, curve] Arguments. P: a point or Infinity; curve: any curve form. Returns. True iff P lies exactly on curve; Infinity always does. Notes & restrictions. Takes a single point list and any curve form, unlike ECPPointQ.

Example. exact membership test, long form

In[49]:= ECPOnCurveQ[{0, 0}, {0, 0, 1, -1, 0}]
Out[49]= True

ECPParseAffineCurve

Usage: ECPParseAffineCurve[input] Arguments. A polynomial, equation, 5-element coefficient list, Association or Automatic. Returns. The list {F, {xv, yv}}. Notes & restrictions. Internal workhorse of the curve-input handling.

Example. normalise a curve to polynomial, variables

In[50]:= ECPParseAffineCurve[y^2 + y - x^3 + x]
Out[50]= {x - x^3 + y + y^2, {x, y}}

ECPParseHomogeneousCurve

Usage: ECPParseHomogeneousCurve[input] Arguments. As ECPParseAffineCurve; a two-variable input is homogenised automatically. Returns. A homogeneous cubic and its three variables. Notes & restrictions. Used by ECPChordAndTangent and ECPCubicToWeierstrass.

Example. homogenise a cubic with respect to z

In[51]:= ECPParseHomogeneousCurve[y^2 + y == x^3 - x]
Out[51]= -x^3 + y^2 z + x z^2 + y z^2

ECPPointOrder

Usage: ECPPointOrder[point, curve] Arguments. A point or Infinity; any curve form. Returns. The exact order, or Infinity for a point of infinite order. Notes & restrictions. Over Q\mathbb{Q} no torsion order exceeds Mazur’s bound 12, so Infinity is unambiguous.

Example. order of (-3,9): infinite, it is not torsion

In[52]:= ECPPointOrder[{-3, 9}, {-36, 0}]
Out[52]= Infinity

ECPPointOrderFp

Usage: ECPPointOrderFp[point, a, b, p] ECPPointOrderFp[point, curve, p] ECPPointOrderFp[point, curve, {p, r}] Arguments. A point or Infinity on the curve mod pp; a,b or curve; a prime pp or {p, r}. Returns. The smallest divisor of N=#E(Fq)N = \#E(\mathbb{F}_q) that kills the point; $Failed with a message for a non-prime, a singular curve or a point off the curve. Notes & restrictions. Exact, not limited by Mazur’s bound. Limited by the point count: about p≤106p \le10^{6}, or $q \le $ECPFqTableLimit. Its computation may take time for large pp, since each call first counts the whole group.

Example. order of (5,1)(5,1)

In[53]:= ECPPointOrderFp[{5, 1}, 2, 2, 17]

Out[53]= 19

ECPPointQ

Usage. ECPPointQ[F, x1, y1]

Arguments. F: a curve Association, equation or polynomial in x,yx,y or X,YX,Y. x1, y1: the two coordinates.

Returns. True iff (x1,y1)(x_1,y_1) satisfies F.

Notes & restrictions. Compare ECPOnCurveQ, which takes a point list and any curve form.

Example. (0,0)(0,0) lies on y2+y=x3−xy^2+y=x^3-x

In[54]:= ECPPointQ[y^2 + y == x^3 - x, 0, 0]

Out[54]= True

ECPPointQFp

Usage. ECPPointQFp[P, a, b, p] ECPPointQFp[P, curve, p] ECPPointQFp[P, curve, {p, r}]

Arguments. A point (not necessarily reduced) or Infinity; a,b or curve; a prime p or {p,r}\{p,r\}.

Returns. True iff P lies on the curve over the field; $Failed with a message if p is not prime.

Notes & restrictions. Over an extension field give coordinates and coefficients in 0/gk0/g^k notation.

Example. (5,1)(5,1) on y2=x3+2x+2y^2=x^3+2x+2 over F17F_{17}

In[55]:= ECPPointQFp[{5, 1}, 2, 2, 17]

Out[55]= True

ECPPolynomialHomogeneous

Usage. ECPPolynomialHomogeneous[F, vars]

Arguments. A polynomial and its variables.

Returns. True iff F is homogeneous in vars.

Notes & restrictions. No numerical tolerance.

Example. homogeneity test

In[56]:= ECPPolynomialHomogeneous[x^2 + x y + y^2, {x, y}]

Out[56]= True

ECPPolynomialTransform

Usage. ECPPolynomialTransform[F, vars, matrix]

Arguments. A polynomial, its variables and a square matrix.

Returns. The expanded polynomial after substituting the linear change of variables.

Notes & restrictions. Used when moving a flex to [0:1:0][0:1:0].

Example. linear change of variables

In[57]:= ECPPolynomialTransform[x^2 + y^2, {x, y}, {{1, 1}, {0, 1}}]

Out[57]= x^2 + 2 x y + 2 y^2

ECPPrimeDivisorCount

Usage: ECPPrimeDivisorCount[n] ECPPrimeDivisorCount[curve]

Arguments. A nonzero integer nn, or an integral model in any curve form.

Returns. ν(n)\nu(n), the number of distinct primes dividing nn (ν(±1)=0\nu(\pm1)=0); for a curve, ν(Δ)\nu(\Delta).

Notes & restrictions. For a minimal model, ν(Δ)\nu(\Delta) is the number of primes of bad reduction. This is the function ν\nu of Theorem 4.

Example. ν(360)=3\nu(360)=3, and ν(Δ)\nu(\Delta) for y2=x3−36xy^2=x^3-36x (Δ=21236\Delta=2^{12}3^6) In[99]:= {ECPPrimeDivisorCount[360], ECPPrimeDivisorCount[{-36, 0}]} Out[99]= {3, 2}

ECPQuarticToWeierstrass

Usage: ECPQuarticToWeierstrass[{a,b,c,d,e}]

Arguments. The coefficients of y2=ax4+bx3+cx2+dx+ey^2=ax^4+bx^3+cx^2+dx+e.

Returns. A pair {A,B}={−27I,−27J}\{A,B\}=\{-27I,-27J\} with I=12ae−3bd+c2I=12ae-3bd+c^2, J=72ace+9bcd−27ad2−27eb2−2c3J=72ace+9bcd-27ad^2-27eb^2-2c^3: the Jacobian of the quartic.

Notes & restrictions. The Jacobian is isomorphic to the quartic itself exactly when the quartic has a rational point.

Example. y^2=x4+x+1\hat{y}^2=x^4+x+1 In[58]:= ECPQuarticToWeierstrass[{1, 0, 0, 1, 1}] Out[58]= {-324, 729}

ECPRankBound

Usage: ECPRankBound[curve] ECPRankBound[curve, "Details"]

Arguments. An integral model in any curve form with a rational point of order 2.

Returns. The smallest of the proven bounds of Theorem 4 and Proposition 1 that apply: ν(a2−4b)+ν(b)−1\nu(a^2-4b)+\nu(b)-1 after moving a rational root of the cubic to x=0x=0, m+2α−1m+2\alpha-1 from the bad reduction, and 2ν(Δ)2\nu(\Delta) when all three 2-torsion points are rational. With "Details", an Association with "Bound", "Candidates" (method →\to bound) and the data used.

Notes & restrictions. A proven upper bound, not the rank. If E(Q)E(\mathbb{Q}) has no point of order 2 no bound of this type exists, and Missing["NoRational2Torsion"] is returned with a message. Its computation may take time, since ECPLocalData factorises Δ\Delta.

Example. y2=x3−36xy^2=x^3-36x (rank 1), and 37a1, which has no rational point of order 2 In[100]:= {ECPRankBound[{-36, 0}], ECPRankBound[{0, 0, 1, -1, 0}]} Out[100]= {3, Missing["NoRational2Torsion"]}

ECPRankUpperBound

Usage: ECPRankUpperBound[{A,B}] ECPRankUpperBound[curve]

Arguments. Any curve form with integral coefficients.

Returns. A small integer: the number of distinct prime factors of Δ\Delta, capped at 4.

Notes & restrictions. A crude sanity signal, not derived from 2-descent: it equals the rank for 37a1 but overestimates it for y2=x3−xy^2=x^3-x. Its computation may take time, since it factorises Δ\Delta, which is slow when ∣Δ∣|\Delta| has large prime factors.

Example. heuristic rank estimate (not a proven bound) In[59]:= ECPRankUpperBound[{-36, 0}] Out[59]= 2

ECPSchoofPointCount

Usage: ECPSchoofPointCount[a, b, p] ECPSchoofPointCount[curve, p]

Arguments. a, b or curve: short {A,B}\{A,B\}, long {a1,…,a6}\{a_1,\ldots,a_6\}, an Association or an equation; a prime pp of any size ({p,1}\{p,1\} is also accepted).

Returns. #E(Fp)\#E(\mathbb{F}_p), including the point at infinity.

Notes & restrictions. Schoof’s algorithm: ap mod ℓa_p \bmod\ell is found from the action of the Frobenius endomorphism on E[ℓ]E[\ell] (division polynomials, arithmetic in Fp[x]/(ψℓ)\mathbb{F}_p[x]/(\psi_\ell)) for ℓ=2,3,5,…\ell=2,3,5,\ldots (ℓ≠p\ell\ne p) until ∏ℓ>4p\prod\ell>4\sqrt{p}, and apa_p is recovered by the Chinese Remainder Theorem and Hasse’s bound. The running time is polynomial in log⁡p\log p, so pp is not limited to 10610^6 as for ECPSEAPointCount. For p=2,3p=2,3 the points are counted directly. The Elkies and Atkin improvements (SEA) are not implemented. Fields Fpr\mathbb{F}_{p^r} with r>1r>1 are not supported; use ECPSEAPointCount. Its computation may take time for very large pp, since the division polynomials ψℓ\psi_\ell have degree about ℓ2/2\ell^2/2.

Example. a prime far beyond the enumeration limit, and a check against enumeration

In[83]:= ECPSchoofPointCount[{2, 3}, 1000000000039]

Out[83]= 1000000769568

In[84]:= ECPSchoofPointCount[{2, 3}, 1000003] == ECPSEAPointCount[{2, 3}, 1000003]

Out[84]= True

ECPSEAPointCount

Usage: ECPSEAPointCount[a, b, p] ECPSEAPointCount[curve, p] ECPSEAPointCount[curve, {p, r}]

Arguments. a, b or curve (the long overload also works for p=2,3p=2,3); a prime p≲106p\lesssim10^6 or {p,r}\{p,r\}.

Returns. #E(Fq)\#E(\mathbb{F}_q) including the point at infinity.

Notes & restrictions. Despite the name this is brute-force enumeration, not the Schoof–Elkies–Atkin algorithm; for larger primes use ECPSchoofPointCount. For a curve with plain integer coefficients over Fpr\mathbb{F}_{p^r} the count comes from #E(Fp)\#E(\mathbb{F}_p) by a Lucas-sequence recurrence and works for any rr. Its computation may take time for large pp, since the running time is proportional to pp.

Example. number of points (direct count, not the SEA algorithm)

In[60]:= ECPSEAPointCount[2, 2, 17]

Out[60]= 19

ECPSearchPoints

Usage: ECPSearchPoints[curve, bound]

Arguments. curve: any curve form; bound (default 50): numerators ∣x∣≤|x|\leq bound, denominators up to 10.

Returns. All points found, in the coordinates of curve.

Notes & restrictions. Not guaranteed complete for positive rank; method distinct from Nagell–Lutz.

Example. rational points of small height

In[61]:= ECPSearchPoints[{-36, 0}, 30]

Out[61]= {{-6, 0}, {-3, 9}, {-3, -9}, {-2, 8}, {-2, -8}, {0, 0}, {6, 0}, {12, 36}, {12, -36}, {18, 72}, {18, -72}, {25/4, 35/8}, {25/4, -35/8}}

ECPSetEC

Usage: ECPSetEC[a1, a2, a3, a4, a6]

Arguments. The five long coefficients as separate arguments.

Returns. The new value of $ECPcurrentEC.

Notes & restrictions. A singular input raises a message and leaves $ECPcurrentEC unchanged.

Example. set the session curve to 37a1: y^2+y=x3−x\hat{y}^{2}+y=x^{3}-x

In[62]:= ECPSetEC[0, 0, 1, -1, 0]
Out[62]= <|"Coefficients" -> {0, 0, 1, -1, 0}, "Equation" -> x - x^3 + y + y^2 ==
0|>

ECPShortDiscriminant

Usage: ECPShortDiscriminant[{A,B}] ECPShortDiscriminant[A, B]

Arguments. A short pair or two numbers.

Returns. −16(4A3+27B2)-16(4A^{3}+27B^{2}).

Notes & restrictions. Short input only; use ECPWeierstrassDiscriminant for other forms.

Example. discriminant of y^2=x3−36x\hat{y}^{2}=x^{3}-36x

In[63]:= ECPShortDiscriminant[{-36, 0}]
Out[63]= 2985984

ECPShortWeierstrassForm

Usage: ECPShortWeierstrassForm[curve]

Arguments. Any curve form.

Returns. Curve in Short form with integer coefficients.

Notes & restrictions. Uses a different transformation than ECPToShortWeierstrass.

Example. correctly spelled synonym

In[64]:= ECPShortWeierstrassForm[y^2 + y == x^3 - x]
Out[64]= -11664 + 1296 x - x^3 + y^2

ECPTate

Usage: ECPTate[model, p]

Arguments. An integral long model {a1,…,a6}\{a_{1},\ldots,a_{6}\} and a prime pp (normally a bad prime).

Returns. An Association with the conductor exponent (key "f"), the Kodaira symbol, the minimal model at pp and the split type.

Notes & restrictions. At a prime of good reduction it only confirms minimality and returns exponent 0. A singular model or a non-prime raises a message.

Example. Tate’s algorithm for 37a1 at p=37p=37

In[66]:= ECPTate[{0, 0, 1, -1, 0}, 37]
Out[66]= <|"f" -> 1, "type" -> "I1", "model" -> {0, 15, 37, 74, -222}, "split" ->
False|>

ECPTateForm

Usage: ECPTateForm[orders, t]

Arguments. orders: a list of five non-negative integers (o1,…,o5)(o_{1},\ldots,o_{5}) for (a1,a2,a3,a4,a6)(a_{1},a_{2},a_{3},a_{4},a_{6}). t: the parameter (a symbol).

Returns. The long Weierstrass coefficients ai=(ci+(i+1)t)toia_i=(c_i+(i+1)t)t^{o_i} with the base constants c=(1,1,3,5,7)c=(1,1,3,5,7), a model whose coefficients vanish to the prescribed orders at t=0t=0.

Notes & restrictions. Example orders: SU(2) (0,0,1,1,2)(0,0,1,1,2), SU(3) (0,1,1,2,3)(0,1,1,2,3), SU(5) (0,1,2,3,5)(0,1,2,3,5), SO(10) (1,1,2,3,5)(1,1,2,3,5), E6 (1,2,2,3,5)(1,2,2,3,5), E7 (1,2,3,3,5)(1,2,3,3,5), E8 (1,2,3,4,5)(1,2,3,4,5). The base constants are one arbitrary generic choice, not the most general Tate form.

Example. Tate form for su(2)

In[96]:= ECPTateForm[{0, 0, 1, 1, 2}, t]
Out[96]= {1 + 2 t, 1 + 3 t, t (3 + 4 t), t (5 + 5 t), t^2 (7 + 6 t)}

ECPTatePairingFp

Usage: ECPTatePairingFp[n, P, Q, curve, field]

Arguments. nn: a positive integer dividing q−1q - 1. PP: a point of E(Fq)E(\mathbb{F}_q) with nP=OnP = O. QQ: any point of E(Fq)E(\mathbb{F}_q). curve: any curve form (every characteristic). field: a prime pp or {p,r}\{p,r\}.

Returns. The reduced Tate pairing tn(P,Q)=fn,P(Q)(q−1)/nt_n(P,Q) = f_{n,P}(Q)^{(q-1)/n}, an nn-th root of unity in Fq\mathbb{F}_q (an integer for r=1r = 1, 00 or gkg^k for r≥2r \ge2).

Notes & restrictions. Computed by Miller’s algorithm. The value depends only on QQ modulo nE(Fq)nE(\mathbb{F}_q); the pairing is bilinear and non-degenerate on E(Fq)[n]×E(Fq)/nE(Fq)E(\mathbb{F}_q)[n] \times E(\mathbb{F}_q)/nE(\mathbb{F}_q). A point PP of smaller exact order mm is reduced to tm(P,Q)t_m(P,Q). If QQ is a zero or a pole of an intermediate Miller function, the value f(Q+S)/f(S)f(Q + S)/f(S) with an auxiliary point SS is used. If n∤q−1n \nmid q - 1 a message asks for an extension field with n∣pr−1n \mid p^r - 1. Unlike the Weil pairing the pairing is not alternating, so tn(P,P)t_n(P,P) need not be 11. Its computation may take time for large qq when the auxiliary point SS is needed, since the points of E(Fq)E(\mathbb{F}_q) are then listed.

Example. Tate pairing of P=(0,4)P = (0, 4) and Q=(5,1)Q = (5, 1) on y2=x3+2y^2 = x^3 + 2 over F7\mathbb{F}_7
In[79]:= ECPTatePairingFp[3, {0, 4}, {5, 1}, {0, 2}, 7]
Out[79]= 2

Table 1 (PDF p. 38).

ECPToLongCoordinates

Usage: ECPToLongCoordinates[pt, curve] ECPToLongCoordinates[pt, curve, {u,r,s,t}]

Arguments. A point (x′,y′)(x', y') of the transformed model ECPTransformWeierstrass[curve, {u,r,s,t}]; the original long curve; an isomorphism {u,r,s,t}\{u,r,s,t\} (default identity {1,0,0,0}\{1,0,0,0\}). The point is checked on the transformed model.

Returns. The point on the original model via x=u2x′+rx = u^2x' + r, y=u3y′+u2sx′+ty = u^3y' + u^2sx' + t.

Notes & restrictions. With the default identity this is a no-op; to undo ECPToShortCoordinates use ECPFromShortCoordinates.

Example. (0,0)(0, 0) on the transformed model {0,3,1,2,0}\{0,3,1,2,0\} (see ECPTransformWeierstrass) is (1,0)(1,0) on 37a1
In[67]:= ECPToLongCoordinates[{0, 0}, {0, 0, 1, -1, 0}, {1, 1, 0, 0}]
Out[67]= {1, 0}

Table 2.

ECPToMinimalPoint

Usage: ECPToMinimalPoint[{x,y}, {u,r,s,t}]

Arguments. A point of the original model and the isomorphism (e.g. "Transformation" of ECPMinimalModel).

Returns. The point on the new model: x′=(x−r)/u2x' = (x - r)/u^2, y′=(y−u2sx′−t)/u3y' = (y - u^2sx' - t)/u^3.

Notes & restrictions. u=0u = 0 raises a message.

Example. map (-12, 72) on y^2=x3−576x\hat{y}^2 = x^3 - 576x to the minimal model
In[68]:= ECPToMinimalPoint[{-12, 72}, ECPMinimalModel[{0, 0, 0, -576, 0}]["Transformation"]]
Out[68]= {-3, 9}

Table 3.

ECPTorsionBasisFp

Usage: ECPTorsionBasisFp[n, curve, field]

Arguments. nn: an integer ≥2\ge2 prime to pp. curve: any curve form. field: a prime pp or {p,r}\{p,r\}.

Returns. A basis {P,Q}\{P,Q\} of the full nn-torsion subgroup E[n]⊂E(Fq)E[n] \subset E(\mathbb{F}_q): PP has exact order nn and ECPWeilPairingFp[n, P, Q, curve, field] is a primitive nn-th root of unity.

Notes & restrictions. Requires E[n]⊂E(Fq)E[n] \subset E(\mathbb{F}_q), that is, E(Fq)⊇Z/n×Z/nE(\mathbb{F}_q) \supseteq\mathbb{Z}/n \times\mathbb{Z}/n (this forces n∣q−1n \mid q - 1); otherwise a message says so, suggests an extension field {p,r}\{p,r\}, and $Failed is returned. All points are enumerated, so q≤q \leq $ECPFqTableLimit. Over Fpr\mathbb{F}_{p^r} the coordinates are written 0 or gkg^k. Its computation may take time for large qq, since every point of E(Fq)E(\mathbb{F}_q) is listed and multiplied by nn.

Example. basis of E[3]E[3] for y2=x3+2y^2=x^3+2 over F7\mathbb{F}_7

In[80]:= ECPTorsionBasisFp[3, {0, 2}, 7]

Out[80]= {{0, 4}, {5, 1}}

ECPTorsionFamily

Usage: ECPTorsionFamily[N, d]

Arguments. NN: 4, 5, 6 or 7. dd: the parameter on X1(N)X_1(N) (a symbol).

Returns. The universal elliptic curve with a rational NN-torsion point, in the Tate–Kubert normal form y2+(1−c)xy−by=x3−bx2y^2+(1-c)xy-by=x^3-bx^2 (the point (0,0)(0,0) has order NN), as an Association with the keys "Coefficients" ({1 - c, -b, -b, 0, 0}), "b", "c" and "Parameter".

Notes & restrictions. Over Q(d)\mathbb{Q}(d) the torsion of the Mordell–Weil group contains Z/NZ\mathbb{Z}/N\mathbb{Z}. Use ECPFibreList on the coefficients to see the fibre content (N=6N=6 gives I6,I3,I2,I1I_6,I_3,I_2,I_1). Other values of NN raise a message.

Example. the family with a point of order 6

In[97]:= ECPTorsionFamily[6, d]["Coefficients"]

Out[97]= {1 - d, -d - d^2, -d - d^2, 0, 0}

ECPTorsionSubgroup

Usage: ECPTorsionSubgroup[curve]

Arguments. Any curve form.

Returns. An Association with "Order", "Structure" (a string), "Generators" and "Points" (including Infinity); points are returned in the coordinates of curve.

Notes & restrictions. Built on ECPFindTorsionPoints, so it inherits the $ECPNagellLutzDiscLimit fallback. Its computation may take time for the same reason as ECPFindTorsionPoints.

Example. torsion subgroup of y2=x3−36xy^2=x^3-36x

In[69]:= ECPTorsionSubgroup[{-36, 0}]

Out[69]= <|"Order" -> 4, "Structure" -> "Z/2Z x Z/2Z", "Generators" -> {{0, 0}, {-6, 0}}, "Points" -> {Infinity, {-6, 0}, {0, 0}, {6, 0}}|>

ECPToShortCoordinates

Usage: ECPToShortCoordinates[{x,y}, curve]

Arguments. A point on curve; any curve form.

Returns. The point {X,Y}\{X,Y\} on the model of ECPToShortWeierstrass[curve]: X=x+b2/12X=x+b_2/12, Y=y+(a1x+a3)/2Y=y+(a_1x+a_3)/2.

Notes & restrictions. A point off the curve, or a singular curve, raises a message and returns $Failed.

Example. move the point (0,0)(0,0) to the short model

In[70]:= ECPToShortCoordinates[{0, 0}, {0, 0, 1, -1, 0}]

Out[70]= {0, 1/2}

ECPToShortCoordinatesFp

Usage: ECPToShortCoordinatesFp[{x,y}, curve, p]

Arguments. A point of the long curve over Fp\mathbb{F}_p; any curve form; a prime pp.

Returns. The image on the model of ECPToShortWeierstrassFp[curve, p]; Infinity maps to Infinity.

Notes & restrictions. A group isomorphism. The point must lie on the curve mod pp.

Example. move (0,0) to the reduced model
In[71]:= ECPToShortCoordinatesFp[{0, 0}, {0, 0, 1, -1, 0}, 7]
Out[71]= {0, 4}

ECPToShortWeierstrass

Usage: ECPToShortWeierstrass[curve]

Arguments. Any curve form.

Returns. The short model Y2=X3+AX+BY^2 = X^3 + AX + B with A=−c4/48A=-c_4/48, B=−c6/864B=-c_6/864, as an equation in X,YX,Y.

Notes & restrictions. For p=2,3p=2,3 use ECPToShortWeierstrassFp or ECPNormalFormCharTwoThree.

Example. the short model Y^2 = X^3 + A X + B, A = -c4/48, B = -c6/864
In[72]:= ECPToShortWeierstrass[{0, 0, 1, -1, 0}]
Out[72]= Y^2 == 1/4 - X + X^3

Remark (ECPToShortWeierstrass versus ECPShortWeierstrassForm). Both reduce a long model to short Weierstrass form for characteristic 0 or >3>3, but they return different things. ECPToShortWeierstrass[curve] gives the equation Y2=X3+AX+BY^2=X^3+AX+B with A=−c4/48A=-c_4/48, B=−c6/864B=-c_6/864, written in the new variables X,YX,Y; the coefficients may be rational, and the substitution X=x+b2/12X=x+b_2/12, Y=y+(a1x+a3)/2Y=y+(a_1x+a_3)/2 is the one used by ECPToShortCoordinates and ECPFromShortCoordinates. For 37a1 it returns Y^2 == 1/4 - X + X^3. ECPShortWeierstrassForm[curve] returns the polynomial y2−(x3+Ax+B)y^2-(x^3+Ax+B) in the curve’s own variables x,yx,y, not an equation. For 37a1 it returns −11664+1296x−x3+y2-11664+1296x-x^3+y^2, that is y2=x3−1296x+11664y^2=x^3-1296x+11664: the same curve rescaled by u=6u=6 so that the coefficients are integers (A=−27c4A=-27c_4, B=−54c6B=-54c_6). The two outputs are therefore isomorphic over Q\mathbb{Q} but are not the same equation, and points computed on one model cannot be used on the other without the corresponding scaling. Use ECPToShortWeierstrass when you need the point transformation or the standard A=−c4/48A=-c_4/48 normalisation, and ECPShortWeierstrassForm when you want an integral short model as a polynomial. Neither applies in characteristic 2 or 3; use ECPToShortWeierstrassFp.

ECPToShortWeierstrassFp

Usage: ECPToShortWeierstrassFp[curve, p] ECPToShortWeierstrassFp[curve, {p, r}]

Arguments. Any curve form (integer or pp-integral rational coefficients); a prime pp or {p,r}\{p,r\}.

Returns. An Association with "Characteristic", "OriginalCoefficients", "ShortCoefficients", "Transformation", "Case", "PureShortQ", "ShortPair", "Equation", "Discriminant" and "jInvariant" (plus "FieldOrder" over Fpr\mathbb{F}_{p^r}).

Notes & restrictions. For p>3p>3 the result is a genuine short model; for p=3p=3 one exists only if j=0j=0 (otherwise y2=x3+a2x2+a6y^2=x^3+a_2x^2+a_6); for p=2p=2 none exists.

Example. long model of 37a1 reduced modulo 7
In[73]:= ECPToShortWeierstrassFp[{0, 0, 1, -1, 0}, 7]
Out[73]= <|"Characteristic" -> 7, "OriginalCoefficients" -> {0, 0, 1, 6, 0},
"ShortCoefficients" -> {0, 0, 6, 2}, "Transformation" -> {1, 0, 0, 3}, "Case" ->
"p > 3: genuine short model y^2 = x^3 + A x + B (A = -c4/48, B = -c6/864 mod p)",
"PureShortQ" -> True, "ShortPair" -> {6, 2}, "Equation" -> y^2 == 2 + 6 x + x^3,
"Discriminant" -> 2, "jInvariant" -> 3|>

ECPToWeierstrassForm

Usage: ECPToWeierstrassForm[F, {xv, yv}]

Arguments. A polynomial or equation and its two variables.

Returns. The equation y2+a1xy+a3y=x3+a2x2+a4x+a6y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6.

Notes & restrictions. No change of variables; stray non-Weierstrass monomials are reported, not discarded.

Example. read the coefficients off a cubic already in Weierstrass shape

In[74]:= ECPToWeierstrassForm[y^2 + y - x^3 + x, {x, y}]

Out[74]= x - x^3 + y + y^2

ECPTransformWeierstrass

Usage: ECPTransformWeierstrass[{a1,...,a6}, {u,r,s,t}]

Arguments. A long model (or any curve form) and an isomorphism with u≠0u \ne0.

Returns. The new coefficients {a1′,…,a6′}\{a'_1,\ldots,a'_6\} for x=u2x′+rx = u^2x' + r, y=u3y′+u2sx′+ty = u^3y' + u^2sx' + t:

ua1′=a1+2s,u2a2′=a2−sa1+3r−s2,u3a3′=a3+ra1+2t,u4a4′=a4−sa3+2ra2−(t+rs)a1+3r2−2st,u6a6′=a6+ra4+r2a2+r3−ta3−t2−rta1.\begin{aligned} u a'_1 &= a_1 + 2s, & u^2a'_2 &= a_2 - sa_1 + 3r - s^2, & u^3a'_3 &= a_3 + ra_1 + 2t, \\ u^4a'_4 &= a_4 - sa_3 + 2ra_2 - (t + rs)a_1 + 3r^2 - 2st, \\ u^6a'_6 &= a_6 + ra_4 + r^2a_2 + r^3 - ta_3 - t^2 - rta_1. \end{aligned}

Notes & restrictions. The building block of ECPMinimalModel, ECPFindLocalReduction, ECPNormalFormCharTwoThree and ECPToShortWeierstrassFp. u=0u = 0 raises a message.

Example. apply the isomorphism 1,1,0,0 to the coefficients

In[75]:= ECPTransformWeierstrass[{0, 0, 1, -1, 0}, {1, 1, 0, 0}]

Out[75]= {0, 3, 1, 2, 0}

ECPWeierstrassDiscriminant

Usage: ECPWeierstrassDiscriminant[curve]

Arguments. Any curve form.

Returns. Δ=−b22b8−8b43−27b62+9b2b4b6\Delta= -b_2^2b_8 - 8b_4^3 - 27b_6^2 + 9b_2b_4b_6.

Notes & restrictions. The curve is nonsingular iff Δ≠0\Delta\ne0.

Example. discriminant of 37a1

In[76]:= ECPWeierstrassDiscriminant[{0, 0, 1, -1, 0}]

Out[76]= 37

ECPWeilPairingFp

Usage: ECPWeilPairingFp[n, P, Q, curve, field]

Arguments. nn: a positive integer prime to pp. PP, QQ: points of E[n]E[n] (nP=nQ=OnP = nQ = O) on curve over the field. curve: any curve form (every characteristic). field: a prime pp or {p,r}\{p,r\}.

Returns. The Weil pairing en(P,Q)=(−1)nfn,P(Q)/fn,Q(P)e_n(P,Q) = (-1)^n f_{n,P}(Q)/f_{n,Q}(P), computed with Miller’s algorithm for both functions: an nn-th root of unity in Fq\mathbb{F}_q, written as an integer for the field pp or {p,1}\{p,1\} and as 00 or gkg^k for r≥2r \ge2.

Notes & restrictions. The pairing is bilinear, alternating (en(P,P)=1e_n(P,P) = 1) and non-degenerate. Points of smaller exact order are reduced to their exact order, and dependent points give 1. Returns $Failed with a message if nn is not prime to pp, or if a point is not on the curve or not in E[n]E[n].

Example. Weil pairing of the basis of E[3]E[3] for y2=x3+2y^2 = x^3 + 2 over F7\mathbb{F}_7 (a primitive cube root of unity: 23≡12^3 \equiv1)

In[81]:= ECPWeilPairingFp[3, {0, 4}, {5, 1}, {0, 2}, 7]

Out[81]= 2

ECPWInvariants

Usage: ECPWInvariants[curve]

Arguments. Any curve form.

Returns. The Association <|"b2" -> ..., "b4" -> ..., "b6" -> ..., "b8" -> ..., "c4" -> ..., "c6" -> ..., "Discriminant" -> ...|>.

Notes & restrictions. There is no jj key; use ECPJInvariant.

Example. b2, b4, b6, b8, c4, c6 and the discriminant

In[77]:= ECPWInvariants[{0, 0, 1, -1, 0}]

Out[77]= <|"b2" -> 0, "b4" -> -2, "b6" -> 1, "b8" -> -1, "c4" -> 48, "c6" -> -216, "Discriminant" -> 37|>

Notebook guide

Here are some pre-computed example notebooks from various standard textbooks on the elliptic curves using ECPack.wl for the better understanding of the subject. User can click on the name of example notebook, which will redirect them to Github page. There the notebook can be downloaded to check the computed examples.

NotebookDescription
Lozano Examples [7]Textbook-style exercises illustrating changes of form, invariants, and basic computations with elliptic curves in the style of Lozano-Robledo.
Husemöller Examples [28]Classical exercises on the group law, torsion points, and explicit arithmetic drawn from the textbook of Husemöller.
Washington Examples [8]Worked examples emphasizing finite-field arithmetic, point counts, and cryptography-related computations from the textbook of Washington.
Silverman AEC Examples [11]Standard arithmetic examples covering minimal models, heights, ranks, and rational points from the textbook of Silverman.
Silverman Tate Examples [9]Examples of point arithmetic and other computations over rational and finite fields from the textbook of Silverman and Tate.
McGee Examples [6]Comparison examples inspired by McGee’s package, highlighting point arithmetic over Fp\mathbb{F}_p, Bachet’s duplication formula and ElGamal encryption.
Miscellaneous ExamplesAdditional test curves and miscellaneous examples. Covers all possible commands of ECPack on some chosen curves.

Table 2 (PDF p. 42). Summary of the seven accompanying Mathematica notebooks.

Declarations

Funding

This research did not receive any specific funding.

Availability of data and material

Not applicable. This manuscript does not report data generation or analysis. The package ECPack.wl and the accompanying Mathematica notebooks are openly available in the ECPack GitHub repository.

Competing interests

The authors have no competing interests to declare that are relevant to the content of this article.

Authors’ contributions

The Mathematica package ECPack.wl was created by D.B., with help from P.T. in the later stages. B.A. provided the essential knowledge of the subject without which this work would not have been completed, and gave D.B. and P.T. the guidance and mentorship they needed. The manuscript was written by B.A., D.B. and P.T.

References

  1. [1]Johannes Blümlein, Carsten Schneider, and Peter Paule, eds. Elliptic Integrals, Elliptic Functions and Modular Forms in Quantum Field Theory. Texts & Monographs in Symbolic Computation. Cham: Springer, 2019. ISBN: 978-3-030-04480-0. DOI: 10.1007/978-3-030-04480-0.
  2. [2]Stefan Weinzierl. Feynman Integrals. A Comprehensive Treatment for Students and Researchers. 1st ed. UNITEXT for Physics. Springer Cham, 2022. ISBN: 978-3-030-99557-7. DOI: 10.1007/978-3-030-99558-4.DOI
  3. [3]Eric D’Hoker and Justin Kaidi. Modular Forms and String Theory. Cambridge University Press, 2024. ISBN: 9781009457521. DOI: 10.1017/9781009457521.
  4. [4]Henry McKean and Victor Moll. Elliptic Curves: Function Theory, Geometry, Arithmetic. Cambridge: Cambridge University Press, 1997. ISBN: 0-521-58228-8. DOI: 10.1017/CBO9781139174879.DOI
  5. [5]Joseph H. Silverman. An Introduction to the Theory of Elliptic Curves. Lecture notes for the Summer School on Computational Number Theory and Applications to Cryptography, University of Wyoming, June 19–July 7, 2006. 2006. URL: https://www.math.brown.edu/~jhs/Presentations/WyomingEllipticCurve.pdf.
  6. [6]John McGee. “A Mathematica Package for Elliptic Curves”. In: Wolfram Technology Conference 2015. Wolfram Research. Champaign, Illinois, USA, 2015. URL: https://library.wolfram.com/infocenter/Conferences/9260/.
  7. [7]Álvaro Lozano-Robledo. Elliptic Curves, Modular Forms, and Their L-functions. Vol. 58. Student Mathematical Library. Providence, Rhode Island: American Mathematical Society, 2011. ISBN: 9780821852422. URL: https://bookstore.ams.org/view?ProductCode=STML/58.
  8. [8]Lawrence C. Washington. Elliptic Curves: Number Theory and Cryptography. 2nd ed. New York: Chapman and Hall/CRC, 2008. ISBN: 9781420071474. DOI: 10.1201/9781420071474.DOI
  9. [9]Joseph H. Silverman and John T. Tate. Rational Points on Elliptic Curves. 2nd ed. Cham: Springer, 2015. ISBN: 9783319858800. DOI: 10.1007/978-3-319-18588-0.DOI
  10. [10]René Schoof. “Elliptic curves over finite fields and the computation of square roots mod p”. In: Mathematics of Computation 44.170 (1985), pp. 483–494. DOI: 10.1090/S0025-5718-1985-077720-6.
  11. [11]Joseph H. Silverman. The Arithmetic of Elliptic Curves. 2nd ed. Vol. 106. Graduate Texts in Mathematics. New York: Springer, 2009. ISBN: 978-0-387-09493-9. DOI: 10.1007/978-0-387-09494-6.DOI
  12. [12]Joseph H. Silverman. Advanced Topics in the Arithmetic of Elliptic Curves. Vol. 151. Graduate Texts in Mathematics. New York: Springer, 1994. ISBN: 978-0-387-94325-1. DOI: 10.1007/978-1-4612-0851-8.DOI
  13. [13]John Tate. “Algorithm for determining the type of a singular fiber in an elliptic pencil”. In: Modular Functions of One Variable IV. Ed. by B. J. Birch and W. Kuyk. Vol. 476. Lecture Notes in Mathematics. Berlin: Springer, 1975, pp. 33–52. DOI: 10.1007/BFb0097582.DOI
  14. [14]Kunihiko Kodaira. “On compact analytic surfaces. II”. In: Annals of Mathematics (2) 77.3 (1963), pp. 563–626. DOI: 10.2307/1970131.DOI
  15. [15]Kunihiko Kodaira. “On compact analytic surfaces. III”. In: Annals of Mathematics (2) 78.1 (1963), pp. 1–40. DOI: 10.2307/1970500.DOI
  16. [16]Neal Koblitz. “Elliptic curve cryptosystems”. In: Mathematics of Computation 48.177 (1987), pp. 203–209. DOI: 10.1090/S0025-5718-1987-0866109-5.DOI
  17. [17]Victor S. Miller. “Use of elliptic curves in cryptography”. In: Advances in Cryptology — CRYPTO ’85 Proceedings. Ed. by Hugh C. Williams. Vol. 218. Lecture Notes in Computer Science. Berlin: Springer, 1986, pp. 417–426. URL: https://doi.org/10.1007/3-540-39799-X_31.
  18. [18]Darrel Hankerson, Alfred Menezes, and Scott Vanstone. Guide to Elliptic Curve Cryptography. Springer Professional Computing. New York: Springer, 2004. ISBN: 978-0-387-95273-4. DOI: 10.1007/b97644.DOI
  19. [19]Taher ElGamal. “A public key cryptosystem and a signature scheme based on discrete logarithms”. In: IEEE Transactions on Information Theory 31.4 (1985), pp. 469–472. DOI: 10.1109/TIT.1985.1057074.DOI
  20. [20]Victor S. Miller. “The Weil pairing, and its efficient calculation”. In: Journal of Cryptology 17.4 (2004), pp. 235–261. DOI: 10.1007/s00145-004-0315-8.DOI
  21. [21]Stephen Lichtenbaum. “Duality theorems for curves over p-adic fields”. In: Inventiones Mathematicae 7 (1969), pp. 120–136. DOI: 10.1007/BF01389795.DOI
  22. [22]Gerhard Frey and Hans-Georg Rück. “A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves”. In: Mathematics of Computation 62.206 (1994), pp. 865–874. DOI: 10.1090/S0025-5718-1994-1218343-6.DOI
  23. [23]Alfred J. Menezes, Tatsuaki Okamoto, and Scott A. Vanstone. “Reducing elliptic curve logarithms to logarithms in a finite field”. In: IEEE Transactions on Information Theory 39.5 (1993), pp. 1639–1646. DOI: 10.1109/18.259647.DOI
  24. [24]Darrin Doud. “A procedure to calculate torsion of elliptic curves over ℚ”. In: Manuscripta Mathematica 95.3 (1998), pp. 463–469. URL: https://eudml.org/doc/156388.DOI
  25. [25]Ernst S. Selmer. “The Diophantine Equation ax^3+by^3+cz^3 = 0”. In: Acta Mathematica 85 (1951), pp. 203–362. DOI: 10.1007/BF02395746.
  26. [26]J. E. Cremona. Algorithms for Modular Elliptic Curves. 2nd ed. Cambridge: Cambridge University Press, 1997, pp. vi+376. ISBN: 0-521-59820-6. URL: https://johncremona.github.io/book/.
  27. [27]Joseph H. Silverman. “Computing heights on elliptic curves”. In: Mathematics of Computation 51.183 (1988), pp. 339–358. DOI: 10.1090/S0025-5718-1988-0942161-4.DOI
  28. [28]Dale Husemöller. Elliptic Curves. 2nd ed. Graduate Texts in Mathematics. New York: Springer, 2004. ISBN: 978-0-387-95490-5. DOI: 10.1007/b979292.DOI

Paper details

vlnc:W_cy9qdd25
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude, ChatGPT

View statement
Looking for related papers…
Contents