submitted to J. Symbolic Computation

An object oriented concept for elliptic curves

MARC CONRAD AND SUSANNE SCHMITT

Universität des Saarlandes, Saarbrücken

(Received 06 July 1999)

We describe objects and methods for an object oriented concept of elliptic curves. In order to achieve this, the representation of elliptic curves in the computer algebra system SIMATH is analyzed. This leads to the objects models (objects which realize Weierstraß equations) and elliptic curves (objects which realize the part of elliptic curves which is invariant under isomorphism). The distinction between methods defined over arbitrary fields and methods defined over concrete fields involves the idea of a polymorphic field. We consider elliptic curves over finite fields and over number fields, but the concept may also be extended for elliptic curves over any other field.

1. Introduction

In the last years computations with elliptic curves have been a main field of research. One reason is the increasing importance of elliptic curves in cryptography (see e.g. (Araki, Satoh, Miura, 1998), (Koblitz, 1998), (Blake, Seroussi, Smart, 1999)). But there has also been progress in number theory itself, as the computation of rank or torsion points of the Mordell-Weil group of an elliptic curve, or the search for integral points (e.g. (Zimmer, 1996), (Cremona, 1997), (Gebel, Pethő, Zimmer, 1997), (Smart, Stephens, 1997)). The aim of this paper is to develop a concept which proposes the way elliptic curves should be implemented in software.

In (Papanikolaou, 1997) the demands on software for computations in number theory in the context of a computer algebra system are formulated (efficiency, reuseability, adaptability, extensibility, portability, simplicity and reliability). We give three examples how these demands affect computations with elliptic curves.

– The demand for reuseability implies the possibility to reuse code written for elliptic curves over one field (e.g. F_{p}) also for other fields (e.g. Q). So we need a clear distinction between algorithms available for arbitrary fields (e.g. the computing of the j-invariant) and algorithms which depend on the basic field (e.g. the counting of points of the Mordell Weil group over F_{p}).

– The idea of adaptability implies an independence of the elliptic curve package to the basic arithmetic and the memory manager.

– Simplicity implies that the design has to follow the mathematical intuition (e.g. elliptic curves may be interpreted as a class of isomorphic equations).

0747–7171/90/000000 + 00 $03.00/0 \begin{matrix}c \\ ◯ \end{matrix} 1999 Academic Press Limited

Only an object oriented approach can follow these demands. The existing software packages for elliptic curves (e.g. Apecs, mwrank, or SIMATH) do not implement such a concept. However, in order to get a better understanding which methods and data structures are appropriate we will investigate in Section 2 the implementation of elliptic curves in SIMATH. Although SIMATH is, as a C library, a priori not object oriented this will lead us to the idea how a strictly object oriented implementation should be set up.

Using the ideas of SIMATH we develop in Section 3 object hierarchies concerning elliptic curves and describe the methods of the involved objects. In this paper there is no preference on a special programming language (as C++, Java, ...) or on a special basic arithmetic (as LiDIA, NTL, ...). However, we mention here the project CAGE which aims to provide a platform for a convenient object oriented implementation of mathematical structures in C++.

We assume in the following that the reader is familiar with the arithmetic of elliptic curves. For details see e.g. (Silverman, 1986).

2. The representation of elliptic curves in SIMATH

For elliptic curves over algebraic number fields it is often convenient to consider at least three different isomorphic equations.

The first one is the equation which was originally given to define the curve, the actual model. The second one is a model in short Weierstraß normal form with integral coefficients. This is required for example for the computation of the torsion group of an elliptic curve over the rational numbers, using the criterion of Nagell, Lutz, and Cassels.

Moreover there exist minimal models at all places. These models are required for many higher algorithms, as e.g. the computation of the reduction type, the L-series of the curve, or the computation of the conductor.

The idea to use different models for different computations is implemented in the computer algebra system SIMATH for elliptic curves over Q and over quadratic number fields. This concept has been successfully used for the search for integral points over Q (Gebel, Pethő, Zimmer, 1997) and for the computation of the Mordell Weil group over quadratic number fields in (Cremona, Serf, 1999) and (Schmitt, 1999).

Note that SIMATH contains also algorithms for elliptic curves over number fields of higher degree and for elliptic curves over finite fields. Their implementation does not follow the concept described in this section.

