Elliptic curve

In mathematics, an elliptic curve is a smooth, projective algebraic curve of genus one, on which there is a specified point "O". An elliptic curve is in fact an abelian variety — that is, it has a multiplication defined algebraically with respect to which it is an abelian group — and "O" serves as the identity element. Often the curve itself, without "O" specified, is called an elliptic curve.

Any elliptic curve can be written as a plane algebraic curve defined by an equation of the form

:$y^2=x^3+ax+b,$

which is non-singular; that is, its graph has no cusps or self-intersections. (When the characteristic of the coefficient field is equal to 2 or 3, the above equation is not quite general enough to comprise all non-singular cubic curves; see below for a more precise definition.) The point "O" is actually the "point at infinity" in the projective plane.

If "y"² = "P"("x"), where "P" is any polynomial of degree three in "x" with no repeated roots, then we obtain a nonsingular plane curve of genus one, which is thus also an elliptic curve. If "P" has degree four and is squarefree this equation again describes a plane curve of genus one; however, it has no natural choice of identity element. More generally, any algebraic curve of genus one, for example from the intersection of two three-dimensional quadric surfaces, is called an elliptic curve, provided that it has at least one rational point.

Using the theory of elliptic functions, it can be shown that elliptic curves defined over the complex numbers correspond to embeddings of the torus into the complex projective plane. The torus is also an abelian group, and in fact this correspondence is also a group isomorphism.

Elliptic curves are especially important in number theory, and constitute a major area of current research; for example, they were used in the proof, by Andrew Wiles (assisted by Richard Taylor), of Fermat's Last Theorem. They also find applications in cryptography (see the article elliptic curve cryptography) and integer factorization.

An elliptic curve is "not" an ellipse: see elliptic integral for the origin of the term.

Elliptic curves over the real numbers

Although the formal definition of an elliptic curve is fairly technical and requires some background in algebraic geometry, it is possible to describe some features of elliptic curves over the real numbers using only high school algebra and geometry.

In this context, an elliptic curve is a plane curve defined by an equation of the form

:$y^2\; =\; x^3\; +\; ax\; +\; b,$

where "a" and "b" are real numbers. This type of equation is called a Weierstrass equation.

The definition of elliptic curve also requires that the curve be non-singular. Geometrically, this means that the graph has no cusps or self-intersections. Algebraically, this involves calculating the discriminant

: $Delta\; =\; -16(4a^3\; +\; 27b^2)\; ,$

The curve is non-singular if the discriminant is not equal to zero. (Although the factor −16 seems irrelevant here, it turns out to be convenient in more advanced study of elliptic curves.)

The graph of a non-singular curve has "two" components if its discriminant is positive, and "one" component if it is negative. For example, in the graphs shown above, the discriminant in the first case is 64, and in the second case is −368.

The group law

By adding a "point at infinity", we obtain the projective version of this curve. If "P" and "Q" are two points on the curve, then we can uniquely describe a third point which is the intersection of the curve with the line through "P" and "Q". If the line is tangent to the curve at a point, then that point is counted twice; and if the line is parallel to the "y"-axis, we define the third point as the point "at infinity". Exactly one of these conditions then holds for any pair of points on an elliptic curve.

It is then possible to introduce a group operation, "+", on the curve with the following properties: we consider the point at infinity to be 0, the identity of the group; and if a straight line intersects the curve at the points "P", "Q" and "R", then we require that "P" + "Q" + "R" = 0 in the group. One can check that this turns the curve into an abelian group, and thus into an abelian variety. It can be shown that the set of "K"-rational points (including the point at infinity) forms a subgroup of this group. If the curve is denoted by "E", then this subgroup is often written as "E"("K").

The above group can be described algebraically as well as geometrically. Given the curve "y"² = "x"³ − "px" − "q" over the field "K" (whose characteristic we assume to be neither 2 nor 3), and points "P" = ("x"_"P", "y"_"P") and "Q" = ("x"_"Q", "y"_"Q") on the curve, assume first that "x"_"P" ≠ "x"_"Q". Let "s" = ("y"_"P" − "y"_"Q")/("x"_"P" − "x"_"Q"); since "K" is a field, "s" is well-defined. Then we can define "R" = "P" + "Q" = ("x"_"R", "y"_"R") by

:$x\_R\; =\; s^2\; -\; x\_P\; -\; x\_Q,,$

:$y\_R\; =\; y\_P\; +\; s(x\_R\; -\; x\_P).,$

If "x"_"P" = "x"_"Q", then there are two options: if "y"_"P" = −"y"_"Q", including the case where "y"_"P" = "y"_"Q" = 0, then the sum is defined as 0; thus, the inverse of each point on the curve is found by reflecting it across the "x"-axis. If "y"_"P" = "y"_"Q" ≠ 0, then "R" = "P" + "P" = 2"P" = ("x"_"R", "- y"_"R") is given by

:$s\; =\; \{(3\{x\_P\}^2\; -\; p)\}/\{(2y\_P)\},,$

