Chapter status: 👷 in progress 👷

TODO:

Elliptic Curves

Contents

• Generalities
• Affine versus Projective Coordinates
  • Projective Plan
  • Elliptic Curves in Projective Coordinates

Generalities

Let $\mathbb{F}$ be a field of characteristic $p>3.$¹ Let $a,b\in \mathbb{F}$ be two field elements such that $$4a^3+27b^2\ne 0.$$ An elliptic curve in short Weierstrass form over $\mathbb{F},$ denoted $E(\mathbb{F}),$ is the set of all pairs $(x,y)\in {\mathbb{F}}^2$ that satisfy the equation $$y^2=x^3+ax+b$$ together with a distinguished element denoted $\mathcal{O}$ called the point at infinity: $$E(\mathbb{F})=\{(x,y)\in {\mathbb{F}}^2\mid y^2=x^3+ax+b\}\cup \{\mathcal{O}\}.$$ This is the so-called affine representation of points of the elliptic curve. There is another family of representations called projective (more attractive from an algorithmic point of view) that we will discuss shortly.

Hasse's bound establishes that the number of points of $E(\mathbb{F}),$ called the order of $E(\mathbb{F}),$ is $$|E(\mathbb{F})|=|\mathbb{F}|+1-t$$ where $t$ is an integer (called the Frobenius trace or simply trace of the curve) satisfying $$|t|\le 2\sqrt{|\mathbb{F}|}.$$

It is possible to equip $E(\mathbb{F})$ with a commutative group law for which the point at infinity $\mathcal{O}$ is the identity element with the so-called chord-and-tangent rule. This group operation is denoted additively and called addition law. The inverse of a point $(x,y)\in E(\mathbb{F})\setminus \{\mathcal{O}\}$ is the point $(x,-y).$