We fix some notations. Let K be the field of rationals Q or a quadratic number field Q(\sqrt{D}). For any x ∈ K we denote by Fx the factorization of x, i.e. a list of prime numbers when K = Q and prime ideals for K = Q(\sqrt{D}). For x ∈ Q(\sqrt{D}) let N (x) denote the norm of x.

In SIMATH an elliptic curve E|K is represented as a list L = (L_{1}, L_{2}, L_{3}, L_{4}) for K = Q and L = (L_{1}, L_{2}, L_{3}, L_{4}, L_{5}) for K = Q(\sqrt{D}), where the lists L_{1}, L_{2}, L_{3} represent several isomorphic models for the curve, the list L_{4} contains constants which are independent of the model, and L_{5} contains information about the quadratic number field. We describe now the lists L_{1}, …, L_{5} in detail.

The list

L_{1} = (L_{11}, L_{12}, L_{13}, L_{14}, L_{15}, L_{16}, L_{17})

contains as elements seven sublists. These lists are given as follows:

L_{11} = (a_{1}, a_{2}, a_{3}, a_{4}, a_{6}) contains the coefficients of the actual model of E|K, L_{12} = (b_{2}, b_{4}, b_{6}, b_{8}) and L_{13} = (c_{4}, c_{6}) contain the Tate values for the actual model, L_{14} = (Δ, FΔ) for K = Q and L_{14} = (Δ, FΔ, N Δ, FN Δ) for K = Q(\sqrt{D}), where Δ

is the discriminant of the actual model, L_{15} = (P, G), where P is a list of the torsion points of the actual model and G is a list

of generators of the torsion group of the actual model, L_{16} = (T_{m}, T_{s}) (or L_{16} = ((T_{m_{1}}, …, T_{m_{k}}), T_{s})) contains the birational transformation

from the actual model to the minimal model (T_{m}) or to the k minimal models (T_{m_{i}}), and from the actual model to the model in short Weierstraß normal form (T_{s}); the birational transformations are given as a list of the parameters of the transformation,

L_{17} = B contains the basis of the Mordell Weil group of the actual model.

If there exists a global minimal model for E|K we have

L_{2} = (L_{21}, L_{22}, L_{23}, L_{24}, L_{25}, L_{26}, L_{27}),

where

L_{21} = (a_{1}^{m}, a_{2}^{m}, a_{3}^{m}, a_{4}^{m}, a_{6}^{m}), L_{22} = (b_{2}^{m}, b_{4}^{m}, b_{6}^{m}, b_{8}^{m}), L_{23} = (c_{4}^{m}, c_{6}^{m}), L_{24} = (Δ^{m}, FΔ^{m}, δ^{m}) for K = Q and L_{24} = (Δ^{m}, FΔ^{m}, N Δ^{m}, FN Δ^{m}, δ^{m}) for K =

Q(\sqrt{D}), L_{25} = (P^{m}, G^{m}), L_{26} = (T_{a}^{m}, T_{s}^{m}), and L_{27} = B^{m}

are analogous to the lists L_{12}, …, L_{17} with the minimal model instead of the actual model. In addition there is an estimate for the difference between the Weil height and the Néron-Tate height on the minimal model (δ^{m} in list L_{24}). The transformations in L_{26} are from the minimal model to the actual model (T_{a}^{m}) and from the minimal model to the model in short Weierstraß normal form (T_{s}^{m}).

If there exists no global minimal model, then we have

L_{2} = ((P_{1}, L_{2}^{1}), ..., (P_{k}, L_{2}^{k})),

where the P_{i} are the prime ideals of bad reduction and the L_{2}^{i} contain the minimal model for the prime ideal P_{i}. The lists L_{2}^{i} are of an analogous form as the list L_{2} for a global minimal model.

We have

L_{3} = (L_{31}, L_{32}, L_{33}, L_{34}, L_{35}, L_{36}, L_{37}),

where

L_{31} = (a_{4}^{s}, a_{6}^{s}) are the coefficients of a model in short Weierstraß normal form of E|K, L_{32} = (b_{2}^{s}, b_{4}^{s}, b_{6}^{s}, b_{8}^{s}), L_{33} = (c_{4}^{s}, c_{6}^{s}), L_{34} = (Δ^{s}, FΔ^{s}, δ^{s}) for K = Q and L_{34} = (Δ^{s}, FΔ^{s}, N Δ^{s}, FN Δ^{s}, δ^{s}) for K =

