Before we can understand the elegant machinery that secures Bitcoin, we must first build a foundation in abstract algebra. The concepts introduced in this chapter—sets, operations, and groups—may seem far removed from cryptocurrency, yet they form the very bedrock upon which all cryptographic security rests.
We shall proceed methodically, defining each concept with precision and illuminating it with examples both familiar and novel. By the chapter's end, the reader will possess the vocabulary necessary to speak of elliptic curves with mathematical rigor.
1.1 Sets and Binary Operations
We begin, as mathematicians often do, with the notion of a set—a collection of distinct objects, considered as a single entity.
Definition 1.1 (Set)
A set is a well-defined collection of distinct objects. The objects within a set are called its elements or members. We write a ∈ S to denote that a is an element of the set S.
Example 1.1
The following are sets:
- ℤ = {..., -2, -1, 0, 1, 2, ...}, the integers
- ℕ = {0, 1, 2, 3, ...}, the natural numbers
- ℝ, the real numbers
- {0, 1}, the binary digits
- ℤ₇ = {0, 1, 2, 3, 4, 5, 6}, integers modulo 7
With sets in hand, we now consider how elements within a set may interact. A binary operation provides a rule for combining two elements to produce a third.
Definition 1.2 (Binary Operation)
A binary operation on a set S is a function ∗ : S × S → S that assigns to each ordered pair (a, b) of elements from S a unique element a ∗ b in S.
The requirement that a ∗ b ∈ S for all a, b ∈ S is called closure. It ensures that the operation never produces a result outside our set—a property that will prove essential in cryptography.
Example 1.2
Standard binary operations include:
- Addition + on ℤ: closed, since the sum of two integers is an integer
- Multiplication × on ℤ: closed
- Subtraction − on ℕ: not closed, since 2 − 5 = −3 ∉ ℕ
- Division ÷ on ℤ: not closed, since 1 ÷ 2 = 0.5 ∉ ℤ
1.2 The Group Axioms
We now arrive at one of the most fundamental structures in all of mathematics: the group. A group is a set equipped with a binary operation satisfying four elegant axioms.
Definition 1.3 (Group)
A group is a pair (G, ∗) consisting of a set G and a binary operation ∗ satisfying:
- Closure: For all a, b ∈ G, a ∗ b ∈ G.
- Associativity: For all a, b, c ∈ G, (a ∗ b) ∗ c = a ∗ (b ∗ c).
- Identity: There exists an element e ∈ G such that for all a ∈ G, e ∗ a = a ∗ e = a.
- Inverse: For each a ∈ G, there exists an element a⁻¹ ∈ G such that a ∗ a⁻¹ = a⁻¹ ∗ a = e.
Example 1.3 (The Integers under Addition)
Consider (ℤ, +). We verify the axioms:
- Closure: The sum of two integers is always an integer. ✓
- Associativity: (a + b) + c = a + (b + c) for all integers. ✓
- Identity: The number 0 satisfies 0 + a = a + 0 = a. ✓
- Inverse: For any integer a, its inverse is −a, since a + (−a) = 0. ✓
Thus (ℤ, +) is a group.
Example 1.4 (The Integers under Multiplication)
Is (ℤ, ×) a group? Let us check:
- Closure: Yes, the product of integers is an integer. ✓
- Associativity: Yes, multiplication is associative. ✓
- Identity: The number 1 satisfies 1 × a = a. ✓
- Inverse: What is the inverse of 2? We need 2 × x = 1, which gives x = ½. But ½ ∉ ℤ. ✗
Therefore (ℤ, ×) is not a group.
Remark.
The failure of the integers under multiplication to form a group hints at why cryptographers favor working in finite fields, where every nonzero element has a multiplicative inverse.
1.3 Abelian Groups
Some groups possess an additional property that simplifies many calculations: their operation is commutative.
Definition 1.4 (Abelian Group)
A group (G, ∗) is called abelian (or commutative) if for all a, b ∈ G:
a ∗ b = b ∗ a
The term honors Niels Henrik Abel (1802–1829), the Norwegian mathematician who made profound contributions to group theory before his untimely death at age 26.
Example 1.5
- (ℤ, +) is abelian, since a + b = b + a for all integers.
- (ℝ \ {0}, ×) is abelian, since a × b = b × a.
- Matrix multiplication is not commutative in general, so the group of invertible n × n matrices (for n > 1) is not abelian.
Why does commutativity matter for cryptography? When we study elliptic curves, we shall see that the points on such a curve form an abelian group. This structure allows us to add points in any order—a fact exploited by every Bitcoin transaction.
1.4 Cyclic Groups and Generators
Among all groups, there is a particularly simple yet powerful class: cyclic groups. These groups are generated by a single element, much like a clock face is generated by repeatedly adding one hour.
Definition 1.5 (Order of a Group)
The order of a group G, denoted |G|, is the number of elements in G. If G has infinitely many elements, we say it has infinite order.
Definition 1.6 (Cyclic Group)
A group G is called cyclic if there exists an element g ∈ G such that every element of G can be expressed as gⁿ for some integer n. Such an element g is called a generator of G.
We write G = ⟨g⟩ to denote that g generates G.
Notation.
When the group operation is written additively (as +), we write ng instead of gⁿ, meaning g + g + ⋯ + g (n times).
Example 1.6 (The Clock Group)
Consider ℤ₁₂ = {0, 1, 2, ..., 11} with addition modulo 12. This is the "clock arithmetic" familiar from daily life.
The element 1 is a generator:
- 1 × 1 = 1
- 1 × 2 = 1 + 1 = 2
- 1 × 3 = 1 + 1 + 1 = 3
- ⋮
- 1 × 12 = 12 ≡ 0 (mod 12)
Thus ⟨1⟩ = ℤ₁₂. Note that 5 is also a generator (verify this!), but 2 is not, since ⟨2⟩ = {0, 2, 4, 6, 8, 10}.
Theorem 1.1 (Structure of Cyclic Groups)
Let G = ⟨g⟩ be a cyclic group of order n. Then:
- G is abelian.
- G is isomorphic to ℤₙ.
- An element gᵏ is a generator of G if and only if gcd(k, n) = 1.
(1) For any gᵃ, gᵇ ∈ G, we have gᵃ ∗ gᵇ = gᵃ⁺ᵇ = gᵇ⁺ᵃ = gᵇ ∗ gᵃ.
(2) The map φ: ℤₙ → G defined by φ(k) = gᵏ is a bijection preserving the group operation.
(3) The proof involves the Euclidean algorithm and is left as an exercise.
1.5 Subgroups
Within any group, there may lurk smaller groups hiding in plain sight. These subgroups inherit the group structure from their parent.
Definition 1.7 (Subgroup)
Let (G, ∗) be a group. A subset H ⊆ G is a subgroup of G if (H, ∗) is itself a group under the same operation. We write H ≤ G.
Proposition 1.2 (Subgroup Test)
A nonempty subset H of a group G is a subgroup if and only if for all a, b ∈ H:
a ∗ b⁻¹ ∈ H
Example 1.7
In the group (ℤ, +):
- The even integers 2ℤ = {..., -4, -2, 0, 2, 4, ...} form a subgroup.
- More generally, nℤ = {..., -2n, -n, 0, n, 2n, ...} is a subgroup for any positive integer n.
- The odd integers do not form a subgroup (why not?).
Theorem 1.3 (Lagrange's Theorem)
If H is a subgroup of a finite group G, then |H| divides |G|.
Lagrange's theorem is profound in its simplicity. It tells us that the order of any subgroup must be a divisor of the group order. In the context of elliptic curves, this theorem guarantees that the cofactor (the ratio of curve order to subgroup order) is always an integer—a fact crucial for cryptographic security.
1.6 The Discrete Logarithm Problem
We arrive now at the mathematical linchpin of elliptic curve cryptography. In a cyclic group, raising a generator to a power is easy; finding that power given only the result is believed to be hard.
Definition 1.8 (Discrete Logarithm)
Let G = ⟨g⟩ be a cyclic group of order n, and let h ∈ G. The discrete logarithm of h to base g, denoted log_g(h), is the unique integer k with 0 ≤ k < n such that:
gᵏ = h
Definition 1.9 (Discrete Logarithm Problem)
The Discrete Logarithm Problem (DLP) is the computational problem of finding k given g and h = gᵏ in a cyclic group.
The security of Bitcoin rests on the assumption that the DLP is computationally infeasible in certain carefully chosen groups. While no proof exists that the DLP is truly hard, decades of research have failed to produce an efficient algorithm for the groups used in practice.
Example 1.8 (DLP in Small Groups)
In ℤ₇* (the nonzero integers modulo 7 under multiplication), let g = 3. We can tabulate powers:
| k | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 3ᵏ mod 7 | 3 | 2 | 6 | 4 | 5 | 1 |
If we're told h = 4, we can easily read off k = 4. But in a group with 2²⁵⁶ elements, such tabulation is impossible.
Cryptographic Security.
The best known algorithms for the general DLP have complexity O(√n), where n is the group order. For Bitcoin's secp256k1 curve with n ≈ 2²⁵⁶, this gives approximately 2¹²⁸ operations—well beyond any foreseeable computational capability.