Elliptic Curves

Elliptic curves are curves defined by a certain type of cubic equation in two variables. The set of rational solutions to this equation has an extremely interesting structure, including a group law. The theory of elliptic curves was essential in Andrew Wiles' proof of Fermat's last theorem. Computational problems involving the group law are also used in many cryptographic applications, and in algorithms for factoring large integers.

An elliptic curve is a plane curve defined by the equation \( y^2=f(x) \), where \( f(x) \) is a cubic polynomial with no repeated roots. \(_\square\)

Notes:

(1) Elliptic curves are not ellipses. The name comes from certain integrals involved in computing the arc length of an ellipse, which involve square roots of cubic and quartic polynomials in \( x \).

(2) The equation above is said to be in Weierstrass form. If \( f(x) = x^3+dx^2+ex+f \), then the substitution \( x' = x+d/3 \) ("completing the cube") transforms the equation into \( y^2 = (x')^3+ax'+b \) for some \(a,b\) (reduced Weierstrass form).

(3) The field of definition of the coefficients of the polynomial has not been specified, because it is convenient to vary it depending on the situation. Elliptic curves over the complex or real numbers, the rational numbers, or a finite field are all of interest. (Note that the substitution in (2) is not possible if the characteristic of the field of definition is \( 3 \), that is, if \( 3 \) does not have a multiplicative inverse in the field.)

(4) More advanced textbooks use a more general definition of elliptic curve, e.g. "a plane curve of genus \( 1 \) with a rational point." The definition of genus is complicated (see below), but the definition given above does not appear to have an obvious rational point (a solution to the equation with all rational coordinates). The reason for this is that the "plane" in "plane curve" is not actually the two-dimensional Cartesian plane, but the two-dimensional projective plane. This is discussed in the next section.

For concreteness, let \( E \) be the elliptic curve given by the equation \( y^2=x^3-1 \). Let \( x = X/Z \) and \( y=Y/Z \). The equation becomes \( (Y/Z)^2 = (X/Z)^3-1 \), and clearing denominators gives \[ Y^2Z = X^3-Z^3. \] This is a homogeneous equation in three variables; "homogeneous" in this context means that all the monomials have the same degree (3). This implies that if \( (X,Y,Z) \) is a solution to this equation, so is \( (\lambda X, \lambda Y, \lambda Z) \) for any \( \lambda \). Two-dimensional projective space is defined to be the set of equivalence classes of points \( (X,Y,Z) \ne (0,0,0), \) where a point \( (X,Y,Z) \) is considered to be equivalent to \( (\lambda X,\lambda Y, \lambda Z) \) \( (\lambda \ne 0)\). Intuitively, the three variables are cut down to two dimensions by collapsing lines through the origin to a single point. The notation for a projective point is \( (X\colon Y \colon Z); \) so \( (X\colon Y \colon Z) = (\lambda X \colon \lambda Y \colon \lambda Z). \)

The homogeneous equation obtained from the original equation is sometimes referred to as the "projectivization" of the equation. It turns out that for elliptic curves in Weierstrass form, projectivization adds one point to the set of solutions \( (x,y) \) in the affine (Cartesian) plane. This is the subject of the next section.

There are two types of solutions \( (X,Y,Z) \) to the homogeneous equation: if \( Z \ne 0 \), then \( x = X/Z \) and \( y=Y/Z \) give a solution to \( y^2=x^3-1,\) and \( (x:y:1) \) is a point on the projective curve. But if \( Z = 0 \), there are points on the projective curve that do not correspond to points on the affine curve (dividing by \( Z \) is not allowed).

Setting \( Z=0 \) gives \( X=0, \) and \( Y \) can take any nonzero value (since \( (0:0:0) \) is not a valid projective point). But \( (0:Y:0) = (0:1:0) \), so there is precisely one projective point \( (0:1:0) \) on the curve which is not in the affine plane. It is easy to check that this remains true for any elliptic curve in Weierstrass form.

The point \( (0:1:0) \) is called the point at infinity. Geometrically, it can be thought of as a point infinitely high (and low) on the \( y\)-axis (its "coordinates" are \( \big(\frac00,\frac10\big)). \) This will be useful in the definition of the group law given below.