Q(\sqrt{D}), L_{35} = (P^{s}, G^{s}), L_{36} = (T_{a}^{s}, T_{m}^{s}) or (T_{a}^{s}, (T_{m_{1}}^{s}, …, T_{m_{k}}^{s})), and L_{37} = B^{s}.

These lists are analogous to the lists L_{22}, …, L_{27} with a model in short Weierstraß normal form instead of the minimal model. Here the transformation T_{a}^{s} is from the model in short Weierstraß normal form to the actual model and the transformation T_{m}^{s} (or the k transformations T_{m_{1}}^{s}, …, T_{m_{k}}^{s}) are from the model in short Weierstraß normal form to the global minimal model (or to the k different minimal models).

The list

L_{4} = (L_{41}, L_{42}, L_{43}, L_{44}, L_{45}, L_{46})

contains data of the elliptic curve, which is invariant of the current model:

L_{41} = (j, Fd_{j}) contains the j-invariant and the factorization of the denominator d_{j} of

j, L_{42} = (N, FN, N_{rt}, L_{c_{p}}) for K = Q and L_{42} = (N, FN, N N, N_{rt}, L_{c_{P}}) for K =

Q(\sqrt{D}), where N is the conductor of the curve, N_{rt} is the list of the places where E has bad reduction together with their reduction type, and L_{c_{P}} is the list of the c_{P} -values which are used in the conjecture of Birch and Swinnerton-Dyer,

