Number Theory
Elliptic Curves
Цели урока
- Understand the Weierstrass equation and the geometric group law on elliptic curves
- Know the Hasse bound and point counting over finite fields
- Distinguish generic, CM, and supersingular curves by endomorphism ring
- Apply Nagell-Lutz and Mazur's theorem to classify rational torsion
Предварительные знания
- Previous number theory lesson
- Basic algebraic geometry
- Finite fields
How can a cubic equation over Q hide both infinite families of rational solutions (rank) and deep connections to complex analysis (L-functions)?
- Bitcoin: secp256k1 curve secures over 500 billion USD in daily transactions via ECDSA
- Post-quantum cryptography: supersingular isogeny protocols (SIDH) use curves with a_p = 0
- Integer factorization: Lenstra's ECM algorithm finds factors using random curves over Z/nZ
- Primality proving: ECPP algorithm certifies primality of large numbers via CM theory
From Fermat to the crypto backbone of the internet
Pierre de Fermat in the 1600s studied the equation y^2 = x^3 - 2 and found the point (3,5). He could not prove it was the only rational solution. Mordell in 1922 proved E(Q) is finitely generated. Mazur in 1977 classified all possible torsion subgroups. Victor Miller and Neal Koblitz independently proposed elliptic curve cryptography in 1985. Today, every HTTPS connection to a major website uses elliptic curves - the same mathematical objects that puzzled Fermat.
Definition and Group Law
Elliptic curves form the backbone of Bitcoin's cryptography: the ECDSA protocol on curve secp256k1 secures transactions worth over 500 billion USD. The curve E: y^2 = x^3 + ax + b over a field F defines an abelian group where points are added geometrically via chords and tangents.
The group law on an elliptic curve is associative - not obvious from the geometric definition. The proof uses the Riemann-Roch theorem on the algebraic curve. This is why the geometric chord-tangent construction actually defines a group.
What does the condition Delta = -16(4a^3 + 27b^2) is nonzero guarantee for an elliptic curve?
Delta is nonzero means the cubic x^3 + ax + b has no repeated roots, which means no singular points on the curve. On a smooth curve, the geometric group law is well defined everywhere.
Curves over Finite Fields and the Hasse Bound
Elliptic curves over finite fields F_p are the setting for cryptographic applications. The order #E(F_p) is close to p+1, with the deviation bounded by the Hasse theorem. This bound is sharp and reflects deep geometry: it follows from the Riemann hypothesis for curves over finite fields.
For cryptography, one needs curves where #E(F_p) is nearly prime (or has a large prime factor). The NIST curves (P-256, P-384) were selected to have prime group order, verified by Schoof's algorithm.
Schoof's algorithm and point counting
Polynomial-time counting
Naive counting of #E(F_p) takes O(p) steps. Schoof's algorithm (1985) reduces this to O(log^8 p) using the Chinese Remainder Theorem and action of Frobenius on torsion points. For 256-bit primes used in Bitcoin, naive counting would take longer than the universe's age; Schoof completes in milliseconds.
For curve E over F_p with trace a_p, what are the roots of the characteristic polynomial 1 - a_p T + p T^2?
The characteristic polynomial 1 - a_p T + pT^2 has roots alpha and alpha-bar with |alpha| = |alpha-bar| = sqrt(p). This determines #E(F_{p^n}) = p^n+1 - (alpha^n + alpha-bar^n) for all n.
Endomorphisms and Complex Multiplication
An endomorphism of an elliptic curve E is a morphism from E to itself preserving the group structure. Over C, the endomorphism ring End(E) is usually Z (multiplication-by-n maps). But some curves have extra endomorphisms - complex multiplication (CM). These curves are special and computationally significant.
| Type | End(E) over C | Trace a_p | Crypto use |
|---|---|---|---|
| Generic | Z | Generic |a_p| <= 2sqrt(p) | Standard ECDH |
| CM by K | Order in K | Determined by K | Efficient arithmetic |
| Supersingular | Quaternion order | a_p = 0 | Post-quantum (isogenies) |
CM curves are computationally efficient but have special structure that can sometimes be exploited. The MOV attack uses the Weil pairing to reduce ECDLP to a discrete log in F_{p^k} for some k, which can be small for CM curves.
What characterizes a supersingular elliptic curve over F_p?
Supersingular: a_p = 0, so #E(F_p) = p+1. The endomorphism ring over F_p-bar is a maximal order in the quaternion algebra ramified at p and infinity. Used in SIDH and other isogeny-based protocols.
Rational Torsion and the Nagell-Lutz Theorem
Over Q, rational torsion points of an elliptic curve are rare and structured. The Nagell-Lutz theorem gives a practical test for finding all torsion points, and Mazur's theorem gives the complete classification.
What does the Nagell-Lutz theorem state about torsion points P = (x,y) on E/Q?
Nagell-Lutz: for P = (x,y) torsion on a minimal model, x, y are integers with y = 0 or y^2 | Delta. This reduces finding torsion to checking finitely many pairs.
Connections to other topics
Elliptic curves sit at the intersection of algebraic geometry, number theory, and cryptography.
- Algebraic geometry — Related topic
- Complex analysis — Related topic
- Representation theory — Related topic
Итоги
- E: y^2 = x^3 + ax + b, smooth when Delta = -16(4a^3+27b^2) is nonzero
- Group law: P+Q via chord (distinct points) or tangent (doubling); identity is the point at infinity
- Hasse bound: |a_p| is at most 2sqrt(p), where a_p = p+1 - #E(F_p)
- CM curves have End(E) containing an imaginary quadratic field; supersingular have a_p = 0
- Mazur's theorem: E(Q)_tors is one of exactly 15 groups
Вопросы для размышления
- Why does the group law defined geometrically (chord-tangent construction) automatically satisfy associativity, without checking it algebraically?
- How does the Hasse bound for elliptic curves relate to the Riemann hypothesis for the curve's zeta function over F_p?
- Why does having CM make an elliptic curve both more computationally tractable and potentially more vulnerable in cryptographic applications?