Elliptic curve

Graphs of curves y² = x³ − x and y² = x³ − x + 1

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

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

${\displaystyle y^{2}=x^{3}+ax+b}$

after a linear change of variables (a and b are real numbers). This type of equation is called a Weierstrass equation, and said to be in Weierstrass form, or Weierstrass normal form.

The definition of elliptic curve also requires that the curve is non-singular. Geometrically, this means that the graph has no cusps, self-intersections, or isolated points. Algebraically, this holds if and only if the discriminant

${\displaystyle \Delta =-16\left(4a^{3}+27b^{2}\right)}$

is not equal to zero. (Although the factor −16 is irrelevant to whether or not the curve is non-singular, this definition of the discriminant is useful in a more advanced study of elliptic curves.)[3]

The real 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 in figure to the right, the discriminant in the first case is 64, and in the second case is −368.

When working in the projective plane, we can define a group structure on any smooth cubic curve. In Weierstrass normal form, such a curve will have an additional point O at infinity (the homogeneous coordinates [0:1:0]), which serves as the identity of the group.

Since the curve is symmetrical about the x-axis, given any point P, we can take −P to be the point opposite it. ${\displaystyle -O=O}$, as it is the identity element.

If P and Q are two points on the curve, then we can uniquely describe a third point P + Q in the following way. First, draw the line that intersects P and Q. This will generally intersect the cubic at a third point, R. We then take P + Q to be −R, the point opposite R.

This definition for addition works except in a few special cases related to the point at infinity and intersection multiplicity. The first is when one of the points is O. Here, we define P + O = P = O + P, making O the identity of the group. Next, if P and Q are opposites of each other, we define P + Q = O. Lastly, if P = Q we only have one point, thus we cannot define the line between them. In this case, we use the tangent line to the curve at this point as our line. In most cases, the tangent will intersect a second point R and we can take its opposite. However, if P happens to be an inflection point (a point where the concavity of the curve changes), we take R to be P itself and P + P is simply the point opposite itself.

For a cubic curve not in Weierstrass normal form, we can still define a group structure by designating one of its nine inflection points as the identity O. In the projective plane, each line will intersect a cubic at three points when accounting for multiplicity. For a point P, −P is defined as the unique third point on the line passing through O and P. Then, for any P and Q, P + Q is defined as −R where R is the unique third point on the line containing P and Q.

Let K be a field over which the curve is defined (that is, the coefficients of the defining equation or equations of the curve are in K) and denote the curve by E. Then the K-rational points of E are the points on E whose coordinates all lie in K, including the point at infinity. The set of K-rational points is denoted by E(K). E(K) is a group, because properties of polynomial equations show that if P is in E(K), then −P is also in E(K), and if two of P, Q, R are in E(K), then so is the third. Additionally, if K is a subfield of L, then E(K) is a subgroup of E(L).

The above groups can be described algebraically as well as geometrically. Given the curve y² = x³ + ax + b 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 (case 1). Let y = sx + d be the equation of the line that intersects P and Q, which has the following slope:

${\displaystyle s={\frac {y_{P}-y_{Q}}{x_{P}-x_{Q}}}}$

The line equation and the curve equation intersect at the points x_P, x_Q, and x_R, so the equations have identical y values.

${\displaystyle \left(sx+d\right)^{2}=x^{3}+ax+b}$

which is equivalent to

${\displaystyle x^{3}-s^{2}x^{2}-2sdx+ax+b-d^{2}=0}$

We know that this equation has its roots at exactly the same x values as

${\displaystyle (x-x_{P})(x-x_{Q})(x-x_{R})=x^{3}+x^{2}(-x_{P}-x_{Q}-x_{R})+x(x_{P}x_{Q}+x_{P}x_{R}+x_{Q}x_{R})-x_{P}x_{Q}x_{R}}$

We equate the coefficient for x² and solve for x_R.

${\displaystyle x_{R}=s^{2}-x_{P}-x_{Q}}$

y_R follows from the line equation

${\displaystyle y_{R}=y_{P}+s(x_{R}-x_{P})}$

and is an element of K. This therefore defines R = (x_R, y_R) = −(P + Q).

If x_P = x_Q, then there are two options: if y_P = −y_Q (case 3), including the case where y_P = y_Q = 0 (case 4), 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 Q = P and R = (x_R, y_R) = −(P + P) = −2P = −2Q (case 2 using P as R). The slope is given by the tangent to the curve at (x_P, y_P).