L_{43} = (o_{T} , S_{T}) are the order (o_{T}) and the structure (S_{T}) of the torsion group of E|K, L_{44} = (ε, r, L_{r}, R, # ⨿⨿, χ, l_{1}) for K = Q and L_{44} = (ε, r, L_{r}, R, # ⨿⨿) for K = Q(\sqrt{D})

contains the sign of the functional equation (ε), the rank r of the curve, the value of the r-th derivation of the L-series at 1 (L_{r}), the regulator R, the order # ⨿⨿ of the Tate Shafarevich group and in addition for K = Q the characteristic polynomial of the regulator matrix χ, and the least eigenvalue of the regulator matrix l_{1},

L_{45} = (p_{ω_{1}}, ω_{1}, p_{ω_{2}}, ω_{2}, p_{τ} , τ) for K = Q, where ω_{1} is the real period, ω_{2} is the complex period and τ = ±\frac{ω_{1}}{ω_{2}} such that Im(τ) > 0; for x ∈ \{ω_{1}, ω_{2}, τ\} the integer p_{x} denotes the precision with which the value x has been computed; for K = Q(\sqrt{D}) the list L_{45} = (ω) contains only the real period,

L_{46} = (N′, n_{th}, b′_{2}, b′_{4}, b′_{6}, b′_{8}) are constants which are used during the computation of the archimedian local Néron-Tate height; for K = Q(\sqrt{D}) the list L_{46} is omitted.

For elliptic curves over quadratic number fields, there is a fifth list which contains data of the field. We have

L_{5} = (D, d_{4}),

where D is the discriminant of the field K and d_{4} = \{ \begin{matrix}1 & if D ≡ 1 (mod 4), \\ 0 & else. \end{matrix}

An elliptic curve over K in SIMATH is initialized with the values a_{1}, …, a_{6} which are stored in L_{11}. The other lists are empty after the initialization. When some of the data is needed the first time it will be computed and stored at the right place. When the data will be needed again, it will be simply read out.

3. The object oriented representation of elliptic curves

For the object oriented representation of an elliptic curve we follow two principles.

abstract model

model over number fields

model over finite fields model over other fields

...

[figure] [figure] [figure]

polymorphic field

Figure 1. Object hierarchy of models of an elliptic curve.

– An elliptic curve over an arbitrary field is given by an equation of genus 1 which can always be transformed to a Weierstraß normal form. We call such an equation a model of the elliptic curve. As we have seen in Section 2, there are data which depend on the equation (L_{1}, L_{2}, L_{3}), and data which are invariant under birational transformations (L_{4}). In an object oriented environment the idea of having data leads to methods which are bound to certain objects. As objects we introduce here models with methods dependent on a specific equation and elliptic curves with methods which are invariant under birational transformations.

– Many basic algorithms (e.g. the computation of Tate values or discriminant) can be performed for elliptic curves over arbitrary fields. For this we use a polymorphic implementation of a field. For a polymorphic field we may assume that all standard field operations (+, −, ·, …) are available. In an application the polymorphic mechanism will find the appropriate realization of operations depending on the concrete field during the execution. The idea of operating in a polymorphic field leads to the distinction between abstract objects and concrete specifications.

We describe now the objects model and elliptic curve on the abstract level. After that we show how these abstract objects should be extended (by inheritance) to objects over number fields and finite fields. Figures 1 and 2 give an overview of these objects. We focus here only on algebraic number fields and finite fields. However, the abstract model can (and should) also be used to define models over other fields, e.g. function fields.

We assume that an elliptic curve is given by a Weierstraß normal form. For elliptic curves defined by a more general equation (which can always be transformed to a Weierstraß normal form), the described objects have to be extended by appropriate methods. As done in SIMATH, it is recommended to store computed values in order to avoid recomputation.

abstract elliptic curve

elliptic curve over number fields elliptic curve over finite fields elliptic curve over other fields

...

[figure] [figure] [figure]

list of models (polymorphic)

Figure 2. Object hierarchy of elliptic curves.

3.1. the abstract situation

The abstract model ...

... is constructed by the values a_{1}, a_{2}, a_{3}, a_{4}, a_{6}, representing the equation y^{2} + a_{1}xy + a_{3}y = x^{3} + a_{2}x^{2} + a_{4}x + a_{6}; or by giving a birational transformation to another existing model.

... contains a reference to the elliptic curve which it belongs to. So the model will always be in the context of an elliptic curve. This can be achieved in two ways:

If the construction of the model is called by an elliptic curve the reference will be

set to this curve. Otherwise the model will construct an elliptic curve, putting itself in the list of

models as the “actual model”.

... has methods for the computation of the Tate values and the discriminant. Note that the j-invariant is independent of the model and will be computed by a method of the elliptic curve.

... can check if a point with given coordinates lies on the model. ... provides the addition of two points and the multiplication with n ∈ Z of a point on

the model. ... has a reference to a polymorphic field.

All methods described above can be implemented in the abstract model using the reference to the polymorphic field. Of course, this does not exclude the possibility to overload certain methods in a concrete specification.

Without going into details we note that we may derive an object “abstract model in short Weierstraß normal form” from the abstract model in order to increase the performance by overloading some of the methods of the abstract model.

An elliptic curve can be considered as an isomorphism class of models. So, the object “abstract elliptic curve” contains a list of polymorphic references to different, isomorphic models. Here, ‘list’ stands for any appropriate aggregate type as e.g. arrays or mappings.

A typical problem in the context of elliptic curves is “Given the curve E : y^{2} = x^{3} + 3x + 4 over Q. Compute a basis of the Mordell-Weil group”. So, questions about elliptic curves are often related to a specific model. Therefore we stress one of the models as the actual model: the model which has been used to define the curve. We describe now the abstract elliptic curve in detail. The abstract elliptic curve ...

... is constructed by a model which will then be the actual model. ... has facilities to manage the list of models. That means to add a model if it is

isomorphic to the actual model, to return a specified model etc. It must also be possible to clearly distinguish the different models, e.g. by giving them names.

... provides for two models a birational transformation between these models. ... computes the j-invariant. ... analyses the structure of the Mordell-Weil group. We note that this method would

be too difficult (perhaps impossible) to be implemented independent from the field where the curve is defined. It is therefore recommended to declare the method as virtual or to accept ”unknown” as a return value and to overload this method in the specification. Because the question for the structure of the Mordell-Weil group is common to all fields, we think that this method should not be omitted on the abstract level.

... has a convenient and simple mechanism to call the methods of a model, e.g. the computation of the Tate values, the addition of points, etc. This can be implemented by defining as methods of the elliptic curve the methods of the model with an optional additional parameter. This additional parameter is the model where the method is actually performed. If the parameter is not given the actual model is chosen.

3.2. Elliptic curves over number fields

The investigation of SIMATH in Section 2 shows which data and functions are necessary in doing computations with elliptic curves over number fields. We do not make here extra considerations for the field Q because it can be seen as a special case of an algebraic number field. However, depending on the intended application, elliptic curves and/or models over Q may also be implemented as objects on their own, possibly derived from the objects over algebraic number fields.

A model over number fields is derived from the abstract model and in addition ...

... computes the norm of the discriminant, the factorization of the discriminant (in prime

ideals), and the factorization of the norm of the discriminant. ... has methods to compute the torsion points and generators of the torsion group. ... computes generators of the Mordell-Weil group. Although today there are only imple-

mentations available for computing the Mordell-Weil group of elliptic curves over Q or over quadratic number fields, there are theoretical algorithms for computing the Mordell-Weil group for elliptic curves over arbitrary number fields which may be implemented in the future. Because questions about the Mordell-Weil group are canonical appropriate methods should not be omitted, and we suggest therefore a return value “unknown” in cases where there is at present no implementation available.

... finds the integral or the S-integral points for a finite set of places S. ... computes an estimate for the difference of the Weil height and the Néron-Tate height.

An elliptic curve over number fields is derived from the abstract elliptic curve and in addition ...

... computes the factorization of the denominator of j. ... provides a model in short Weierstraß normal form. ... provides a global minimal model (if it exists), a local minimal model to a place P of

bad reduction, and the reduction type of the curve at P. ... computes the conductor, the norm of the conductor, the factorization of the conduc-

tor, and the factorization of the norm of the conductor. ... has methods to compute the sign of the functional equation, the real and the complex

period, the rank r, the value of the r-th derivative of the L-series at s = 1, and the order of the Tate-Shafarevich group.

... computes the regulator of the curve.

3.3. elliptic curves over finite fields

A model over a finite field is derived from the abstract model and in addition ...

... has methods which compute special points of the curve e.g. points of large order or

generators of the Mordell-Weil group. ... solves to a given point and an integer the discrete logarithm problem.

An elliptic curve over a finite field is derived from the abstract elliptic curve and in addition ...

... provides a model in short Weierstraß normal form, if it exists. If there is no such model (which can happen in characteristic 2 or 3) it provides some other well defined normal form.

... computes the Hasse interval. ... has a method to compute the number of points of the Mordell-Weil group. ... computes the Hasse invariant.

Because of the increasing importance in cryptography we recommend to have special objects derived from the abstract model/elliptic curve with additional and overloaded methods for F_{2^{n}} and F_{p} where p is a (large) prime.

References

K. Araki, T. Satoh, S. Miura (1998). Overview of elliptic curve cryptography. Public key cryptography.

PKC ’98, Pacifico Yokohama, Japan, Lect. Notes Comput. Sci. 1431, 29–49. I. Blake, G. Seroussi, N. Smart (1999). Elliptic Curves in Cryptography. Cambridge University Press.

J. E. Cremona (1997). Algorithms for modular elliptic curves. Cambridge University Press. J. E. Cremona, P. Serf (1999). Computing the rank of elliptic curves over real quadratic number fields

of class number 1. Math. Comp. 68, no. 227, 1187–1200. J. Gebel, A. Pethő, H. G. Zimmer (1997). Computing integral points on Mordell’s elliptic curves. Col-

lect. Math. 48, 115–136. N. Koblitz (1998). Algebraic Aspects of Cryptography. Springer. Th. Papanikolaou (1997). Entwurf und Entwicklung einer objektorientierten Bibliothek für algorithmi-

sche Zahlentheorie. Dissertation an der Universität des Saarlandes, Saarbrücken. S. Schmitt (1999). Bestimmung der Mordell-Weil Gruppe elliptischer Kurven über algebraischen

Zahlkörpern. Dissertation an der Universität des Saarlandes, Saarbrücken. J. Silverman (1986). The arithmetic of elliptic curves. Springer. N. P. Smart, N. M. Stephens (1997). Integral points on elliptic curves over number fields, Math. Proc.

Camb. Philos. Soc. 122.1, 9–16. H. G. Zimmer (1996). Basic algorithms for elliptic curves. In Number theory (Eger 1996). 541–595, de

Gruyter.

References to Software

Apecs. Arithmetic of plane elliptic curves, ftp://ftp.math.mcgill.ca/pub/apecs. CAGE. Classes for Algebraic Geometry and Elliptic Curves, http://cage.math.uni-sb.de. LiDIA. A C++ library for computational number theory,

http://www.informatik.tu-darmstadt.de/TI/LiDIA. mwrank. A package to compute ranks of elliptic curves over the rationals,

http://www.maths.nott.ac.uk/personal/jec/ftp/progs. NTL. A Library for doing Number Theory , http://www.shoup.net/NTL. SIMATH. A computer algebra system for algorithmic number theory, http://simath.math.uni-sb.de.