:$x\_R\; =\; s^2\; -\; 2x\_P,,$

:$y\_R\; =\; y\_P\; +\; s(x\_R\; -\; x\_P).,$

Elliptic curves over the complex numbers

The formulation of elliptic curves as the embedding of a torus in the complex projective plane follows naturally from a curious property of Weierstrass's elliptic functions. These functions and their first derivative are related by the formula

:$wp\text{'}(z)^2\; =\; 4wp(z)^3\; -g\_2wp(z)\; -\; g\_3.$

Here, $g\_2$ and $g\_3$ are constants; $wp(z)$ is the Weierstrass elliptic function and $wp\text{'}(z)$ its derivative. It should be clear that this relation is in the form of an elliptic curve (over the complex numbers). The Weierstrass functions are doubly-periodic; that is, they are periodic with respect to a lattice Λ; in essence, the Weierstrass functions are naturally defined on a torus $T=mathbb\{C\}/Lambda$. This torus may be embedded in the complex projective plane by means of the map

:$z\; mapsto\; (1,wp(z),\; wp\text{'}(z)).,$

This map is a group isomorphism, carrying the natural group structure of the torus into the projective plane. It is also an isomorphism of Riemann surfaces, and so topologically, a given elliptic curve looks like a torus. If the lattice Λ is related to a lattice "c"Λ by multiplication by a non-zero complex number "c", then the corresponding curves are isomorphic. Isomorphism classes of elliptic curves are specified by the j-invariant.

The isomorphism classes can be understood in a simpler way as well. The constants $g\_2$ and $g\_3$, called the modular invariants, are uniquely determined by the lattice, that is, by the structure of the torus. However, the complex numbers are the splitting field for polynomials, and so the elliptic curve may be written as

:$y^2=x(x-1)(x-lambda).,$

One finds that

:$g\_2\; =\; frac\{4^\{1/3\{3\}\; (lambda^2-lambda+1)$

and

:$g\_3=frac\{1\}\{27\}\; (lambda+1)(2lambda^2-5lambda+2)$

so that the modular discriminant is

:$Delta\; =\; g\_2^3-27g\_3^2\; =\; lambda^2(lambda-1)^2.,$

Here, λ is sometimes called the modular lambda function.

Note that the uniformization theorem states that every compact Riemann surface of genus one can be represented as a torus.

Elliptic curves over a general field

Elliptic curves can be defined over any field "K"; the formal definition of an elliptic curve is a non-singular projective algebraic curve over "K" with genus 1 with a given point defined over "K".

If the characteristic of "K" is neither 2 nor 3, then every elliptic curve over "K" can be written in the form:$y^2=x^3-px-q$where "p" and "q" are elements of "K" such that the right hand side polynomial "x"³ − "px" − "q" does not have any double roots. If the characteristic is 2 or 3, then more terms need to be kept: in characteristic 3, the most general equation is of the form:$y^2\; =\; 4x^3\; +\; b\_2\; x^2\; +\; 2b\_4\; x\; +\; b\_6$for arbitrary constants $b\_2,\; b\_4,\; b\_6$ such that the polynomial on the right-hand side has distinct roots (the notation is chosen for historical reasons). In characteristic 2, even this much is not possible, and the most general equation is:$y^2\; +\; a\_1\; xy\; +\; a\_3\; y\; =\; x^3\; +\; a\_2\; x^2\; +\; a\_4\; x\; +\; a\_6$provided that the variety it defines is nonsingular. If characteristic were not an obstruction, each equation would reduce to the previous ones by a suitable change of variables.

One typically takes the curve to be the set of all points ("x","y") which satisfy the above equation and such that both "x" and "y" are elements of the algebraic closure of "K". Points of the curve whose coordinates both belong to "K" are called "K"-rational points.

Isogeny

Let "E" and "D" be elliptic curves over a field "k". An "isogeny" between "E" and "D" is a finite morphism $f\; :\; E\; o\; D$ of varieties that preserves basepoints (in other words, maps the given point on "E" to that on "D").

The two curves are called "isogenous" if there is an isogeny between them. This is an equivalence relation, symmetry being due to the existence of the dual isogeny. Every isogeny is an algebraic homomorphism and thus induces homomorphisms of the groups of the elliptic curves for $k$-valued points.

See also Abelian varieties up to isogeny.

Connections to number theory

The Mordell-Weil theorem states that if the underlying field "K" is the field of rational numbers (or more generally a number field), then the group of "K"-rational points is finitely generated. This means that the group can be expressed as the direct sum of a free abelian group and a finite torsion subgroup. While it is relatively easy to determine the torsion subgroup of "E"("K"), no general algorithm is known to compute the rank of the free subgroup. A formula for this rank is given by the Birch and Swinnerton-Dyer conjecture.

The recent proof of Fermat's last theorem proceeded by proving a special case of the deep Taniyama-Shimura conjecture relating elliptic curves over the rationals to modular forms; this conjecture has since been completely proved.

While the precise number of rational points of an elliptic curve "E" over a finite field F_"p" is in general rather difficult to compute, Hasse's theorem on elliptic curves tells us

:$\{left|\; \#\; E(\; mathbb\{F\}\_p\; )\; -\; p\; -\; 1\; ight|\; leq\; 2\; sqrt\{p\}.\; \}$

This fact can be understood and proven with thehelp of some general theory; see local zeta function, Étale cohomology. The number of points on a specific curve can be computed with Schoof's algorithm.

For further developments see arithmetic of abelian varieties.

Algorithms that use elliptic curves

Elliptic curves over finite fields are used in some cryptographic applications as well as for integer factorization. Typically, the general idea in these applications is that a known algorithm which makes use of certain finite groups is rewritten to use the groups of rational points of elliptic curves. For more see also:

* Elliptic curve cryptography
* Elliptic Curve DSA
* Lenstra elliptic curve factorization
* Elliptic curve primality proving

ee also

*Riemann-Hurwitz formula
*Nagell–Lutz theorem
*Complex multiplication
*Arithmetic dynamics

References

Serge Lang, in the introduction to the book cited below, stated that "It is possible to write endlessly on elliptic curves. (This is not a threat.)" The following short list is thus at best a guide to the vast expository literature available on the theoretical, algorithmic, and cryptographic aspects of elliptic curves.
* cite book
author = I. Blake
coauthors = G. Seroussi, N. Smart, N.J. Hitchin
year = 2000
title = Elliptic Curves in Cryptography
series=LMS Lecture Notes
publisher = Cambridge University Press
isbn=0-521-65374-6
* cite book
author = Richard Crandall
coauthors = Carl Pomerance
year = 2001
title = Prime Numbers: A Computational Perspective
publisher = Springer-Verlag
edition = 1st edition
isbn=0-387-94777-9
chapter = Chapter 7: Elliptic Curve Arithmetic
pages = 285–352
* cite book
author = John Cremona | authorlink = John Cremona
year = 1997 | edition=2nd edition
title = Algorithms for Modular Elliptic Curves
publisher = Cambridge University Press
url = http://www.warwick.ac.uk/staff/J.E.Cremona//book/fulltext/index.html
isbn=0-521-59820-6
*
* cite book
author = Dale Husemöller
year = 2004
title = Elliptic Curves
edition = 2nd edition
series = Graduate Texts in Mathematics
volume=111
publisher = Springer
isbn=0-387-95490-2
* cite book
author = Kenneth Ireland | authorlink = Kenneth Ireland
coauthors = Michael I. Rosen
year = 1998
title = A Classical Introduction to Modern Number Theory
volume=84 | series=Graduate Texts in Mathematics
publisher = Springer
edition = 2nd revised edition
chapter = Chapters 18 and 19
isbn=0-387-97329-X
* cite book
author = Anthony Knapp | authorlink = Anthony Knapp
year = 1992
title = Elliptic Curves
series = Math Notes | volume=40
publisher = Princeton University Press
* cite book
author = Neal Koblitz | authorlink = Neal Koblitz
year = 1993 | edition=2nd edition
title = Introduction to Elliptic Curves and Modular Forms
series = Graduate Texts in Mathematics
volume=97
publisher = Springer-Verlag
isbn=0-387-97966-2
* cite book
author = Neal Koblitz | authorlink = Neal Koblitz
year = 1994
title = A Course in Number Theory and Cryptography
series = Graduate Texts in Mathematics
volume=114
publisher = Springer-Verlag
edition = 2nd edition
id = ISBN 0-387-94293-9
chapter = Chapter 6
*
* cite book|author=Henry McKean | coauthors=Victor Moll
title=Elliptic curves: function theory, geometry and arithmetic
publisher=Cambridge University Press|isbn=0-521-65817-9|year=1999
*
* cite book
author = Joseph H. Silverman | authorlink=Joseph H. Silverman
year = 1986
title = The Arithmetic of Elliptic Curves
series = Graduate Texts in Mathematics
volume=106
publisher = Springer-Verlag
isbn=0-387-96203-4
* cite book
author = Joseph H. Silverman | authorlink=Joseph H. Silverman
year = 1994
title = Advanced Topics in the Arithmetic of Elliptic Curves
series = Graduate Texts in Mathematics
volume=151
publisher = Springer-Verlag
isbn=0-387-94328-5
* cite book
author = Joseph H. Silverman | authorlink=Joseph H. Silverman
coauthors = John Tate
year = 1992
title = Rational Points on Elliptic Curves
publisher = Springer-Verlag
isbn=0-387-97825-9
*
* cite book
author = Lawrence Washington | authorlink=Lawrence Washington
year = 2003
title = Elliptic Curves: Number Theory and Cryptography
publisher = Chapman & Hall/CRC
isbn=1-58488-365-0

External links

* [http://www.math.niu.edu/~rusin/known-math/index/14H52.html The Mathematical Atlas: 14H52 Elliptic Curves]
*

* [http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=300&objectType=File Matlab code for implicit function plotting] - Can be used to plot elliptic curves.