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 , where is a cubic polynomial with no repeated roots.
(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 .
(2) The equation above is said to be in Weierstrass form. If , then the substitution ("completing the cube") transforms the equation into for some (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 , that is, if 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 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 be the elliptic curve given by the equation . Let and . The equation becomes , and clearing denominators gives 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 is a solution to this equation, so is for any . Two-dimensional projective space is defined to be the set of equivalence classes of points where a point is considered to be equivalent to . 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 so
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 in the affine (Cartesian) plane. This is the subject of the next section.
There are two types of solutions to the homogeneous equation: if , then and give a solution to and is a point on the projective curve. But if , there are points on the projective curve that do not correspond to points on the affine curve (dividing by is not allowed).
Setting gives and can take any nonzero value (since is not a valid projective point). But , so there is precisely one projective point 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 is called the point at infinity. Geometrically, it can be thought of as a point infinitely high (and low) on the -axis (its "coordinates" are 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 and defined by the vanishing of homogeneous polynomials and intersect in exactly points, counting multiplicity.
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 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 in the affine plane intersects the curve in two points But the line does intersect the projective curve in three points, and the point at infinity .
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 , but it should not be mistaken for the origin , which may not even be a point on the curve. In fact turns out to be the point at infinity . As remarked above, the line at infinity intersects the curve in exactly one point , so this point has multiplicity . The other lines through are all of the form , or in affine coordinates, , where . These are the vertical lines in the affine plane.
Given two points and on the curve, define to be the third point on the line through and that intersects the curve. Note that or is possible if the line is tangent to the curve at or , as in picture 2 in the diagram above.
Then is obtained from by reflecting it across the -axis. This is because the vertical line between and its reflection hits the curve in the point at infinity, so , so .
(1) If and are rational points, and the equation of the curve has rational coefficients, then the point will be a rational point as well. This is extremely useful.
(2) Warning: Do not confuse this group law with coordinate-wise addition. If and are points on an elliptic curve, their sum will not be (it is unlikely that 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 is best described geometrically and has no simple algebraic formula to describe it. There are formulas for using the coordinates of 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: . 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 the construction for involves finding the third point on the tangent line to the curve at (and then negating it). Sometimes this gives infinitely many new points; sometimes it does not.
Let be the elliptic curve Let and .
Starting with does not lead to any more rational points, since ; the tangent line to is the vertical line . So etc.
Now to compute first note that the line connecting them is the line . Then has three solutions, . So and so . This is a new point.
Even more interesting is . The tangent line to at is , so finding the third point of intersection involves solving the equation It helps to realize that this cubic polynomial must be divisible by , so the third factor is . Plugging into the tangent line equation, the point is , and . This is a rational point that would have been difficult to find by other means.
It turns out that the points are all distinct, so there are infinitely many rational points on this curve.
Let be the group of rational points on the elliptic curve. There is a very deep theorem about the structure of 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 be an elliptic curve defined over the rational numbers. Then the set of rational points on the curve, is finitely generated. That is, there is a finite set of rational points such that any rational point on can be written as , for some integers .
General abelian group theory implies that there is a nonnegative integer and rational points such that every rational point can be written uniquely as a sum where is a torsion point. A torsion point is a point such that for some positive integer .
The integer is called the rank of .
If is the curve it turns out that and there are only two torsion points, namely (which is always a torsion point) and , which satisfies . The point is not a torsion point, and in fact every point can be written uniquely as , where is any integer and or . (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 is either or .
(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 or or a direct sum of a cyclic group of order and a cyclic group of even order every possibility actually occurs.)
Let be the elliptic curve . Then has exactly five torsion points, the point at infinity and the four points obtained by setting both sides of the equation equal to . That is, It turns out that the rank of 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 . Then 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 such that the rank of every elliptic curve over is
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 exists, it is at least , because the curve has rank . (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 -function for the curve, denoted which is a function of a complex variable 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 . In particular, they conjectured that the first nonzero term of its Taylor series around would be , where is the rank of the elliptic curve. Later, they gave a precise conjectural formula for 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 and is or then is indeed the rank of . 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 is a congruent number if and only if the elliptic curve has positive rank. (It can be shown that there are always only two torsion points on this curve, the point at infinity and ; and a right triangle with area and rational sides corresponds to another point on the curve.)
There is an effective (but slow) algorithm to determine whether a given 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 -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 with and an odd prime, then 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 defined over a finite field is finite, and is generally straightforward to compute. Suppose there is an elliptic curve such that the number of points on is a large prime number . Then the order of a nontrivial point on must be . 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 and (along with the elliptic curve , determine .
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).