In the previous chapter, we constructed the abstract framework of groups. Now we enrich this structure by introducing a second operation—multiplication—and demanding that both operations behave well together. This leads us to the concept of a field.
For cryptography, we require fields with only finitely many elements. The arithmetic within these finite fields resembles clock arithmetic, yet possesses remarkable algebraic properties. It is in these finite worlds that elliptic curves shall live.
2.1 Modular Arithmetic: Clock Mathematics
Consider a 12-hour clock. When it shows 10 o'clock and three hours pass, the clock shows 1 o'clock—not 13. The numbers "wrap around" upon reaching 12. This wrapping behavior is the essence of modular arithmetic.
Definition 2.1 (Congruence)
Let n be a positive integer. We say that integers a and b are congruent modulo n, written
a ≡ b (mod n)
if n divides a − b. Equivalently, a and b have the same remainder when divided by n.
Example 2.1
- 17 ≡ 5 (mod 12) since 17 − 5 = 12 is divisible by 12.
- −3 ≡ 4 (mod 7) since −3 − 4 = −7 is divisible by 7.
- 100 ≡ 2 (mod 7) since 100 = 14 × 7 + 2.
Proposition 2.1 (Properties of Congruence)
Congruence modulo n is an equivalence relation:
- Reflexive: a ≡ a (mod n)
- Symmetric: If a ≡ b (mod n), then b ≡ a (mod n)
- Transitive: If a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n)
This equivalence relation partitions the integers into n disjoint residue classes. We typically represent each class by its smallest nonnegative member.
Definition 2.2 (Residue Classes)
The set ℤₙ = {0, 1, 2, ..., n−1} denotes the residue classes modulo n, also called the integers modulo n.
Proposition 2.2 (Modular Arithmetic Operations)
If a ≡ a' (mod n) and b ≡ b' (mod n), then:
- a + b ≡ a' + b' (mod n)
- a − b ≡ a' − b' (mod n)
- a × b ≡ a' × b' (mod n)
This proposition is the engine of modular arithmetic: we may freely replace any number with a congruent one without affecting the final residue. This allows us to keep numbers small throughout long calculations.
2.2 The Ring ℤₙ
With addition and multiplication defined on residue classes, ℤₙ acquires the structure of a ring.
Definition 2.3 (Ring)
A ring is a set R equipped with two binary operations, addition + and multiplication ×, satisfying:
- (R, +) is an abelian group with identity 0.
- Multiplication is associative: (a × b) × c = a × (b × c).
- Multiplication distributes over addition:
a × (b + c) = (a × b) + (a × c)
(a + b) × c = (a × c) + (b × c)
If there exists an element 1 ∈ R with 1 × a = a × 1 = a for all a, the ring is called a ring with unity. If multiplication is commutative, it is a commutative ring.
Example 2.2 (Arithmetic in ℤ₇)
In ℤ₇ = {0, 1, 2, 3, 4, 5, 6}:
| + | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 1 | 2 | 3 | 4 | 5 | 6 | 0 |
| 2 | 2 | 3 | 4 | 5 | 6 | 0 | 1 |
| 3 | 3 | 4 | 5 | 6 | 0 | 1 | 2 |
| 4 | 4 | 5 | 6 | 0 | 1 | 2 | 3 |
| 5 | 5 | 6 | 0 | 1 | 2 | 3 | 4 |
| 6 | 6 | 0 | 1 | 2 | 3 | 4 | 5 |
Observe that 3 + 5 = 8 ≡ 1 (mod 7) and 4 + 4 = 8 ≡ 1 (mod 7).
2.3 Multiplicative Inverses and Fields
A ring becomes a field when every nonzero element has a multiplicative inverse. This is the structure we need for cryptography.
Definition 2.4 (Field)
A field is a commutative ring F with unity 1 ≠ 0 in which every nonzero element a has a multiplicative inverse a⁻¹ satisfying:
a × a⁻¹ = a⁻¹ × a = 1
When does ℤₙ form a field? The answer lies in the structure of n.
Theorem 2.1 (Prime Fields)
ℤₙ is a field if and only if n is prime.
(⇒) Suppose n is not prime. Then n = ab for some 1 < a, b < n. In ℤₙ, we have a × b = n ≡ 0, so a and b are zero divisors. But a field cannot have zero divisors.
(⇐) Suppose n = p is prime. For any a ≠ 0 in ℤₚ, consider the function f: ℤₚ → ℤₚ defined by f(x) = ax. If f(x) = f(y), then ax ≡ ay (mod p), so a(x − y) ≡ 0. Since p is prime and doesn't divide a, it must divide x − y, giving x = y. Thus f is injective, hence bijective. In particular, there exists b with f(b) = 1, meaning ab ≡ 1. This b is the multiplicative inverse of a.
Definition 2.5 (Prime Field)
For a prime p, the field 𝔽ₚ = ℤₚ is called the prime field of characteristic p. It contains exactly p elements: {0, 1, 2, ..., p−1}.
Example 2.3 (Multiplicative Inverses in 𝔽₇)
Let us find all multiplicative inverses in 𝔽₇:
| a | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| a⁻¹ | 1 | 4 | 5 | 2 | 3 | 6 |
Verification: 2 × 4 = 8 ≡ 1, 3 × 5 = 15 ≡ 1, 6 × 6 = 36 ≡ 1.
2.4 The Extended Euclidean Algorithm
How do we efficiently compute multiplicative inverses? The answer is one of the oldest algorithms in mathematics: the Euclidean algorithm, extended to find not just the greatest common divisor, but also the coefficients of Bézout's identity.
Theorem 2.2 (Bézout's Identity)
For any integers a and b, not both zero, there exist integers x and y such that:
ax + by = gcd(a, b)
When gcd(a, p) = 1 (which is guaranteed when p is prime and a ≢ 0), Bézout's identity gives us:
ax + py = 1
Reducing modulo p: ax ≡ 1 (mod p). Thus x is the multiplicative inverse of a!
Algorithm 2.1 (Extended Euclidean Algorithm)
To find gcd(a, b) and integers x, y with ax + by = gcd(a, b):
function extended_gcd(a, b):
if b = 0:
return (a, 1, 0)
else:
(d, x, y) = extended_gcd(b, a mod b)
return (d, y, x - (a ÷ b) × y)
Example 2.4 (Finding 11⁻¹ in 𝔽₂₆)
Although 26 is not prime, let us trace through the algorithm for illustration. We seek x such that 11x ≡ 1 (mod 26).
Apply the Euclidean algorithm:
| Step | Equation | Quotient |
|---|---|---|
| 1 | 26 = 2 × 11 + 4 | 2 |
| 2 | 11 = 2 × 4 + 3 | 2 |
| 3 | 4 = 1 × 3 + 1 | 1 |
| 4 | 3 = 3 × 1 + 0 | — |
Now back-substitute:
- 1 = 4 − 1 × 3
- 1 = 4 − 1 × (11 − 2 × 4) = 3 × 4 − 1 × 11
- 1 = 3 × (26 − 2 × 11) − 1 × 11 = 3 × 26 − 7 × 11
Thus −7 × 11 ≡ 1 (mod 26), giving 11⁻¹ ≡ −7 ≡ 19 (mod 26).
Verification: 11 × 19 = 209 = 8 × 26 + 1 ≡ 1. ✓
2.5 Fermat's Little Theorem
An elegant alternative method for computing inverses emerges from a beautiful result attributed to Pierre de Fermat.
Theorem 2.3 (Fermat's Little Theorem)
Let p be prime and a an integer not divisible by p. Then:
aᵖ⁻¹ ≡ 1 (mod p)
Consider the set S = {a, 2a, 3a, ..., (p−1)a} reduced modulo p. Since gcd(a, p) = 1, multiplication by a is a bijection on 𝔽ₚ*, so S is just a permutation of {1, 2, ..., p−1}.
Taking the product of all elements in both representations:
a × 2a × 3a × ⋯ × (p−1)a ≡ 1 × 2 × 3 × ⋯ × (p−1) (mod p)
aᵖ⁻¹ × (p−1)! ≡ (p−1)! (mod p)
Since (p−1)! is not divisible by p, we may divide both sides by (p−1)!, yielding aᵖ⁻¹ ≡ 1.
An immediate corollary provides another formula for the multiplicative inverse:
Corollary 2.1
For a ≢ 0 (mod p):
a⁻¹ ≡ aᵖ⁻² (mod p)
From Fermat's theorem: aᵖ⁻¹ ≡ 1. Multiply both sides by a⁻¹: aᵖ⁻² ≡ a⁻¹.
Example 2.5
Find 3⁻¹ in 𝔽₇ using Fermat's theorem.
By the corollary: 3⁻¹ ≡ 3⁷⁻² = 3⁵ (mod 7).
Computing: 3² = 9 ≡ 2, 3⁴ = (3²)² ≡ 2² = 4, 3⁵ = 3⁴ × 3 ≡ 4 × 3 = 12 ≡ 5 (mod 7).
Verification: 3 × 5 = 15 ≡ 1 (mod 7). ✓
Efficiency.
For large primes (like Bitcoin's p ≈ 2²⁵⁶), the extended Euclidean algorithm is typically faster than exponentiation for finding inverses. However, the exponentiation method has advantages in certain constant-time implementations that resist side-channel attacks.
2.6 The Multiplicative Group 𝔽ₚ*
The nonzero elements of a prime field form a group under multiplication. This group has a remarkable structure.
Definition 2.6
The multiplicative group of 𝔽ₚ is:
𝔽ₚ* = (𝔽ₚ \ {0}, ×) = {1, 2, ..., p−1}
This is a group of order p − 1.
Theorem 2.4
The multiplicative group 𝔽ₚ* is cyclic.
This fundamental result means there exists a generator g such that every nonzero element can be written as a power of g. Such a generator is called a primitive root modulo p.
Example 2.6 (Primitive Root)
In 𝔽₇*, let us check if 3 is a primitive root:
| k | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 3ᵏ mod 7 | 3 | 2 | 6 | 4 | 5 | 1 |
The powers of 3 produce all six nonzero elements, so 3 is indeed a generator of 𝔽₇*.
The existence of generators in 𝔽ₚ* is precisely what enables the discrete logarithm problem to be defined in this group. When we move to elliptic curves, we shall see that points on the curve form a similar cyclic group, with a generator point playing an analogous role.
2.7 Division in Finite Fields
With multiplicative inverses in hand, division becomes straightforward: to compute a / b in 𝔽ₚ, we simply compute a × b⁻¹.
Example 2.7 (Division in 𝔽₁₃)
Compute 7 / 5 in 𝔽₁₃.
First find 5⁻¹. Using 5⁻¹ ≡ 5¹¹ (mod 13):
- 5² = 25 ≡ 12 ≡ −1 (mod 13)
- 5⁴ = (5²)² ≡ 1 (mod 13)
- 5⁸ ≡ 1 (mod 13)
- 5¹¹ = 5⁸ × 5² × 5 ≡ 1 × 12 × 5 = 60 ≡ 8 (mod 13)
Thus 7 / 5 = 7 × 8 = 56 ≡ 4 (mod 13).
Verification: 4 × 5 = 20 ≡ 7 (mod 13). ✓
This ability to divide (except by zero) is what distinguishes fields from mere rings. It is also what makes elliptic curve arithmetic possible: the formulas for point addition involve division, which is only well-defined in a field.
2.8 Large Primes in Cryptography
In practice, cryptographic systems use primes of tremendous size. Bitcoin's elliptic curve, secp256k1, is defined over a prime field where:
p = 2²⁵⁶ − 2³² − 2⁹ − 2⁸ − 2⁷ − 2⁶ − 2⁴ − 1
In decimal, this is approximately:
p ≈ 1.158 × 10⁷⁷
To appreciate this magnitude: there are roughly 10⁸⁰ atoms in the observable universe. The number of elements in our field is a substantial fraction of this cosmic count.
Why This Specific Prime?
The prime p = 2²⁵⁶ − 2³² − 977 was chosen for efficiency. Its special form allows faster modular reduction than a random 256-bit prime. The subtracted terms are small, enabling optimized implementations.