MathLabs

Arithmetic and number theory

Elliptic curves

Smooth cubic curves y2=x3+ax+by^2=x^3+ax+b whose points form an abelian group under a geometric chord-and-tangent law, linking classical Diophantine geometry to modular forms, elliptic-curve cryptography, and the unsolved Birch and Swinnerton-Dyer conjecture.

IntuitionA curve that turns points into a group

Take a smooth cubic curve E:y2=x3+ax+bE: y^2 = x^3 + ax + b — a shape that looks like a lazy S-curve, or (depending on a,ba,b) a single wavy branch plus a separate oval loop. Pick any two points PP and QQ on the curve. A remarkable fact of algebra guarantees that the straight line through PP and QQ always meets the curve at exactly one more point (counting multiplicity), because substituting the line's equation into the cubic leaves a degree-33 polynomial, and two of its three roots are already pinned down by PP and QQ. Call that third point RR. Now reflect RR across the xx-axis: the mirror image −R-R is defined to be the sum P+QP + Q. This purely geometric recipe — draw a chord, find the third point, flip it over — turns the points on the curve into a commutative group, with the point at infinity O\mathcal{O} (where every vertical line meets the curve) playing the role of the identity element 00.

Example: Adding two rational points by hand

On the curve E:y2=x3−36xE: y^2 = x^3 - 36x, check that P=(−3,9)P = (-3, 9) and Q=(−2,8)Q = (-2, 8) are both rational points, then use the chord construction to compute P+QP + Q.

Solution

First, (−3)3−36(−3)=−27+108=81=92(-3)^3 - 36(-3) = -27 + 108 = 81 = 9^2 and (−2)3−36(−2)=−8+72=64=82(-2)^3-36(-2) = -8+72 = 64 = 8^2, so both points lie on EE (this is the n=6n=6 congruent number curve, linked to the 33-44-55 right triangle of area 66). The chord through PP and QQ has slope λ=8−9−2−(−3)=−11=−1\lambda = \frac{8-9}{-2-(-3)} = \frac{-1}{1} = -1. The third intersection point has xx-coordinate x3=λ2−xP−xQ=1−(−3)−(−2)=6x_3 = \lambda^2 - x_P - x_Q = 1 - (-3) - (-2) = 6 and yy-coordinate y3=λ(xP−x3)−yP=(−1)(−3−6)−9=9−9=0y_3 = \lambda(x_P - x_3) - y_P = (-1)(-3-6) - 9 = 9 - 9 = 0. So the line meets EE again at (6,0)(6,0) — and since this point already sits on the xx-axis, its own reflection is itself, giving P+Q=(6,0)P + Q = (6, 0). As a sanity check, 63−36×6=216−216=0=026^3 - 36\times 6 = 216 - 216 = 0 = 0^2, confirming (6,0)∈E(6,0) \in E.

A 2D graph of the cubic function $y = x^3 - x + 1$: a single S-shaped curve rising from lower left to upper right, with a local maximum near $x=-0.6$ and a local minimum near $x=0.6$, crossing the $x$-axis once near $x \approx -1.32$.
This graph shows only the cubic polynomial y=x3−x+1y = x^3 - x + 1 on the right-hand side of the Weierstrass equation y2=x3−x+1y^2 = x^3 - x + 1 — not the elliptic curve itself. Because this cubic has one real root and no repeated roots, the actual curve y2=x3−x+1y^2 = x^3-x+1 has a single unbounded wavy branch (no separate oval), and it is nonsingular.

UndergraduateWeierstrass form, the discriminant, and nonsingularity

Definition: Elliptic curve (short Weierstrass form)

Over a field of characteristic ≠2,3\neq 2, 3 (such as Q\mathbb{Q}, R\mathbb{R}, or a finite field Fp\mathbb{F}_p with p>3p > 3), every smooth plane cubic curve with a rational point can be put in short Weierstrass form E:y2=x3+ax+bE: y^2 = x^3 + ax + b for some constants a,ba, b in the field. An elliptic curve is such a curve together with the extra point at infinity O\mathcal{O}, required to be nonsingular: no point of the curve may have both partial derivatives of F(x,y)=y2−x3−ax−bF(x,y) = y^2 - x^3 - ax - b vanish simultaneously (a singular point would be a self-crossing node or a sharp cusp, where the chord-and-tangent recipe breaks down).

