# Elliptic curve

In

mathematics , an**elliptic curve**is a smooth, projectivealgebraic curve of genus one, on which there is a specified point "O". An elliptic curve is in fact anabelian variety — that is, it has a multiplication defined algebraically with respect to which it is anabelian 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 theprojective plane .If "y"

^{2}= "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, anyalgebraic 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 function s, it can be shown that elliptic curves defined over thecomplex number s correspond to embeddings of thetorus into thecomplex projective plane . The torus is also an abelian group, and in fact this correspondence is also agroup 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, byAndrew Wiles (assisted by Richard Taylor), ofFermat's Last Theorem . They also find applications incryptography (see the articleelliptic curve cryptography ) andinteger factorization .An elliptic curve is

**"not**" anellipse : seeelliptic 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 thereal numbers using only high schoolalgebra andgeometry .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 thediscriminant : $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 anabelian variety . It can be shown that the set of "K"-rational point s (including the point at infinity) forms asubgroup 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"

^{2}= "x"^{3}− "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 thecomplex projective plane follows naturally from a curious property ofWeierstrass'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 ofRiemann surface s, 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 thej-invariant .The isomorphism classes can be understood in a simpler way as well. The constants $g\_2$ and $g\_3$, called the

modular invariant s, are uniquely determined by the lattice, that is, by the structure of the torus. However, the complex numbers are thesplitting 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 compactRiemann 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"

^{3}− "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 thedual isogeny . Every isogeny is an algebraichomomorphism 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 ofrational number s (or more generally anumber field ), then the group of "K"-rational points is finitely generated. This means that the group can be expressed as the direct sum of afree abelian group and a finitetorsion 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 theBirch and Swinnerton-Dyer conjecture .The recent proof of

Fermat's last theorem proceeded by proving a special case of the deepTaniyama-Shimura conjecture relating elliptic curves over the rationals tomodular form s; 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 withSchoof'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 knownalgorithm 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.

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Elliptic curve cryptography**— (ECC) is an approach to public key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz[1] and Victor S. Miller[2] in 1985.… … Wikipedia**Elliptic Curve DSA**— (ECDSA) is a variant of the Digital Signature Algorithm (DSA) which operates on elliptic curve groups. As with elliptic curve cryptography in general, the bit size of the public key believed to be needed for ECDSA is about twice the size of the… … Wikipedia**Elliptic curve primality proving**— (ECPP) is a method based on elliptic curves to prove the primality of a number. It is a general purpose algorithm, meaning it does not depend on the number being a special form. ECPP is currently in practice the fastest known algorithm for… … Wikipedia**Elliptic Curve Diffie-Hellman**— (ECDH) is a key agreement protocol that allows two parties to estabilish a shared secret key over an insecure channel [NIST, [http://csrc.nist.gov/publications/nistpubs/800 56A/SP800 56A Revision1 Mar08 2007.pdf Special Publication 800 56A,… … Wikipedia**Elliptic Curve Digital Signature Algorithm**— (ECDSA) est un algorithme de signature numérique. C est une variante du standard DSA qui à la différence de l algorithme d origine utilise la cryptographie sur les courbes elliptiques. Les avantages de ECDSA sur DSA et RSA sont des longueurs de… … Wikipédia en Français**Elliptic curve digital signature algorithm**— (ECDSA) est un algorithme de signature numérique à clé publique, variante de DSA il fait appel à la cryptographie sur les courbes elliptiques. Sommaire 1 Introduction 2 Algorithme 2.1 Préparation des clé … Wikipédia en Français**Elliptic Curve Diffie-Hellman**— oder abgekürzt ECDH ist eine Implementation des Diffie Hellman Schlüsselaustauschs mittels elliptischer Kurven. Kategorie: Kryptologisches Verfahren … Deutsch Wikipedia**Elliptic Curve Cryptography**— Elliptische Kurve über Unter Elliptic Curve Cryptography (ECC) oder deutsch Elliptische Kurven Kryptographie versteht man asymmetrische Kryptosysteme, die Operationen auf elliptischen Kurven über endlichen Körpern v … Deutsch Wikipedia**Elliptic Curve DSA**— Der Elliptic Curve Digital Signature Algorithmus (ECDSA) (deutsch: digitaler Signatur Algorithmus mit elliptischen Kurven) ist eine Variante des Digital Signature Algorithm (DSA), der Elliptische Kurven Kryptographie verwendet. Inhaltsverzeichnis … Deutsch Wikipedia**Elliptic Curve Integrated Encryption Scheme**— Das Elliptic Curve Integrated Encryption Scheme (ECIES) ist ein hybrides Verschlüsselungsverfahren, dem elliptische Kurven zugrunde liegen. Als Hybridverfahren kombiniert es ein asymmetrisches Verfahren, das zum Versenden eines symmetrischen… … Deutsch Wikipedia