We now arrive at the central mathematical object of this treatise: the elliptic curve. Despite the name, these curves have nothing to do with ellipses. The terminology is historical, arising from 18th-century attempts to compute the arc length of an ellipse, which led to certain integrals that are now called "elliptic integrals."
In this chapter, we study elliptic curves over the real numbers, where we can draw pictures and develop geometric intuition. The visual approach will serve us well when we later move to the more abstract setting of finite fields.
3.1 The Weierstrass Equation
Definition 3.1 (Elliptic Curve)
An elliptic curve over the real numbers is the set of points (x, y) satisfying an equation of the form:
y² = x³ + ax + b
where a, b ∈ ℝ and the curve is non-singular, meaning it has no cusps or self-intersections. This is called the short Weierstrass form.
The condition for non-singularity is that the discriminant is nonzero:
Definition 3.2 (Discriminant)
The discriminant of the curve y² = x³ + ax + b is:
Δ = −16(4a³ + 27b²)
The curve is non-singular if and only if Δ ≠ 0.
Example 3.1 (Bitcoin's Curve: secp256k1)
The curve used in Bitcoin has a = 0 and b = 7:
y² = x³ + 7
The discriminant is Δ = −16(4·0³ + 27·7²) = −16·1323 ≠ 0, so this curve is indeed non-singular.
Observation.
Notice that every elliptic curve is symmetric about the x-axis. If (x, y) is on the curve, then so is (x, −y), since (−y)² = y². This symmetry will be crucial for defining point addition.
3.2 The Point at Infinity
Before defining addition on elliptic curves, we must extend our curve by adding a special point that serves as the identity element.
Definition 3.3 (Point at Infinity)
The point at infinity, denoted 𝒪 (or sometimes ∞), is an abstract point added to every elliptic curve. Geometrically, it can be thought of as the point where all vertical lines meet "at infinity."
The complete elliptic curve is thus:
E = {(x, y) : y² = x³ + ax + b} ∪ {𝒪}
The point at infinity may seem like a mathematical artifice, but it arises naturally when we work in projective coordinates. For now, simply accept it as the identity element for our group operation.
3.3 The Chord-and-Tangent Law: Geometric Point Addition
Here we define the group operation on elliptic curves. The construction is beautifully geometric: it involves only drawing lines and finding intersections.
Definition 3.4 (Point Addition)
Let P and Q be points on an elliptic curve E. Their sum P + Q is defined as follows:
- Identity: P + 𝒪 = 𝒪 + P = P for all points P.
- Inverse: If P = (x, y), then −P = (x, −y), and P + (−P) = 𝒪.
- General addition (P ≠ Q): Draw the line through P and Q. This line intersects E at exactly one more point R. Then P + Q = −R.
- Point doubling (P = Q): Draw the tangent line to E at P. This line intersects E at one more point R. Then P + P = 2P = −R.
The recipe can be summarized in three words: connect, intersect, reflect.
Theorem 3.1 (A Line Meets a Cubic in Three Points)
Any line that is not vertical intersects an elliptic curve in exactly three points (counting multiplicity and the point at infinity).
Consider a line y = mx + c. Substituting into y² = x³ + ax + b:
(mx + c)² = x³ + ax + b
x³ − m²x² + (a − 2mc)x + (b − c²) = 0
This is a cubic in x, which has exactly three roots (counting multiplicity) in any algebraically closed field, and at least one real root.
3.4 The Addition Formulas
While the geometric definition is elegant, computation requires explicit formulas. Let P = (x₁, y₁) and Q = (x₂, y₂) be points on E: y² = x³ + ax + b.
Theorem 3.2 (Point Addition Formulas)
If P ≠ ±Q and neither is 𝒪, then P + Q = (x₃, y₃) where:
λ = (y₂ − y₁) / (x₂ − x₁)
x₃ = λ² − x₁ − x₂
y₃ = λ(x₁ − x₃) − y₁
The line through P and Q has slope λ = (y₂ − y₁)/(x₂ − x₁) and equation y = λ(x − x₁) + y₁.
Substituting into the curve equation:
[λ(x − x₁) + y₁]² = x³ + ax + b
Expanding and using Vieta's formulas, if x₁, x₂, x₃ are the three roots, then x₁ + x₂ + x₃ = λ². Thus x₃ = λ² − x₁ − x₂.
The y-coordinate y₃ follows from the line equation and reflection: y₃ = λ(x₁ − x₃) − y₁.
Theorem 3.3 (Point Doubling Formulas)
If P = (x₁, y₁) with y₁ ≠ 0, then 2P = (x₃, y₃) where:
λ = (3x₁² + a) / (2y₁)
x₃ = λ² − 2x₁
y₃ = λ(x₁ − x₃) − y₁
The tangent slope at P is found by implicit differentiation of y² = x³ + ax + b:
2y(dy/dx) = 3x² + a
λ = dy/dx = (3x² + a)/(2y)
The rest follows as in the addition case.
Example 3.2 (Point Addition on y² = x³ − 7x + 10)
Let P = (1, 2) and Q = (3, 4). First verify these are on the curve:
- P: 2² = 4 and 1³ − 7·1 + 10 = 4. ✓
- Q: 4² = 16 and 3³ − 7·3 + 10 = 27 − 21 + 10 = 16. ✓
Now compute P + Q:
- λ = (4 − 2)/(3 − 1) = 2/2 = 1
- x₃ = 1² − 1 − 3 = −3
- y₃ = 1·(1 − (−3)) − 2 = 4 − 2 = 2
Thus P + Q = (−3, 2).
Verification: 2² = 4 and (−3)³ − 7·(−3) + 10 = −27 + 21 + 10 = 4. ✓
3.5 The Group Structure
We now verify that elliptic curve addition satisfies the group axioms.
Theorem 3.4 (Elliptic Curves Form an Abelian Group)
The set of points on an elliptic curve E, together with point addition, forms an abelian group.
(Sketch)
- Closure: The formulas produce points on the curve (verified algebraically).
- Identity: 𝒪 satisfies P + 𝒪 = P by definition.
- Inverse: −P = (x, −y) satisfies P + (−P) = 𝒪.
- Commutativity: The line through P and Q is the same as through Q and P.
- Associativity: This requires a lengthy algebraic verification or can be proven geometrically using properties of cubic curves.
3.6 Scalar Multiplication
Given a point P and a positive integer n, we define scalar multiplication as repeated addition:
Definition 3.5 (Scalar Multiplication)
nP = P + P + ⋯ + P (n times)
We extend this to all integers by defining 0P = 𝒪 and (−n)P = n(−P).
Scalar multiplication is the fundamental one-way operation in elliptic curve cryptography. Computing nP from n and P can be done efficiently, but finding n given only P and nP is the Elliptic Curve Discrete Logarithm Problem (ECDLP).
Algorithm 3.1 (Double-and-Add)
To compute nP efficiently:
function scalar_multiply(n, P):
if n = 0:
return 𝒪
if n < 0:
return scalar_multiply(-n, -P)
result = 𝒪
addend = P
while n > 0:
if n is odd:
result = result + addend
addend = 2 × addend // point doubling
n = n ÷ 2 // integer division
return result
Example 3.3 (Computing 151P)
The binary representation of 151 is 10010111₂. Using double-and-add:
| Step | n | Binary | Action | Result |
|---|---|---|---|---|
| 0 | 151 | 10010111 | odd: add P | P |
| 1 | 75 | 1001011 | odd: add 2P | P + 2P = 3P |
| 2 | 37 | 100101 | odd: add 4P | 3P + 4P = 7P |
| 3 | 18 | 10010 | even: skip | 7P |
| 4 | 9 | 1001 | odd: add 16P | 7P + 16P = 23P |
| 5 | 4 | 100 | even: skip | 23P |
| 6 | 2 | 10 | even: skip | 23P |
| 7 | 1 | 1 | odd: add 128P | 23P + 128P = 151P |
Total: 7 doublings and 4 additions, instead of 150 additions.
3.7 Why "Elliptic"?
The curious reader may wonder about the name. Elliptic curves are not ellipses. The connection is historical and indirect.
Historical Note.
In the 18th century, mathematicians sought to compute the arc length of an ellipse. This led to integrals of the form:
∫ R(x, √(p(x))) dx
where p(x) is a polynomial of degree 3 or 4, and R is a rational function. These are called elliptic integrals.
The inverse functions of these integrals are called elliptic functions, and these functions satisfy polynomial relations that define what we now call elliptic curves. The name stuck, even though the connection to actual ellipses is rather tenuous.