Δ=−16(4a3+27b2)\Delta = -16(4a^3 + 27b^2)

The curve E:y2=x3+ax+bE: y^2 = x^3+ax+b is nonsingular if and only if the discriminant Δ=−16(4a3+27b2)\Delta = -16(4a^3+27b^2) is nonzero, which happens if and only if the cubic x3+ax+bx^3+ax+b has three distinct roots (over an algebraic closure).

Why is it true?

A point (x0,0)(x_0, 0) where the cubic has a repeated root is exactly where the curve pinches into a cusp or crosses itself, because the tangent direction becomes undefined there — precisely the geometric flaw that would break the chord-and-tangent group law.

Proof

The point (x0,y0)(x_0,y_0) is singular iff F=y2−x3−ax−b=0F=y^2-x^3-ax-b=0, ∂F/∂y=2y0=0\partial F/\partial y = 2y_0 = 0, and ∂F/∂x=−3x02−a=0\partial F/\partial x = -3x_0^2-a=0 all hold. The second equation forces y0=0y_0=0, so x0x_0 must be a root of x3+ax+bx^3+ax+b; the third equation forces 3x02+a=03x_0^2+a=0, i.e. x0x_0 is also a root of the derivative 3x2+a3x^2+a. A polynomial and its derivative share a common root exactly at a repeated root of the polynomial, so EE is singular iff x3+ax+bx^3+ax+b has a repeated root. The classical discriminant of the depressed cubic x3+ax+bx^3+ax+b is −4a3−27b2-4a^3-27b^2, which vanishes exactly when the cubic has a repeated root; multiplying by the normalization constant −16-16 gives Δ=−16(4a3+27b2)\Delta = -16(4a^3+27b^2), so EE is nonsingular iff Δ≠0\Delta \neq 0.

The geometric chord-and-tangent recipe translates into explicit algebra. For distinct points P=(x1,y1)P=(x_1,y_1), Q=(x2,y2)Q=(x_2,y_2) with x1≠x2x_1 \neq x_2, the chord has slope λ=y2−y1x2−x1\lambda = \frac{y_2-y_1}{x_2-x_1}; for doubling a point P=(x1,y1)P=(x_1,y_1) with y1≠0y_1 \neq 0, the tangent line at PP has slope λ=3x12+a2y1\lambda = \frac{3x_1^2+a}{2y_1} (found by implicit differentiation of y2=x3+ax+by^2=x^3+ax+b). In both cases, the sum's coordinates are given by the same two formulas below. If P=(x1,y1)P=(x_1,y_1) and −P=(x1,−y1)-P=(x_1,-y_1) are added, the vertical line through them meets EE only at O\mathcal{O}, so P+(−P)=OP+(-P)=\mathcal{O}, matching the identity axiom of a group.

x3=λ2−x1−x2,y3=λ(x1−x3)−y1,P+Q:=(x3,−y3)x_3 = \lambda^2 - x_1 - x_2, \qquad y_3 = \lambda(x_1-x_3) - y_1, \qquad P+Q := (x_3, -y_3)

Since Fp\mathbb{F}_p has characteristic ≠2,3\neq 2,3 for p>3p>3, the same addition and doubling formulas apply verbatim when EE is reduced modulo a prime pp, giving the reduced curve E(Fp)={(x,y)∈Fp2:y2=x3+ax+b}∪{O}E(\mathbb{F}_p) = \{(x,y) \in \mathbb{F}_p^2 : y^2=x^3+ax+b\} \cup \{\mathcal{O}\} the structure of a finite abelian group. This is the setting used throughout elliptic-curve cryptography, and it raises an obvious question: how large is #E(Fp)\#E(\mathbb{F}_p)?

Theorem: Hasse's bound

