This chapter describes some of the specialised facilities for elliptic and hyperelliptic curves defined over finite fields. Details concerning their construction, arithmetic, and basic properties may be found in Chapters Elliptic Curves and Hyperelliptic Curves.
A problem of considerable importance is the calculation of the number of points on a curve over a finite field. For elliptic and hyperelliptic curves, Magma contains a range of algorithms adapted for different sizes of field and characteristic.
Magma contains an efficient implementation of the Schoof–Elkies–Atkin (SEA) algorithm, with R. Lercier's extension to base fields of characteristic 2. This is used for the case where the characteristic is not small. For small characteristic, canonical lift algorithms are used, while for moderate characteristic a deformation algorithm is used. The canonical lift methods use a range of techniques to lift a modular parameter of the curve to an unramified p-adic ring.
If a suitable Gaussian normal basis exists then the method of R. Lercier and D. Lubicz is used with some adaptations by M. Harrison (Magma) to increase the speed for fields of moderate size. Otherwise, the MSST algorithm as described by P. Gaudry is used for fields up to a certain size, and a recursive version due to R. Harley is used for larger fields. When X0(p) is hyperelliptic, but excluding p = 37, Harrison's method involves lifting a pair of modular parameters, specifically, the coordinates on a Weierstrass model for X0(p).
As a consequence of point counting, the Euler factor and zeta function can be computed for elliptic curves. The points and rational points can also be enumerated.
For Jacobians of curves of genus 2, all the techniques described by P. Gaudry and P. Harley are available in Magma. The best algorithms are those based on p-adic liftings when the characteristic is not too large. In odd characteristic Kedlaya's algorithm is used, while in characteristic 2 Mestre's canonical lift method as adapted by Lercier and Lubicz is used. An implementation of Vercauteren's characteristic 2 version of Kedlaya's algorithm is also available.
The deformation methods for both elliptic and hyperelliptic curves are due to A. Lauder and were implemented by H. Hubrechts. The p-adic methods also provide the Euler factor and zeta function, in addition to the number of points.
The set of rational points of the Jacobian can be constructed. Also the structure of the abelian group of rational points of the Jacobian can be obtained.
Pairings on elliptic curves over finite fields have many uses, ranging from checking independence of torsion points to more practical applications in cryptography. Both destructive applications (such as the MOV attack) and constructive applications (such as pairing-based cryptography) are worth mentioning.
Magma contains an implementation of the most popular pairings on elliptic curves over finite fields, including the Weil pairing, the Tate pairing, and various versions of the Eta and Ate pairings. These were implemented by F. Vercauteren. The Weil pairing provides the basis of an efficient algorithm for determining the structure of the abelian group of rational points of the elliptic curve.
In the case of hyperelliptic Jacobians the Weil pairing of two m-torsion points on a 2-dimensional Jacobian can be computed.
Several algorithms are provided to solve the discrete log problem (DLP) which work by reducing the DLP on a curve to a DLP in a finite field). An implementation of Weil descent in characteristic 2 was undertaken by F. Hess (Magma) for use in the GHS attack on the DLP for elliptic curves.
In the other direction, a routine is provided to generate a cryptographically secure curve together with a certificate of its security.