This section studies the finite fields, the fields of
§4 with finitely many elements. A verifier must divide
by every nonzero value, which the arithmetic of a 64-bit processor word,
modulo 2 64 , does not permit: in Z / 2 64 Z no even class has an
inverse (Theorem 2.24). The section gives two inversion
algorithms for F p and proves that every finite field has p k
elements for a prime p (6.10), so no field
has 6 , 10 , or 12 elements. Fields of size 2 k exist for every
positive k , but the field with 2 64 elements is not
Z / 2 64 Z : it is the polynomial quotient of
6.11, with different addition and
multiplication. The section then defines the Frobenius map
Most constructions of the series are carried out over the field
Given a with
| a − 1 = [u] p in F p . |
The cost is O (log p) division steps
(Theorem 2.13). This is the standard general-purpose
method; a worked instance is Example 2.25, which
computed
The second method rests on Fermat’s little theorem and on the following fast exponentiation.
Let a be an element of any structure with an associative multiplication,
and let
| a 2 0 = a, a 2 i + 1 = (a 2 i) 2, |
and multiplying together the factors indexed by the nonzero digits gives
| a e = ∏ i : e i = 1 a 2 i . |
The computation uses ⌊ log 2 e ⌋ squarings and at most
⌊ log 2 e ⌋ further multiplications— O (log e) multiplications
in all, against the
Written additively, the same algorithm computes the multiple
Let
| a − 1 = a p − 2, |
computed by square-and-multiply (6.2) with
exponent
Take
| 97 | = 19 ⋅ 5 + 2, | ||
| 5 | = 2 ⋅ 2 + 1, | ||
| 2 | = 2 ⋅ 1 + 0, |
and back-substitution gives
| 1 = 5 − 2 ⋅ 2 = 5 − 2 (97 − 19 ⋅ 5) = 39 ⋅ 5 − 2 ⋅ 97, |
so
| i 0 1 2 3 4 5 6 e i 1 1 1 1 1 0 1 a 2 i 5 25 43 6 36 35 61 |
Multiplying the factors with
The two methods have comparable asymptotic cost. In
6.4 the sequence of operations
performed—which steps square, which multiply—depends only on the binary
digits of the public exponent
This subsection determines the possible cardinalities of a finite field through the characteristic of 4.5, defined by the canonical homomorphism
| ι : Z → F, ι (n) = n ⋅ 1 F, |
whose kernel is an ideal n Z of Z ; the characteristic char (F) is its nonnegative generator (Definition 4.30).
Every finite field F has prime characteristic:
The map ι cannot be injective, since its domain Z is infinite
and its codomain F is finite; two distinct integers
Every field of characteristic p contains a canonical copy of F p (Remark 4.33), defined as follows.
A subfield of a field F is a subset
The intersection of any family of subfields is again a subfield, since each defining closure property is preserved under intersection; the intersection of all subfields is contained in every subfield, hence is the smallest one. That this smallest subfield is exactly what 1 F generates—the closure of { 1 F } under the field operations—follows from the classification below, whose proof exhibits the prime subfield inside that closure.
Let F be a field. If
Suppose first that
| ι ̄ : F p = Z / p Z → F, ι ̄ ([a] p) = a ⋅ 1 F . |
A single equivalence shows the map well defined and injective:
Now suppose
| j : Q → F, j (a b) = (a ⋅ 1 F) (b ⋅ 1 F) − 1 . |
The map is well defined: if
The size constraint follows by counting over the prime subfield. Every
field F of characteristic p is a vector space over its prime
subfield F p : vectors are the elements of F , vector addition is the
field addition, and scalar multiplication
Every finite field F has cardinality
By 6.7 the characteristic of F is a prime
p , and by 6.9 the prime subfield of F
is a copy of F p , with which we identify it. As explained above, F
is then a vector space over F p . It is spanned by the finite set F
itself, so it has a finite basis
| c 1 e 1 + c 2 e 2 + ⋯ + c k e k |
for a unique tuple (c 1, ..., c k) with each
For every prime power
The fields on the critical path of Halo 2 and Orchard are prime
fields, the case
The identity
Let R be a commutative ring. For all
| (a + b) n = ∑ k = 0 n (n k) a k b n − k, |
where the integer coefficient (n k) acts as the additive
multiple
| (n k) = n ! k ! (n − k) ! . |
Expand the product
For the formula, count the sequences of k distinct elements of an
n -element set in two ways. Choosing the entries in turn, there
are n choices for the first,
Let R be a commutative ring of prime characteristic p . Then for all
| (a + b) p = a p + b p, |
and more generally
By the binomial theorem (6.13),
| (a + b) p = ∑ i = 0 p (p i) a i b p − i, |
where the integer coefficient (p i) acts as the additive
multiple
| (p i) i ! (p − i) ! = p ! |
the prime p divides the right-hand side. It does not divide
Now let
The general case follows by induction on n , the base case
| (a + b) p n = ((a + b) p n − 1) p = (a p n − 1 + b p n − 1) p = a p n + b p n, |
using the inductive hypothesis in the middle step. □
A homomorphism from a structure to itself is an endomorphism. In characteristic p the p -th power map is one: it preserves addition by the lemma, and multiplication by commutativity.
Let F be a field of characteristic
| Frob : F → F, Frob (x) = x p . |
Let F be a field of characteristic p . The Frobenius map is a ring
homomorphism
Multiplicativity follows from commutativity and associativity alone:
Injectivity is an instance of a general fact used again later:
every ring homomorphism between fields is injective. If
| 1 = φ (1) = φ (x − 1 x) = φ (x − 1) φ (x) = φ (x − 1) ⋅ 0 = 0 |
in F ′ , contradicting
The prime subfield is fixed pointwise. By
6.9 its elements are the values
| Frob (ι ̄ ([a] p)) = ι ̄ ([a] p) p = ι ̄ ([a] p p) = ι ̄ ([a p] p) = ι ̄ ([a] p), |
the last step because
Finally, let F be finite. An injective map from a finite set to itself is surjective—the injectivity-implies-surjectivity argument of 4.4—so Frob is a bijective ring homomorphism of F onto itself, an automorphism. □
The iterates
The multiplicative group F q × is a finite abelian group of order
For every integer
| ∑ d ∣ n φ (d) = n, |
the sum running over the positive divisors d of n .
Partition the set { 1, 2, ..., n } according to the value of gcd (a, n) . For each a the gcd is a positive divisor d of n , so the classes
| C d = { a : 1 ≤ a ≤ n, gcd (a, n) = d }, d ∣ n, |
are disjoint and cover { 1, ..., n } ; hence
We claim
| gcd (d b, n) = d ⟺ gcd (b, n / d) = 1 . |
For the forward direction, suppose
The members of C d are therefore exactly the integers d b with
| n = ∑ d ∣ n φ (n d) = ∑ d ∣ n φ (d), |
the second equality because
Let F be any field and let
For each divisor
| ψ (d) = | { a ∈ G : ord (a) = d } | |
count the elements of G of order exactly d . Every element of the
finite group G has finite order dividing
| ∑ d ∣ N ψ (d) = N . | (6) |
We claim that for each
| (a j) d = (a d) j = 1 j = 1, |
so each is a root in F of the polynomial
| ord (a j) = d gcd (d, j), |
which equals d exactly when
Summing the inequality over the divisors of N and comparing (6) with Gauss’s identity (Lemma 6.17),
| N = ∑ d ∣ N ψ (d) ≤ ∑ d ∣ N φ (d) = N . |
The two ends are equal, so the inequality is an equality term by term:
| ψ (N) = φ (N) ≥ 1, |
since
For the final statement, let
A cyclic group G of order N contains, for each divisor
Write
A generator of the cyclic group F q × is called a
primitive root (or primitive element) of F q .
Equivalently, an element
The group-theoretic term “generator of F q × ” and the polynomial
term “primitive
The group F 7 × has order 6 . Testing
| 3 1 = 3, 3 2 = 2, 3 3 = 6, 3 4 = 4, 3 5 = 5, 3 6 = 1, |
which run through all of { 1, ..., 6 } : the element 3 is a
primitive root of F 7 . By contrast 2 is not: its powers are
Cyclicity also determines the number of solutions of the equation
Let F q be a finite field and
Fix a primitive root g (6.18) and write each
element of F q × uniquely as
| (q − 1) ∣ j n ⇔ d m ∣ j d n ′ ⇔ m ∣ j n ′ ⇔ m ∣ j, |
the last step by Euclid’s lemma
(Proposition 2.15(1), with
The corollary makes a curve such as Pallas or Vesta suitable for Halo 2:
the field size q is chosen so that
The cyclicity of F q ×
(6.18) underlies the discrete-logarithm
problem—every nonzero element has the form g j , the problem is to
recover j , and the presumed hardness of doing so is a foundational
assumption of later volumes—and, through
6.23, guarantees the existence of the
roots of unity used in polynomial commitment schemes. The Frobenius
endomorphism (6.15) induces, on an
elliptic curve over F p , an endomorphism of the curve whose
characteristic polynomial