For an elliptic curve EE over a finite field Fp\mathbb{F}_p (pp prime), the number of points satisfies ∣#E(Fp)−(p+1)∣≤2p|\#E(\mathbb{F}_p) - (p+1)| \le 2\sqrt{p}.

Why is it true?

The quantity ap:=p+1−#E(Fp)a_p := p+1-\#E(\mathbb{F}_p) measures the 'error term' of the naive guess that a random cubic should have about pp solutions plus the point at infinity; Hasse's bound says this error can never be more than about 2p2\sqrt{p}, an astonishingly small deviation compared to the trivial bound of size pp, and it is what makes #E(Fp)\#E(\mathbb{F}_p) usable as a reliable, predictable group order in cryptographic constructions.

Proof

Consider the Frobenius endomorphism φ:E(Fp‾)→E(Fp‾)\varphi: E(\overline{\mathbb{F}_p}) \to E(\overline{\mathbb{F}_p}), φ(x,y)=(xp,yp)\varphi(x,y) = (x^p, y^p). Its fixed points are exactly E(Fp)E(\mathbb{F}_p), and one shows #E(Fp)=deg⁡(φ−1)=p+1−t\#E(\mathbb{F}_p) = \deg(\varphi - 1) = p+1-t where t=φ+φ^t = \varphi + \hat\varphi is the trace of Frobenius acting on the endomorphism ring. The degree map on endomorphisms of EE is a positive-definite integer-valued quadratic form (it satisfies deg⁡(mφ+n)≥0\deg(m\varphi+n) \ge 0 for all integers m,nm,n, with equality only when mφ+n=0m\varphi+n=0), and deg⁡φ=p\deg\varphi = p. Expanding deg⁡(mφ+n)=m2p+mnt+n2≥0\deg(m\varphi+n) = m^2 p + mnt + n^2 \ge 0 as a quadratic form in m,nm,n forces its discriminant to be non-positive: t2−4p≤0t^2 - 4p \le 0, i.e. ∣t∣≤2p|t|\le 2\sqrt p. Since #E(Fp)−(p+1)=−t\#E(\mathbb{F}_p) - (p+1) = -t, this is exactly the claimed bound.

ap:=p+1−#E(Fp),∣ap∣≤2pa_p := p + 1 - \#E(\mathbb{F}_p), \qquad |a_p| \le 2\sqrt{p}
A circle with $17$ evenly spaced points labeled $0$ through $16$, connected by straight chords linking each point $x$ to the point $3x \bmod 17$, forming a star-like pattern of intersecting line segments.
This widget is not a picture of an elliptic curve; it shows the ambient modular arithmetic mod 1717 in which point coordinates of E(F17)E(\mathbb{F}_{17}) live, drawing 1717 points on a circle and chords for the map x↦3x mod 17x \mapsto 3x \bmod 17. Every xx- and yy-coordinate of a point on E(F17)E(\mathbb{F}_{17}) is one of these 1717 residues.

Example: Counting points on a curve over a small finite field

Let E:y2=x3+x+1E: y^2 = x^3+x+1 over F5\mathbb{F}_5. Compute #E(F5)\#E(\mathbb{F}_5) by direct enumeration and check it satisfies Hasse's bound.

Solution

For each x∈{0,1,2,3,4}x \in \{0,1,2,3,4\}, compute x3+x+1 mod 5x^3+x+1 \bmod 5 and check whether it is a square mod 55 (the squares mod 55 are {0,1,4}\{0,1,4\}, since 02=0,12=1,22=4,32=4,42=10^2=0,1^2=1,2^2=4,3^2=4,4^2=1): x=0⇒1x=0 \Rightarrow 1 (square, y=±1y=\pm 1, 22 points); x=1⇒3x=1 \Rightarrow 3 (not a square, 00 points); x=2⇒11≡1x=2 \Rightarrow 11\equiv 1 (square, y=±1y=\pm 1, 22 points); x=3⇒31≡1x=3 \Rightarrow 31\equiv 1 (square, y=±1y=\pm 1, 22 points); x=4⇒69≡4x=4 \Rightarrow 69\equiv 4 (square, y=±2y=\pm 2, 22 points). This gives 2+0+2+2+2=82+0+2+2+2=8 affine points, plus the point at infinity, so #E(F5)=9\#E(\mathbb{F}_5) = 9. Checking Hasse's bound: ∣9−(5+1)∣=∣9−6∣=3|9-(5+1)| = |9-6| = 3, and 25≈4.472\sqrt{5}\approx 4.47, so 3≤4.473 \le 4.47 holds.