From the addition law we can define scalar multiplication: for $m\in \mathbb{Z}$ and $P\in E(\mathbb{F}),$ the scalar multiplication of $P$ by $m,$ denoted $[m]P$ or $mP$ if there is no ambiguity, is given by $$[m]P:=\{\begin{array}{ll}\mathcal{O}& \text{if }m=0\\ \underset{m\text{ times}}{\underbrace{P+\cdots +P}}& \text{if }m>0\\ -([-m]P)& \text{if }m<0.\end{array}$$

The group structure of $E(\mathbb{F})$ is either cyclic or "almost" cyclic. Namely, a general theorem establishes that $E(\mathbb{F})$ has at most two invariant factors (see Theorem 5.6 for the definition of an invariant factor). In other words, $E(\mathbb{F})$ is isomorphic to either the cyclic group ${\mathbb{Z}}_n$ or a direct product of cyclic groups ${\mathbb{Z}}_{n_1}\times {\mathbb{Z}}_{n_2}$ with $n_1\mid n_2.$

Affine versus Projective Coordinates

Earlier we saw how to defined an elliptic curve using affine coordinates. This is not how elliptic curves are usually defined by mathematicians, who usually prefer to use projective geometry.

Projective Plan

Let $\mathbb{F}$ be a finite field of order $q$ and let ${\mathbb{F}}^{\ast }:=\mathbb{F}\setminus \{0\}.$ The projective plan over $\mathbb{F},$ denoted $P^2(\mathbb{F}),$ is the set of equivalence classes of ${\mathbb{F}}^3\setminus \{(0,0,0)\}$ where two tuples $(x,y,z)$ and $(x^{\prime },y^{\prime },z^{\prime })$ are equivalent, denoted $(x,y,z)\sim (x^{\prime },y^{\prime },z^{\prime }),$ if there is a scalar $k\in {\mathbb{F}}^{\ast }$ such that $$(x^{\prime },y^{\prime },z^{\prime })=(kx,ky,kz).$$ Such an equivalence class is called a projective point. A projective point contains $q-1$ tuples $(x,y,z)\in {\mathbb{F}}^3.$ The convention is to denote projective points with capital letters and colon separators, i.e., $(X:Y:Z)$ (or sometimes $[X:Y:Z])$ will denote the equivalence class $$\{(kX,kY,kZ)\mid k\in {\mathbb{F}}^{\ast }\}.$$

Equivalently, projective points can be seen as 1-dimensional subspaces ("lines") of the 3-dimensional vector space $V={\mathbb{F}}^3$ over $\mathbb{F}.$ How many projective points are there? There are $q^3-1$ non-zero vectors in ${\mathbb{F}}^3,$ but each of the $q-1$ non-zero vectors in a subspace generates this subspace, hence the total number of 1-dimensional subspaces is $$\frac{q^3-1}{q-1}=q^2+q+1.$$

Another way to count the number of projective points is as follows:

• there are $q^2$ projective points of the form $(X:Y:1),$ $X,Y\in \mathbb{F};$
• there are $q$ projective points of the form $(1:Y:0),$ $Y\in \mathbb{F};$
• there is one projective point of the form $(0:1:0).$

It is customary to identify the ordinary "affine" plane ${\mathbb{F}}^2=\{(x,y)\mid x,y\in \mathbb{F}\}$ with the first type of projective points, meaning there is an injective map from ${\mathbb{F}}^2$ to $P^2(\mathbb{F})$ given by $(x,y)\mapsto (x:y:1).$ The inverse of this map is $(X:Y:Z)\mapsto (X/Z,Y/Z).$

The $q+1$ points of the second and third types (sharing the property that $Z=0)$ are called "points at infinity" and form the so-called "line at infinity".

It is possible to define projective lines in a similar way to projective points: projective lines are 2-dimensional subspaces of ${\mathbb{F}}^3$ (with vector $(0,0,0)$ removed). There are also $q^2+q+1$ projective lines in $P^2(\mathbb{F}),$ which is quite natural since any 1-dimensional subspace of ${\mathbb{F}}^3$ defines a unique 2-dimensional subspace via its orthogonal complement. A projective point "lies on" a projective line if it is included (in the set-theoretical sense) in the projective line. From this definition, it follows that (i) given any two projective points, there is exactly one projective line containing both of them, and (ii) given any two projective lines, there is exactly one projective point lying on both of them (meaning there are no parallel lines). Properties (i) and (ii) are in fact the axiomatic definition of a projective plan. Each projective line contains $q^2-1$ vectors $(x,y,z)\in {\mathbb{F}}^3\setminus \{(0,0,0)\},$ and is the disjoint union of $q+1$ projective points. In particular, the $q+1$ projective points of the second and third type are indeed on the same projective line corresponding to the 2-dimensional subspace orthogonal to vector $(0,0,1).$

Elliptic Curves in Projective Coordinates

To obtain the equation defining an elliptic curve in projective coordinates, we substitute $X/Z$ to $x$ and $Y/Z$ to $y$ in the affine short Weierstrass equation $$y^2=x^3+ax+b\text{\hspace{1em}(11.1)}$$ and multiply by $Z^3$ to clear the denominators. This way, we obtain the projective short Weierstrass equation: $$Y^{2}Z=X^3+aX{Z}^2+b{Z}^3.\text{\hspace{1em}(11.2)}$$

It is easy to see that a projective point $(X:Y:Z)$ with $Z\ne 0$ satisfies (11.2) if and only if the corresponding affine point $(x,y)$ with $x=X/Z$ and $y=Y/Z$ satisfies (11.1). Moreover, a projective point $(X:Y:Z)$ on the line at infinity ($Z=0)$ satisfies (11.2) if and only $X=0,$ meaning the only of the $q+1$ projective points at infinity satisfying (11.2) is $(0:1:0).$ This is the "curve point at infinity", the identity element of the group law, that we denoted $\mathcal{O}$ when we defined the elliptic curve in affine coordinates.

Hence, one of the main advantages of projective coordinates over affine ones is that it unifies ordinary points and the point at infinity $\mathcal{O},$ which now has a projective representation as any other point, namely $(0:1:0).$

Another advantage is that computing the group law is more efficient because it does not require to perform modular division (which is only required to perform projective-to-affine conversion). A ballpark estimation is that a modular inversion is 20 to 100 times more costly than a modular multiplication depending on the platform and the implementation.

The projective coordinates obtained with the substitution $x\leftarrow X/Z,$ $y\leftarrow Y/Z$ is just one possibility among others, called homogeneous projective coordinates because the resulting projective equation (11.2) for the curve is homogeneous, meaning all terms have the same total degree, 3 here. An very common alternative are Jacobian coordinates defined by the substitution $$x\leftarrow X/Z^2,y\leftarrow Y/Z^3.$$ The resulting projective equation is $$Y^2=X^3+aX{Z}^4+b{Z}^6.$$ Projective points in Jacobian coordinates are defined by the equivalence relation $$(x,y,z)\sim (x^{\prime },y{,}^{\prime },z^{\prime })\text{if}\exists k\in {\mathbb{F}}^{\ast },(x^{\prime },y^{\prime },z^{\prime })=(k^{2}x,k^{3}y,kz).$$ The point at infinity ($Z=0)$ is the equivalence class $(1:1:0)=\{(k^2,k^3,0):k\in {\mathbb{F}}^{\ast }\}.$

See http://www.hyperelliptic.org/EFD/ for a list of various other possible coordinates systems.

---

1: It is possible to define elliptic curves over fields of characteristic 2 or 3 but equations are more complicated.