It is a general fact that projective curves have much nicer (and more symmetric) properties than affine curves. In particular, there is an important theorem of Bezout:

Two curves \( f(X,Y,Z) = 0 \) and \( g(X,Y,Z) = 0 \) defined by the vanishing of homogeneous polynomials \( f \) and \( g \) intersect in exactly \( \text{deg}(f)\text{deg}(g) \) points, counting multiplicity. \(_\square\)

This is a fundamental result in algebraic geometry. The proof is involved, but one important point about the result is that "counting multiplicity" are the two most important words in the statement--the proof consists of defining the multiplicity of an intersection of curves at a point in such a way that the theorem holds. (The first step, and the easiest, is that the multiplicity of the intersection is \( 1 \) if and only if the two curves are not tangent at the point.)

When one of the curves is a line, the result is that

Every line in the projective plane intersects an elliptic curve in three points, counting multiplicity.

This is not true for the affine curve: for instance, the line \( x=0\) in the affine plane intersects the curve \( y^2=x^3+1\) in two points \( (0,\pm 1). \) But the line \( X = 0 \) does intersect the projective curve in three points, \( (0:\pm 1:1) \) and the point at infinity \( (0:1:0) \).

The group law on an elliptic curve is what makes the theory of elliptic curves so special and interesting. In particular, it provides a way to generate points on the curve from other points. (For an introduction to group theory, see the wiki.)

The basic idea is that a line intersects the curve in three points, by Bezout's theorem, and the group law is obtained by setting the sum of three collinear points on the curve to the identity.

Since the group is written additively, the identity is sometimes called \( O \), but it should not be mistaken for the origin \( (0,0) \), which may not even be a point on the curve. In fact \( O \) turns out to be the point at infinity \( (0:1:0) \). As remarked above, the line at infinity \( Z=0 \) intersects the curve \( Y^2Z = Z^3f(X/Z) \) in exactly one point \( O \), so this point has multiplicity \( 3 \). The other lines through \( O \) are all of the form \( aX+bZ = 0 \), or in affine coordinates, \( ax+c=0\), where \( a\ne 0 \). These are the vertical lines in the affine plane.

Given two points \( P \) and \( Q\) on the curve, define \( R=-(P+Q) \) to be the third point on the line through \( P \) and \( Q \) that intersects the curve. Note that \( R=P \) or \( R=Q \) is possible if the line is tangent to the curve at \( P \) or \( Q \), as in picture 2 in the diagram above.