AdvancedRank, torsion, and the shape of E(Q)E(\mathbb{Q})

Over Q\mathbb{Q} the group E(Q)E(\mathbb{Q}) is infinite whenever it contains a point of infinite order, and Henri Poincaré's 1901 paper first asked how many rational points are needed to generate all the others by chords and tangents. Louis Mordell answered this in 1922 using a refinement of Fermat's method of infinite descent, and André Weil generalized the result in his 1929 thesis to abelian varieties over arbitrary number fields.

For an elliptic curve EE over Q\mathbb{Q}, the group of rational points E(Q)E(\mathbb{Q}) is finitely generated: E(Q)≅Zr⊕E(Q)torsE(\mathbb{Q}) \cong \mathbb{Z}^r \oplus E(\mathbb{Q})_{\mathrm{tors}} for some integer r≥0r \ge 0 called the rank, where E(Q)torsE(\mathbb{Q})_{\mathrm{tors}} is a finite abelian group.

Why is it true?

This theorem is the arithmetic payoff of the group law: it says that however intricate the set of rational points looks, it is always controlled by finitely many 'seed' points — a finite generating set — from which every other rational point is reached by repeated chord-and-tangent addition.

Proof

The proof combines two ingredients. Weak Mordell–Weil: one shows E(Q)/2E(Q)E(\mathbb{Q})/2E(\mathbb{Q}) is a finite group, by embedding it (via Galois cohomology, using the 22-descent map P↦(x(P)−e1,x(P)−e2,x(P)−e3)P \mapsto (x(P)-e_1, x(P)-e_2, x(P)-e_3) for the roots eie_i of the cubic) into a group built from the class group and unit group of a related number field, both of which are known to be finite. Height descent: one attaches to each point a canonical height h^(P)≥0\hat h(P) \ge 0, a real-valued measure of arithmetic complexity satisfying h^(2P)=4h^(P)\hat h(2P) = 4\hat h(P) and for which only finitely many points have height below any given bound. Combining a finite set of coset representatives for E(Q)/2E(Q)E(\mathbb{Q})/2E(\mathbb{Q}) with the fact that repeatedly halving the height of any point (via the parallelogram law for heights) eventually lands in a bounded-height region shows every point is a Z\mathbb{Z}-combination of the finitely many representatives and finitely many bounded-height points — hence E(Q)E(\mathbb{Q}) is finitely generated.

For an elliptic curve EE over Q\mathbb{Q}, the torsion subgroup E(Q)torsE(\mathbb{Q})_{\mathrm{tors}} is isomorphic to exactly one of the following 1515 groups: the cyclic group Z/NZ\mathbb{Z}/N\mathbb{Z} for N=1,…,10N=1,\dots,10 or N=12N=12, or the group Z/2Z⊕Z/2NZ\mathbb{Z}/2\mathbb{Z}\oplus\mathbb{Z}/2N\mathbb{Z} for N=1,2,3,4N=1,2,3,4; no other finite abelian group occurs.

Why is it true?

This is a striking rigidity statement: among infinitely many abstractly possible finite abelian groups, only these 1515 ever occur as the torsion of a rational elliptic curve — a torsion subgroup of order, say, 1111 or 1616 is simply impossible.

Proof