${\displaystyle {\begin{aligned}s&={\frac {3{x_{P}}^{2}+a}{2y_{P}}}\\x_{R}&=s^{2}-2x_{P}\\y_{R}&=y_{P}+s(x_{R}-x_{P})\end{aligned}}}$

A curve E defined over the field of rational numbers is also defined over the field of real numbers. Therefore, the law of addition (of points with real coordinates) by the tangent and secant method can be applied to E. The explicit formulae show that the sum of two points P and Q with rational coordinates has again rational coordinates, since the line joining P and Q has rational coefficients. This way, one shows that the set of rational points of E forms a subgroup of the group of real points of E. As this group, it is an abelian group, that is, P + Q = Q + P.

Set of affine points of elliptic curve y² = x³ − x over finite field F₆₁.

Let K = F_q be the finite field with q elements and E an elliptic curve defined over K. While the precise number of rational points of an elliptic curve E over K is in general difficult to compute, Hasse's theorem on elliptic curves gives the following inequality:

${\displaystyle |\#E(K)-(q+1)|\leq 2{\sqrt {q}}}$

(which includes the point at infinity).

In other words, the number of points on the curve grows proportionally to the number of elements in the field. This fact can be understood and proven with the help of some general theory; see local zeta function and étale cohomology for example.

Set of affine points of elliptic curve y² = x³ − x over finite field F₈₉.

The set of points E(F_q) is a finite abelian group. It is always cyclic or the product of two cyclic groups, depending whether q is even or odd. For example,[17] the curve defined by

${\displaystyle y^{2}=x^{3}-x}$

over F₇₁ has 72 points (71 affine points including (0,0) and one point at infinity) over this field, whose group structure is given by Z/2Z × Z/36Z. The number of points on a specific curve can be computed with Schoof's algorithm.

Studying the curve over the field extensions of F_q is facilitated by the introduction of the local zeta function of E over F_q, defined by a generating series (also see above)

${\displaystyle Z(E(K),T)=\exp \left(\sum _{n=1}^{\infty }\#\left[E(K_{n})\right]{T^{n} \over n}\right)}$

where the field K_n is the (unique up to isomorphism) extension of K = F_q of degree n (that is, F_qⁿ).

The zeta function is a rational function in T. To see this, there is an integer ${\displaystyle a_{n}}$ such that

${\displaystyle \#E_{q}=1-a_{n}+q^{n}=1-\alpha ^{n}-{\bar {\alpha }}^{n}+q^{n}}$

with complex number ${\displaystyle \alpha }$ and its complex conjugate. We can choose ${\displaystyle \alpha }$ so that its absolute value is ${\displaystyle {\sqrt {q}}}$, that is ${\displaystyle \alpha =q^{\frac {1}{2}}e^{i\theta },{\bar {\alpha }}=q^{\frac {1}{2}}e^{-i\theta }}$, and that ${\displaystyle \cos \theta ={\frac {a_{n}}{2{\sqrt {q}}}}}$. This can be used to prove Hasse's Theorem, as ${\displaystyle 2{\sqrt {q}}}$ is the minimum value of ${\displaystyle q^{n}+q^{1-n}}$.

The local zeta function then becomes

${\displaystyle Z_{E}(T)=\exp \left(\sum _{n=1}^{\infty }\left(1-\alpha ^{n}-{\bar {\alpha }}^{n}+q^{n}\right){T^{n} \over n}\right)}$

${\displaystyle Z_{E}(T)=\exp \left(\sum _{n=1}^{\infty }{T^{n} \over n}-\sum _{n=1}^{\infty }\alpha ^{n}{T^{n} \over n}-\sum _{n=1}^{\infty }{\bar {\alpha }}^{n}{T^{n} \over n}+\sum _{n=1}^{\infty }q^{n}{T^{n} \over n}\right)}$

${\displaystyle Z_{E}(T)=\exp \left(-\ln(1-T)+\ln(1-\alpha T)+\ln(1-{\bar {\alpha }}T)-\ln(1-qT)\right)}$

${\displaystyle Z_{E}(T)=\exp \left(\ln {\frac {(1-\alpha T)(1-{\bar {\alpha }}T)}{(1-T)(1-qT)}}\right)}$

${\displaystyle Z_{E}(T)={\frac {(1-\alpha T)(1-{\bar {\alpha }}T)}{(1-T)(1-qT)}}}$

Then ${\displaystyle (1-\alpha T)(1-{\bar {\alpha }}T)=1-aT+qT^{2}}$, so finally

${\displaystyle Z(E(K),T)={\frac {1-aT+qT^{2}}{(1-qT)(1-T)}}}$

For example,[18] the zeta function of E : y² + y = x³ over the field F₂ is given by

${\displaystyle {\frac {1+2T^{2}}{(1-T)(1-2T)}}}$

which follows from:

${\displaystyle \left|E(\mathbf {F} _{2^{r}})\right|={\begin{cases}2^{r}+1&r{\text{ odd}}\\2^{r}+1-2(-2)^{\frac {r}{2}}&r{\text{ even}}\end{cases}}}$

The functional equation is

${\displaystyle Z\left(E(K),{\frac {1}{qT}}\right)={\frac {1-a{\frac {1}{qT}}+q\left({\frac {1}{qT}}\right)^{2}}{(1-q{\frac {1}{qT}})(1-{\frac {1}{qT}})}}={\frac {q^{2}T^{2}-aqT+q}{(qT-q)(qT-1)}}=Z(E(K),T)}$

Set of affine points of elliptic curve y² = x³ − x over finite field F₇₁.

The Sato–Tate conjecture is a statement about how the error term ${\displaystyle 2{\sqrt {q}}}$ in Hasse's theorem varies with the different primes q, if an elliptic curve E over Q is reduced modulo q. It was proven (for almost all such curves) in 2006 due to the results of Taylor, Harris and Shepherd-Barron,[19] and says that the error terms are equidistributed.

Elliptic curves over finite fields are notably applied in cryptography and for the factorization of large integers. These algorithms often make use of the group structure on the points of E. Algorithms that are applicable to general groups, for example the group of invertible elements in finite fields, F*_q, can thus be applied to the group of points on an elliptic curve. For example, the discrete logarithm is such an algorithm. The interest in this is that choosing an elliptic curve allows for more flexibility than choosing q (and thus the group of units in F_q). Also, the group structure of elliptic curves is generally more complicated.

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 and endowed with a distinguished 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

${\displaystyle y^{2}=x^{3}-px-q}$

after a linear change of variables. Here 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

${\displaystyle y^{2}=4x^{3}+b_{2}x^{2}+2b_{4}x+b_{6}}$

for arbitrary constants b₂, b₄, b₆ 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

${\displaystyle 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 non-singular. If characteristic were not an obstruction, each equation would reduce to the previous ones by a suitable linear 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.

Many of the preceding results remain valid when the field of definition of E is a number field K, that is to say, a finite field extension of Q. In particular, the group E(K) of K-rational points of an elliptic curve E defined over K is finitely generated, which generalizes the Mordell–Weil theorem above. A theorem due to Loïc Merel shows that for a given integer d, there are (up to isomorphism) only finitely many groups that can occur as the torsion groups of E(K) for an elliptic curve defined over a number field K of degree d. More precisely,[20] there is a number B(d) such that for any elliptic curve E defined over a number field K of degree d, any torsion point of E(K) is of order less than B(d). The theorem is effective: for d > 1, if a torsion point is of order p, with p prime, then

${\displaystyle p<d^{3d^{2}}}$

As for the integral points, Siegel's theorem generalizes to the following: Let E be an elliptic curve defined over a number field K, x and y the Weierstrass coordinates. Then there are only finitely many points of E(K) whose x-coordinate is in the ring of integers O_K.

The properties of the Hasse–Weil zeta function and the Birch and Swinnerton-Dyer conjecture can also be extended to this more general situation.

An elliptic curve over the complex numbers is obtained as a quotient of the complex plane by a lattice Λ, here spanned by two fundamental periods ω₁ and ω₂. The four-torsion is also shown, corresponding to the lattice 1/4Λ containing Λ.

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

${\displaystyle \wp '(z)^{2}=4\wp (z)^{3}-g_{2}\wp (z)-g_{3}}$

Here, g₂ and g₃ are constants; ℘(z) is the Weierstrass elliptic function and ℘′(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 = C/Λ. This torus may be embedded in the complex projective plane by means of the map

${\displaystyle z\mapsto \left[1:\wp (z):{\tfrac {1}{2}}\wp '(z)\right]}$

This map is a group isomorphism of the torus (considered with its natural group structure) with the chord-and-tangent group law on the cubic curve which is the image of this map. It is also an isomorphism of Riemann surfaces from the torus to the cubic curve, so topologically, an elliptic curve is a torus. If the lattice Λ is related by multiplication by a non-zero complex number c to a lattice 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₂ and g₃, called the modular invariants, are uniquely determined by the lattice, that is, by the structure of the torus. However, all real polynomials factorize completely into linear factors over the complex numbers, since the field of complex numbers is the algebraic closure of the reals. So, the elliptic curve may be written as

${\displaystyle y^{2}=x(x-1)(x-\lambda )}$

One finds that

${\displaystyle {\begin{aligned}g_{2}'&={\frac {\sqrt[{3}]{4}}{3}}\left(\lambda ^{2}-\lambda +1\right)\\[4pt]g_{3}'&={\frac {1}{27}}(\lambda +1)\left(2\lambda ^{2}-5\lambda +2\right)\end{aligned}}}$

and

${\displaystyle j(\tau )=1728{\frac {{g_{2}'}^{3}}{{g_{2}'}^{3}-27{g_{3}'}^{2}}}=256{\frac {\left(\lambda ^{2}-\lambda +1\right)^{3}}{\lambda ^{2}\left(\lambda -1\right)^{2}}}}$

with j-invariant j(τ) and λ(τ) is sometimes called the modular lambda function. For example, let τ = 2i, then λ(2i) = (−1 + √2)⁴ which implies g′₂, g′₃, and therefore g′₂³
− 27g′₃²
of the formula above are all algebraic numbers if τ involves an imaginary quadratic field. In fact, it yields the integer j(2i) = 66³ = 287496.

In contrast, the modular discriminant

${\displaystyle \Delta (\tau )=g_{2}(\tau )^{3}-27g_{3}(\tau )^{2}=(2\pi )^{12}\,\eta ^{24}(\tau )}$

is generally a transcendental number. In particular, the value of the Dedekind eta function η(2i) is

${\displaystyle \eta (2i)={\frac {\Gamma \left({\frac {1}{4}}\right)}{2^{\frac {11}{8}}\pi ^{\frac {3}{4}}}}}$

Note that the uniformization theorem implies that every compact Riemann surface of genus one can be represented as a torus. This also allows an easy understanding of the torsion points on an elliptic curve: if the lattice Λ is spanned by the fundamental periods ω₁ and ω₂, then the n-torsion points are the (equivalence classes of) points of the form

${\displaystyle {\frac {a}{n}}\omega _{1}+{\frac {b}{n}}\omega _{2}}$

for integers a and b in the range 0 ≤ (a, b) < n.

If

${\displaystyle E:y^{2}=4(x-e_{1})(x-e_{2})(x-e_{3})}$

is an elliptic curve over the complex numbers and

${\displaystyle a_{0}={\sqrt {e_{1}-e_{3}}},\qquad b_{0}={\sqrt {e_{1}-e_{2}}},\qquad c_{0}={\sqrt {e_{2}-e_{3}}},}$

then a pair of fundamental periods of E can be calculated very rapidly by

${\displaystyle \omega _{1}={\frac {\pi }{\operatorname {M} (a_{0},b_{0})}},\qquad \omega _{2}={\frac {\pi }{\operatorname {M} (c_{0},ib_{0})}}}$

M(w, z) is the arithmetic–geometric mean of w and z. At each step of the arithmetic–geometric mean iteration, the signs of z_n arising from the ambiguity of geometric mean iterations are chosen such that |w_n − z_n| ≤ |w_n + z_n| where w_n and z_n denote the individual arithmetic mean and geometric mean iterations of w and z, respectively. When |w_n − z_n| = |w_n + z_n|, there is an additional condition that Im(z_n/w_n) > 0.[21]

Over the complex numbers, every elliptic curve has nine inflection points. Every line through two of these points also passes through a third inflection point; the nine points and 12 lines formed in this way form a realization of the Hesse configuration.

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 Diffie–Hellman key exchange
• Supersingular isogeny key exchange
• Elliptic curve digital signature algorithm
• EdDSA digital signature algorithm
• Dual EC DRBG random number generator
• Lenstra elliptic-curve factorization
• Elliptic curve primality proving

• Hessian curve
• Edwards curve
• Twisted curve
• Twisted Hessian curve
• Twisted Edwards curve
• Doubling-oriented Doche–Icart–Kohel curve
• Tripling-oriented Doche–Icart–Kohel curve
• Jacobian curve
• Montgomery curve

• Arithmetic dynamics
• Elliptic algebra
• Elliptic surface
• Comparison of computer algebra systems
• Isogeny
• j-line
• Level structure (algebraic geometry)
• Modularity theorem
• Moduli stack of elliptic curves
• Nagell–Lutz theorem
• Riemann–Hurwitz formula
• Wiles's proof of Fermat's Last Theorem

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.

• I. Blake; G. Seroussi; N. Smart (2000). Elliptic Curves in Cryptography. LMS Lecture Notes. Cambridge University Press. ISBN 0-521-65374-6.
• Brown, Ezra (2000), "Three Fermat Trails to Elliptic Curves", The College Mathematics Journal, 31 (3): 162–172, doi:10.1080/07468342.2000.11974137, S2CID 5591395, winner of the MAA writing prize the George Pólya Award
• Richard Crandall; Carl Pomerance (2001). "Chapter 7: Elliptic Curve Arithmetic". Prime Numbers: A Computational Perspective (1st ed.). Springer-Verlag. pp. 285–352. ISBN 0-387-94777-9.
• Cremona, John (1997). Algorithms for Modular Elliptic Curves (2nd ed.). Cambridge University Press. ISBN 0-521-59820-6.
• Darrel Hankerson, Alfred Menezes and Scott Vanstone (2004). Guide to Elliptic Curve Cryptography. Springer. ISBN 0-387-95273-X.
• Hardy, G. H.; Wright, E. M. (2008) [1938]. An Introduction to the Theory of Numbers. Revised by D. R. Heath-Brown and J. H. Silverman. Foreword by Andrew Wiles. (6th ed.). Oxford: Oxford University Press. ISBN 978-0-19-921986-5. MR 2445243. Zbl 1159.11001. Chapter XXV
• Hellegouarch, Yves (2001). Invitation aux mathématiques de Fermat-Wiles. Paris: Dunod. ISBN 978-2-10-005508-1.
• Husemöller, Dale (2004). Elliptic Curves. Graduate Texts in Mathematics. Vol. 111 (2nd ed.). Springer. ISBN 0-387-95490-2.
• Kenneth Ireland; Michael I. Rosen (1998). "Chapters 18 and 19". A Classical Introduction to Modern Number Theory. Graduate Texts in Mathematics. Vol. 84 (2nd revised ed.). Springer. ISBN 0-387-97329-X.
• Knapp, Anthony W. (2018) [1992]. Elliptic Curves. Mathematical Notes. Vol. 40. Princeton University Press. ISBN 9780691186900.
• Koblitz, Neal (1993). Introduction to Elliptic Curves and Modular Forms. Graduate Texts in Mathematics. Vol. 97 (2nd ed.). Springer-Verlag. ISBN 0-387-97966-2.
• Koblitz, Neal (1994). "Chapter 6". A Course in Number Theory and Cryptography. Graduate Texts in Mathematics. Vol. 114 (2nd ed.). Springer-Verlag. ISBN 0-387-94293-9.
• Serge Lang (1978). Elliptic curves: Diophantine analysis. Grundlehren der mathematischen Wissenschaften. Vol. 231. Springer-Verlag. ISBN 3-540-08489-4.
• Henry McKean; Victor Moll (1999). Elliptic curves: function theory, geometry and arithmetic. Cambridge University Press. ISBN 0-521-65817-9.
• Ivan Niven; Herbert S. Zuckerman; Hugh Montgomery (1991). "Section 5.7". An introduction to the theory of numbers (5th ed.). John Wiley. ISBN 0-471-54600-3.
• Silverman, Joseph H. (1986). The Arithmetic of Elliptic Curves. Graduate Texts in Mathematics. Vol. 106. Springer-Verlag. ISBN 0-387-96203-4.
• Joseph H. Silverman (1994). Advanced Topics in the Arithmetic of Elliptic Curves. Graduate Texts in Mathematics. Vol. 151. Springer-Verlag. ISBN 0-387-94328-5.
• Joseph H. Silverman; John Tate (1992). Rational Points on Elliptic Curves. Springer-Verlag. ISBN 0-387-97825-9.
• John Tate (1974). "The arithmetic of elliptic curves". Inventiones Mathematicae. 23 (3–4): 179–206. Bibcode:1974InMat..23..179T. doi:10.1007/BF01389745. S2CID 120008651.
• Lawrence Washington (2003). Elliptic Curves: Number Theory and Cryptography. Chapman & Hall/CRC. ISBN 1-58488-365-0.

Wikimedia Commons has media related to Elliptic curve.

Wikiquote has quotations related to Elliptic curve.

• LMFDB: Database of Elliptic Curves over Q
• "Elliptic curve", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Weisstein, Eric W. "Elliptic Curves". MathWorld.
• The Arithmetic of elliptic curves from PlanetMath
• Interactive elliptic curve over R and over Zp – web application that requires HTML5 capable browser.

This article incorporates material from Isogeny on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.