Then \( P+Q \) is obtained from \( R = -(P+Q) \) by reflecting it across the \( x\)-axis. This is because the vertical line between \( R \) and its reflection \( R'\) hits the curve in the point at infinity, so \( R+R'+O = O \), so \( R'=-R\).

Notes:

(1) If \( P \) and \(Q\) are rational points, and the equation of the curve has rational coefficients, then the point \( P+Q \) will be a rational point as well. This is extremely useful.

(2) Warning: Do not confuse this group law with coordinate-wise addition. If \( (1,1) \) and \( (2,3) \) are points on an elliptic curve, their sum will not be \( (3,4) \) (it is unlikely that \( (3,4) \) will even be a point on the elliptic curve). The group law obeys many of the same rules that regular addition does, but the point \( P+Q \) is best described geometrically and has no simple algebraic formula to describe it. There are formulas for \( P+Q \) using the coordinates of \( P,Q,\) and the coefficients of the elliptic curve, but they are quite involved and difficult to compute with.

(3) The proof that this law defines an abelian group has one nontrivial piece, and it is (somewhat surprisingly) the associativity of the law: \( P+(Q+S) = (P+Q)+S \). The proof of associativity requires some classical algebraic geometry and is omitted here.

(4) Any point on the curve can be used to generate other points; given \( P, \) the construction for \( 2P := P+P \) involves finding the third point on the tangent line to the curve at \( P \) (and then negating it). Sometimes this gives infinitely many new points; sometimes it does not.

Let \( E \) be the elliptic curve \( y^2=x^3-2x.\) Let \( P = (0,0) \) and \( Q = (2,2) \).

Starting with \( P \) does not lead to any more rational points, since \( 2P = P+P = O \); the tangent line to \( P \) is the vertical line \( x=0\). So \( 3P=P, 4P=O,\) etc.

Now to compute \( P+Q, \) first note that the line connecting them is the line \( y=x \). Then \( x^2=x^3-2x \) has three solutions, \( x=-1,0,2\). So \( -(P+Q) = (-1,-1), \) and so \( P+Q = (-1,1) \). This is a new point.

Even more interesting is \( Q+Q = 2Q \). The tangent line to \( E \) at \( Q \) is \( y = \frac52x-3 \), so finding the third point of intersection involves solving the equation \[ \left( \frac52 x-3\right)^2 = x^3-2x, \, \text{so } x^3-\frac{25}4 x^2 + 13x -9 = 0. \] It helps to realize that this cubic polynomial must be divisible by \( (x-2)^2 \), so the third factor is \( x-\frac94\). Plugging into the tangent line equation, the point \( -2Q \) is \( \left( \frac94, \frac{21}8 \right) \), and \( 2Q = \left( \frac94, -\frac{21}8\right) \). This is a rational point that would have been difficult to find by other means.

It turns out that the points \( Q,2Q,3Q,\ldots\) are all distinct, so there are infinitely many rational points on this curve.

Let \( G \) be the group of rational points on the elliptic curve. There is a very deep theorem about the structure of \( G \) that was proved by Mordell in 1922. (Its generalization to higher-dimensional varieties, which will not be discussed in this wiki, was due to Weil.)

Let \( E \) be an elliptic curve defined over the rational numbers. Then \( E({\mathbb Q}),\) the set of rational points on the curve, is finitely generated. That is, there is a finite set of rational points \( Q_1,\ldots,Q_s \in E({\mathbb Q}) \) such that any rational point on \( E \) can be written as \( a_1Q_1+a_2Q_2+\cdots+a_sQ_s \), for some integers \( a_i \). \(_\square\)

General abelian group theory implies that there is a nonnegative integer \( r \) and rational points \( P_1,\ldots,P_r \) such that every rational point can be written uniquely as a sum \[ a_1P_1+a_2P_2+\ldots+a_rP_r+T, \] where \( T \) is a torsion point. A torsion point \( T \in E \) is a point such that \( nT = O \) for some positive integer \( n \).

The integer \( r \) is called the rank of \( E({\mathbb Q})\).

If \( E \) is the curve \( y^2=x^3-2x, \) it turns out that \( r=1\) and there are only two torsion points, namely \( O \) (which is always a torsion point) and \( P = (0,0) \), which satisfies \( 2P = O \). The point \( Q = (2,2) \) is not a torsion point, and in fact every point \( R \in E({\mathbb Q}) \) can be written uniquely as \( mQ+nP \), where \( m \) is any integer and \( n=0\) or \(1\). (These facts are by no means obvious.)

Computing the rank of a given elliptic curve is a difficult computational problem, and there are not effective algorithms for the computation in the general case. The torsion subgroup is not as difficult to compute, and there is in fact a very short list of the possible numbers of torsion points.

(Mazur, 1976) The number of torsion points in \( E({\mathbb Q}) \) is either \( 1,2,3,4,5,6,7,8,9,10,12,\) or \( 16\). \(_\square\)

(In fact the theorem proves slightly more, in that it gives the structure of the group in each case. The group is either cyclic of order \( \le 10\) or \( 12,\) or a direct sum of a cyclic group of order \( 2 \) and a cyclic group of even order \( \le 8; \) every possibility actually occurs.)

Let \( E \) be the elliptic curve \( y^2+y = x^3-x^2 \). Then \( E \) has exactly five torsion points, the point at infinity and the four points obtained by setting both sides of the equation equal to \( 0 \). That is, \[ P = (0,0), 2P = (1,-1), 3P = (1,0), 4P = (0,-1). \] It turns out that the rank of \( E \) is zero, so these are the only rational points on the curve.

(By the way, this equation is not in Weierstrass form; but it can be transformed to Weierstrass form by making the substitution \( y' = y+1/2 \). Then \( (y')^2 = x^3-x^2+1/4. \) The original form is used in this case because the equation looks nicer.)

Rational points on elliptic curves are the subject of intense research, but there are still many unanswered questions about their structure. One simple question is