Mazur's 1977 proof translates the existence of a rational point of exact order NN on EE into the existence of a non-cuspidal rational point on the modular curve X1(N)X_1(N), which classifies pairs (E,P)(E, P) with PP of order NN. The strategy studies the Jacobian J0(N)J_0(N) of the related modular curve X0(N)X_0(N) and the Eisenstein ideal I\mathcal{I} — the ideal in the Hecke algebra generated by Tℓ−ℓ−1T_\ell - \ell - 1 for primes ℓ∤N\ell \nmid N — acting on it. By analyzing the Eisenstein quotient of J0(N)J_0(N) and its reduction modulo auxiliary primes, Mazur shows that for NN outside the allowed list, X1(N)(Q)X_1(N)(\mathbb{Q}) consists only of cusps, so no elliptic curve over Q\mathbb{Q} can have a rational point of that exact order; explicit constructions (for instance using the curves y2=x3+axy^2=x^3+ax and y2=x3+by^2=x^3+b) exhibit examples realizing each of the 1515 permitted groups.

Definition: The jj-invariant

For E:y2=x3+ax+bE: y^2=x^3+ax+b, the **jj-invariant** is j(E)=1728⋅4a34a3+27b2j(E) = 1728\cdot\frac{4a^3}{4a^3+27b^2}. Two elliptic curves over an algebraically closed field are isomorphic if and only if they have the same jj-invariant, so j(E)j(E) is the complete classifying invariant of the curve's shape, independent of which Weierstrass equation is used to present it (curves sharing a jj-invariant over Q\mathbb{Q} but not isomorphic over Q\mathbb{Q} are called twists of one another).

Because arithmetic in E(Fp)E(\mathbb{F}_p) is fast to compute forward but (for well-chosen curves) extremely slow to invert, elliptic curves underpin much of today's public-key cryptography. Fix a public base point P∈E(Fp)P \in E(\mathbb{F}_p); computing kPkP (adding PP to itself kk times, done efficiently by repeated doubling) is easy, but recovering the secret integer kk from PP and Q=kPQ=kP alone — the Elliptic Curve Discrete Logarithm Problem (ECDLP) — is believed to require roughly p\sqrt{p} operations for the best known classical algorithms, with no faster method known. This lets protocols like ECDSA and ECDH use much shorter keys than RSA for the same security level.

Example: A toy discrete logarithm computation

On E:y2=x3+2x+2E: y^2=x^3+2x+2 over F17\mathbb{F}_{17}, verify that P=(5,1)P=(5,1) lies on EE, then compute 2P2P using the doubling formula, illustrating (at a toy scale) the arithmetic behind the Elliptic Curve Discrete Logarithm Problem.

Solution

First, 53+2(5)+2=125+10+2=137≡1(mod17)5^3+2(5)+2 = 125+10+2=137 \equiv 1 \pmod{17}, and 12=11^2=1, so P=(5,1)∈EP=(5,1) \in E. To double PP, the tangent slope is λ=3(5)2+22(1)=772≡92(mod17)\lambda = \frac{3(5)^2+2}{2(1)} = \frac{77}{2} \equiv \frac{9}{2} \pmod{17}; since 2×9=18≡12\times 9=18\equiv 1, the inverse of 22 mod 1717 is 99, so λ≡9×9=81≡13(mod17)\lambda \equiv 9\times 9 = 81 \equiv 13 \pmod{17}. Then x3=λ2−2x1≡132−10=169−10=159≡6(mod17)x_3 = \lambda^2-2x_1 \equiv 13^2-10 = 169-10=159\equiv 6 \pmod{17}, and y3=λ(x1−x3)−y1≡13(5−6)−1=−14≡3(mod17)y_3 = \lambda(x_1-x_3)-y_1 \equiv 13(5-6)-1=-14\equiv 3\pmod{17}, so 2P=(x3,−y3)=(6,−3)≡(6,14)(mod17)2P = (x_3,-y_3) = (6, -3) \equiv (6,14)\pmod{17}. Checking: 63+2(6)+2=216+12+2=230≡9(mod17)6^3+2(6)+2 = 216+12+2=230\equiv 9\pmod{17}, and 142=196≡9(mod17)14^2=196\equiv 9\pmod{17} ✓. On this toy curve with only 1717 possible xx-values, an attacker could search every multiple of PP by hand; real ECC uses primes pp with roughly 256256 bits, making the analogous search (≈p≈2128\approx\sqrt{p}\approx 2^{128} steps) utterly infeasible.

AdvancedThe bridge to modular forms and Fermat's Last Theorem