Is there some positive integer \( N \) such that the rank of every elliptic curve over \( {\mathbb Q}\) is \( \le N?\)

Many open questions in research mathematics have answers that are expected; e.g. very few mathematicians believe that the Riemann hypothesis is false, or believed that Fermat's last theorem was false before 1994 (when Andrew Wiles proved the theorem). This question about elliptic curves seems to be one of the exceptions. The consensus had been that the answer was "no," but recently mathematicians have found some evidence that the answer may be "yes"!

All that is known for sure is that if \( N \) exists, it is at least \( 28\), because the curve \[ \begin{align} y^2 + xy + y &= x^3 - x^2 - 20067762415575526585033208209338542750930230312178956502x \\ & + 34481611795030556467032985690390720374855944359319180361266008296291939448732243429 \end{align} \] has rank \( \ge 28 \). (This was discovered by Elkies, in 2006.)

Another open question comes from complex analysis. Given an elliptic curve with integer coefficients, one can build a function called an \( L\)-function for the curve, denoted \( L(E,s),\) which is a function of a complex variable \(s\) defined by a Dirichlet series whose coefficients are (almost always) equal to the number of points on the curve over various finite fields. It is analogous to the Riemann zeta function and shares many of its properties.

In the 1960s, Birch and Swinnerton-Dyer, two English mathematicians, gave a conjectural formulation of the behavior of the function at \( s=1 \). In particular, they conjectured that the first nonzero term of its Taylor series around \( 1 \) would be \( a_r(s-1)^r \), where \( r \) is the rank of the elliptic curve. Later, they gave a precise conjectural formula for \( a_r \) as well.

The Birch-Swinnerton-Dyer (BSD) conjecture is one of the seven Clay Millennium problems (each one has a prize of $1,000,000 to the solver), and is among the most important open problems in mathematics. It has been proven only in special cases. In particular, it is known that when the first nonzero term of its Taylor series is \( a_t(s-1)^t \) and \( t \) is \( 0 \) or \( 1, \) then \( t\) is indeed the rank of \( E \). If true, the BSD conjecture can sometimes be used to verify the rank of an elliptic curve.

Many Diophantine problems come down to finding the set of rational points on a given elliptic curve.

One example is the congruent number problem: which rational numbers are the areas of right triangles with rational sides? Such numbers are called congruent numbers.

Some elementary observations show that \( n \) is a congruent number if and only if the elliptic curve \( y^2 = x^3-n^2x \) has positive rank. (It can be shown that there are always only two torsion points on this curve, the point at infinity and \( (0,0) \); and a right triangle with area \( n \) and rational sides corresponds to another point on the curve.)

There is an effective (but slow) algorithm to determine whether a given \( n \) is a congruent number, but its correctness relies on an affirmative answer to the Birch-Swinnerton-Dyer conjecture.

Probably the most famous application of elliptic curves is the proof of Fermat's last theorem by Andrew Wiles in the 1990s. He showed that the \( L\)-functions of certain types of elliptic curves corresponded to analytic objects called modular forms in a precise way. A result from the 1980s showed that if \( a^p+b^p = c^p \) with \( abc\ne 0 \) and \( p \) an odd prime, then \( y^2=x(x-a^p)(x+b^p) \) could not be a modular elliptic curve, so this proved the theorem. See the Fermat's Last Theorem wiki for details.

Elliptic curves over finite fields are useful for cryptographic purposes. In particular, the number of points on an elliptic curve \( E \) defined over a finite field is finite, and is generally straightforward to compute. Suppose there is an elliptic curve \( E \) such that the number of points on \( E \) is a large prime number \( p \). Then the order of a nontrivial point \( P \) on \( E\) must be \( p\). The security of cryptosystems that use elliptic curves is based on the assumption that the so-called elliptic curve discrete log problem is hard: namely, given \( Q=nP \) and \( P \) (along with the elliptic curve \( E) \), determine \( n \).

Elliptic curve cryptography is becoming the standard in modern cryptographic applications, as it appears to be more secure and cheaper to implement than earlier public-key cryptography algorithms which use the arithmetic in finite fields directly (e.g. RSA encryption and the Diffie-Hellman protocol).