Elliptic curves live in a second world too: that of modular forms, highly symmetric holomorphic functions on the upper half-plane. Attaching to EE its Hasse–Weil LL-function L(E,s)=∏p(1−app−s+p1−2s)−1L(E,s) = \prod_p (1-a_p p^{-s}+p^{1-2s})^{-1} (built from the same ap=p+1−#E(Fp)a_p = p+1-\#E(\mathbb{F}_p) that appears in Hasse's bound), the Modularity Theorem (Taniyama–Shimura–Weil conjecture) asserts that L(E,s)L(E,s) always agrees with the LL-function of a weight-22 modular form. Equivalently, EE is covered by a modular curve X0(N)X_0(N) via a non-constant map defined over Q\mathbb{Q}, where NN is the conductor of EE. This links the purely arithmetic data #E(Fp)\#E(\mathbb{F}_p) for every prime pp to the Fourier coefficients of a single, highly structured function — an extraordinary bridge between two areas of mathematics that look unrelated at first sight. The associated Galois representation on the ℓ\ell-adic Tate module of EE (a construction built from the group-theoretic ideas pioneered by Évariste Galois) is exactly the object whose 'modularity' is being asserted.

Every elliptic curve EE over Q\mathbb{Q} is modular: there is a nonconstant morphism X0(N)→EX_0(N) \to E defined over Q\mathbb{Q}, where NN is the conductor of EE; equivalently, L(E,s)L(E,s) equals the LL-function of a weight-22 newform on Γ0(N)\Gamma_0(N).

Why is it true?

Modularity turns every elliptic curve into a modular form in disguise, transferring the powerful analytic machinery available for modular forms (analytic continuation, functional equations) to elliptic curves, and — crucially for Fermat's Last Theorem — it means a curve that cannot be modular cannot exist.

Proof

Wiles proved modularity for semistable elliptic curves over Q\mathbb{Q} in 1994–95 (with the final step, a numerical criterion for isomorphism between deformation rings and Hecke algebras — the 'R=TR=T theorem' — established jointly with Richard Taylor). The strategy shows that the Galois representation on the ℓ\ell-adic Tate module of EE, and the corresponding representation attached to a candidate modular form, live in the same deformation space; proving the deformation ring RR and the Hecke algebra TT acting on modular forms coincide forces every allowed Galois representation — in particular EE's — to come from a modular form. Since every semistable curve suffices to rule out a counterexample to Fermat's equation (any solution an+bn=cna^n+b^n=c^n would yield a semistable Frey curve y2=x(x−an)(x+bn)y^2=x(x-a^n)(x+b^n) that Kenneth Ribet had shown, via his 1990 proof of ε\varepsilon-conjecture, cannot be modular), this proved Fermat's Last Theorem. The semistability restriction was later removed entirely, extending modularity to all elliptic curves over Q\mathbb{Q}, by Christophe Breuil, Brian Conrad, Fred Diamond, and Richard Taylor in 2001.

ResearchOpen problems: the Birch and Swinnerton-Dyer conjecture and post-quantum cryptography

Which of these Weierstrass equations is singular (i.e. does NOT define an elliptic curve)?

Which statement must hold for every elliptic curve EE over the finite field F101\mathbb{F}_{101}?

By Mazur's torsion classification, which of the following can NOT be the torsion subgroup E(Q)torsE(\mathbb{Q})_{\mathrm{tors}} of an elliptic curve over Q\mathbb{Q}?

The Modularity Theorem, proved for semistable elliptic curves by Wiles (with Taylor) in 1994–95, was the key ingredient in the proof of which classical problem?

References

  1. Joseph H. Silverman (2009). The Arithmetic of Elliptic Curves · DOI:10.1007/978-0-387-09494-6
  2. Andrew Wiles (1995). Modular elliptic curves and Fermat's Last Theorem · DOI:10.2307/2118559
  3. Andrew Wiles / Clay Mathematics Institute (2000). The Birch and Swinnerton-Dyer Conjecture (official Millennium Problem description)
  4. Wouter Castryck, Thomas Decru (2022). An efficient key recovery attack on SIDH