The Zcash ArboretumI Math Guide
Contents
PDF
Theme

6 Finite fields

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 264, does not permit: in ℤ/264ℤ no even class has an inverse (Theorem 2.24). The section gives two inversion algorithms for 𝔽p and proves that every finite field has pk elements for a prime p (6.10), so no field has 6, 10, or 12 elements. Fields of size 2k exist for every positive k, but the field with 264 elements is not ℤ/264ℤ: it is the polynomial quotient of 6.11, with different addition and multiplication. The section then defines the Frobenius map x↦xp and proves that the multiplicative group 𝔽q× is cyclic, the powers of a single element running through every nonzero value (6.18). Cyclicity gives discrete logarithms their meaning and guarantees the roots of unity on which the polynomial constructions of later sections depend.

6.1 The prime field and two inversion routes

Most constructions of the series are carried out over the field 𝔽p=ℤ/pℤ of 4.26, for a prime p of roughly 255 bits. Its addition, subtraction, and multiplication are the residue arithmetic of §2; inversion requires an algorithm, since a proof that an inverse exists (§4) does not compute it.

Construction 6.1 (Inversion by the extended Euclidean algorithm).

Given a with 0<a<p, run the extended Euclidean algorithm (Theorem 2.13) on the pair (a,p). Since p is prime and p∤a, the gcd is 1, and the algorithm outputs integers u,v with au+pv=1. Reducing modulo p gives au≡1(modp), that is,

a−1=[u]pin ⁢𝔽p.

The cost is O(logp) division steps (Theorem 2.13). This is the standard general-purpose method; a worked instance is Example 2.25, which computed [17]43−1=[38]43 by exactly this route.

The second method rests on Fermat’s little theorem and on the following fast exponentiation.

Construction 6.2 (Square-and-multiply).

Let a be an element of any structure with an associative multiplication, and let e≥1 have binary expansion e=∑iei2i with digits ei∈{0,1}. Squaring repeatedly produces the values

a20=a,a2i+1=(a2i)2,

and multiplying together the factors indexed by the nonzero digits gives

ae=∏i:ei=1a2i.

The computation uses ⌊log2e⌋ squarings and at most ⌊log2e⌋ further multiplications—O(loge) multiplications in all, against the e−1 multiplications of the naive product a⋅a⋯a. For the 255-bit exponents of later sections the former is a few hundred multiplications and the latter a count beyond the reach of any computer.

Remark 6.3.

Written additively, the same algorithm computes the multiple e⋅P of a group element P by repeated doubling and selective adding. Under the name double-and-add it is the algorithm for scalar multiplication on elliptic curves (10.20).

Construction 6.4 (Inversion by Fermat’s little theorem).

Let a∈𝔽p be nonzero. Fermat’s little theorem (Corollary 3.32) gives ap−1=1, hence a⋅ap−2=1, and so

a−1=ap−2,

computed by square-and-multiply (6.2) with exponent p−2, at a cost of O(logp) modular multiplications when p>2. For p=2, the only nonzero element is 1, whose inverse is 1; the exponent is zero and no multiplication is needed.

Example 6.5 (Both routes in 𝔽97).

Take p=97 and a=5. For 6.1, the Euclidean algorithm on 97 and 5 runs

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 au+pv=1 with (u,v)=(39,−2), and 5−1=[39]97. For 6.4, the exponent is e=p−2=95=26+24+23+22+21+20, and square-and-multiply (6.2) tabulates its digits and the repeated squares in 𝔽97:

i0123456ei1111101a2i525436363561

Multiplying the factors with ei=1 in order of i gives the partial products 5,28,40,46,7 and finally 7⋅61=427=4⋅97+39, so 595=39. This route costs 6 squarings and 5 multiplications, against the 94 multiplications of the naive product. Both routes give 39, and 5⋅39=195=2⋅97+1.

Remark 6.6 (Constant-time inversion).

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 p−2, never on the secret input a; the method is constant-time-friendly. The extended Euclidean method, by contrast, performs a sequence of divisions whose lengths and quotients depend on a itself, so its running time and memory-access pattern can leak information about a to an observer timing the computation. Side-channel-resistant implementations therefore often prefer the Fermat method despite its slightly larger constant factor.

6.2 Characteristic, prime subfield, and prime-power order

This subsection determines the possible cardinalities of a finite field through the characteristic of 4.5, defined by the canonical homomorphism

ι:ℤ→F,ι⁢(n)=n⋅1F,

whose kernel is an ideal nℤ of ℤ; the characteristic char(F) is its nonnegative generator (Definition 4.30).

Theorem 6.7.

Every finite field F has prime characteristic: char(F)=p for some prime p. In particular char(𝔽p)=p.

Proof.

The map ι cannot be injective, since its domain ℤ is infinite and its codomain F is finite; two distinct integers m<n must satisfy ι(m)=ι(n), and then n−m is a nonzero element of kerι. Hence kerι=nℤ with n>0, that is, char(F)>0; and the characteristic of a field, being nonzero, is prime by Theorem 4.32. For F=𝔽p itself, Example 4.31 computed char(ℤ/pℤ)=p directly. □

Every field of characteristic p contains a canonical copy of 𝔽p (Remark 4.33), defined as follows.

Definition 6.8 (Subfield; prime subfield).

A subfield of a field F is a subset K⊆F containing 0 and 1 and closed under addition, negation, multiplication, and inversion of nonzero elements; with the restricted operations, K is itself a field. The prime subfield of F is the intersection of all subfields of F—equivalently, the smallest subfield of F, and equivalently again the subfield generated by 1F.

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 1F generates—the closure of {1F} under the field operations—follows from the classification below, whose proof exhibits the prime subfield inside that closure.

Proposition 6.9 (Classification of prime subfields).

Let F be a field. If char(F)=p>0, the prime subfield of F is isomorphic to 𝔽p. If char(F)=0, it is isomorphic to ℚ.

Proof.

Suppose first that char(F)=p>0, so that kerι=pℤ. Define

ι¯:𝔽p=ℤ/pℤ→F,ι¯([a]p)=a⋅1F.

A single equivalence shows the map well defined and injective: a⋅1F=b⋅1F holds if and only if (a−b)⋅1F=0, i.e. a−b∈kerι=pℤ, i.e. [a]p=[b]p. It is a ring homomorphism because ι is one (4.5) and ι¯ evaluates ι on representatives of residue classes. Its image K={a⋅1F:a∈ℤ} is therefore a subring of F isomorphic to the field 𝔽p, and K is a subfield: for [a]p≠[0]p the computation ι¯([a]p)ι¯([a]p−1)=ι¯([1]p)=1F exhibits the inverse of each nonzero element of K inside K. Finally, K lies in every subfield: a subfield contains 1F, hence all its additive multiples a⋅1F by closure under addition and negation. So K is contained in the intersection of all subfields and is itself a subfield, so K equals that intersection: the prime subfield is K≅𝔽p.

Now suppose char(F)=0, so that ι is injective and b⋅1F≠0 for every nonzero integer b. Define

j:ℚ→F,j⁢(ab)=(a⋅1F)⁢(b⋅1F)−1.

The map is well defined: if a/b=c/d with b,d≠0, then ad=bc in ℤ, so (a⋅1F)(d⋅1F)=(b⋅1F)(c⋅1F) by applying ι, and multiplying both sides by (b⋅1F)−1(d⋅1F)−1 gives (a⋅1F)(b⋅1F)−1=(c⋅1F)(d⋅1F)−1. That j preserves sums, products, and 1 is the usual arithmetic of fractions, transported by the homomorphism ι and commutativity. The map is injective: j(a/b)=0 forces a⋅1F=0, hence a=0. The image of j is thus a subfield of F isomorphic to ℚ; and it lies in every subfield K, since K contains 1F, hence every a⋅1F, hence—being closed under inversion and multiplication—every (a⋅1F)(b⋅1F)−1. As before the image must equal the intersection of all subfields, and the prime subfield is a copy of ℚ. □

The size constraint follows by counting over the prime subfield. Every field F of characteristic p is a vector space over its prime subfield 𝔽p: vectors are the elements of F, vector addition is the field addition, and scalar multiplication c⋅x for c∈𝔽p⊆F is the field multiplication, so the vector-space axioms are instances of the ring axioms of F. The proof uses two facts, proved in 8 independently of the present theorem: a space with a finite spanning set has a basis, and coordinates with respect to a basis are unique.

Theorem 6.10 (Finite fields have prime-power order).

Every finite field F has cardinality |F|=pk for some prime p and integer k≥1, where p=char(F).

Proof.

By 6.7 the characteristic of F is a prime p, and by 6.9 the prime subfield of F is a copy of 𝔽p, with which we identify it. As explained above, F is then a vector space over 𝔽p. It is spanned by the finite set F itself, so it has a finite basis e1,…,ek; and k≥1 because 1≠0 makes F nonzero. Every element of F is thus

c1⁢e1+c2⁢e2+⋯+ck⁢ek

for a unique tuple (c1,…,ck) with each ci∈𝔽p: existence because the ei span, uniqueness because coordinates with respect to a basis are unique (8). The assignment (c1,…,ck)↦∑iciei is therefore a bijection from 𝔽pk to F, and counting tuples gives |F|=p⋅p⋯p=pk. □

Theorem 6.11 (Existence and uniqueness of 𝔽q).

For every prime power q=pk there exists a field with exactly q elements, and any two finite fields of the same cardinality are isomorphic. One constructs such a field as the quotient 𝔽p[x]/(f) of the polynomial ring by the ideal generated by an irreducible polynomial f of degree k—the construction recorded in Example 4.22.

Remark 6.12.

The fields on the critical path of Halo 2 and Orchard are prime fields, the case q=p with k=1, where the theorem is proved: existence is 4.26, and uniqueness holds because a field with p elements has order pk=p with k=1 by 6.10, so it equals its own prime subfield, a copy of 𝔽p (6.9). The general case k≥2 would require polynomial factorisation over field extensions; no later result depends on it, so it is stated without proof. Convention, fixed henceforth: the letter q=pk denotes a prime power, and 𝔽q a field with q elements, of characteristic p; results are stated for general 𝔽q whenever the proof is identical to the prime case, and for the applications to Halo 2 one may take q=p throughout.

6.3 The Frobenius endomorphism

The identity (a+b)p=ap+bp, a common error over ℚ and ℝ, where it is false for every p≥2, is a theorem in characteristic p. Its proof expands (a+b)p by the binomial theorem.

Lemma 6.13 (Binomial theorem; the coefficients count subsets).

Let R be a commutative ring. For all a,b∈R and every integer n≥0,

(a+b)n=∑k=0n(nk)⁢ak⁢bn−k,

where the integer coefficient (nk) acts as the additive multiple (nk)⋅x=x+⋯+x, equals the number of k-element subsets of an n-element set, and satisfies

(nk)=n!k!⁢(n−k)!.
Proof.

Expand the product (a+b)n=(a+b)⋯(a+b) by distributivity without collecting terms: the result is a sum of 2n products, one for each way of choosing, from every factor, either its a or its b. By commutativity such a product equals akbn−k exactly when a was chosen from k of the n factors, and it is determined by the set of those k factors; so the coefficient of akbn−k is the number of k-element subsets of the n factors, and collecting the terms gives the displayed sum.

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, n−1 for the second, and n−k+1 for the k-th: n(n−1)⋯(n−k+1)=n!/(n−k)! sequences. Alternatively, each such sequence is a k-element subset together with an ordering of it, and a k-element set has k! orderings — the same count with k in place of n — so there are k! sequences per subset, and the number of subsets is n!/(k!(n−k)!). □

Lemma 6.14 (Freshman’s dream).

Let R be a commutative ring of prime characteristic p. Then for all a,b∈R,

(a+b)p=ap+bp,

and more generally (a+b)pn=apn+bpn for every n≥1.

Proof.

By the binomial theorem (6.13),

(a+b)p=∑i=0p(pi)⁢ai⁢bp−i,

where the integer coefficient (pi) acts as the additive multiple (pi)⋅x=x+⋯+x. We claim that p∣(pi) for 0<i<p. From the factorial identity of the same lemma

(pi)⁢i!⁢(p−i)!=p!

the prime p divides the right-hand side. It does not divide i!(p−i)!: that product is a product of integers all smaller than p, and if p divided the product it would divide one of the factors by Euclid’s lemma for primes (Lemma 2.17), which is impossible. Applying Euclid’s lemma to the left-hand side instead, p must divide (pi), say (pi)=pm.

Now let 0<i<p and consider the corresponding term. Writing ι(n)=n⋅1R for the canonical homomorphism of 4.5, the coefficient acts as multiplication by ι((pi))=ι(pm)=ι(p)ι(m)=0⋅ι(m)=0, since char(R)=p means exactly ι(p)=p⋅1R=0. Every middle term of the binomial expansion therefore vanishes, and the terms i=p and i=0 leave (a+b)p=ap+bp.

The general case follows by induction on n, the base case n=1 being the identity just proved. For n≥2, apply the base case to the elements apn−1 and bpn−1:

(a+b)pn=((a+b)pn−1)p=(apn−1+bpn−1)p=apn+bpn,

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.

Definition 6.15 (Frobenius endomorphism).

Let F be a field of characteristic p>0. The Frobenius map of F is

Frob:F→F,Frob⁡(x)=xp.
Proposition 6.16.

Let F be a field of characteristic p. The Frobenius map is a ring homomorphism F→F fixing the prime subfield pointwise. If F is finite, Frob is an automorphism of F—a bijective ring homomorphism of F onto itself.

Proof.

Multiplicativity follows from commutativity and associativity alone: (x⁢y)p=xpyp. Additivity is the freshman’s dream (Lemma 6.14), and 1p=1; so Frob is a ring homomorphism.

Injectivity is an instance of a general fact used again later: every ring homomorphism between fields is injective. If ϕ:F→F′ had ϕ(x)=0 for some x≠0, then

1=ϕ⁢(1)=ϕ⁢(x−1⁢x)=ϕ⁢(x−1)⁢ϕ⁢(x)=ϕ⁢(x−1)⋅0=0

in F′, contradicting 1≠0 in a field. In particular Frob is injective.

The prime subfield is fixed pointwise. By 6.9 its elements are the values ι¯([a]p)=a⋅1F, and since ι¯ is a ring homomorphism,

Frob⁡(ι¯⁢([a]p))=ι¯⁢([a]p)p=ι¯⁢([a]pp)=ι¯⁢([ap]p)=ι¯⁢([a]p),

the last step because ap≡a(modp) for all integers a (Corollary 3.32).

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 Frobn(x)=xpn are again homomorphisms, by the general case of the freshman’s dream. On 𝔽p the Frobenius map is the identity; on larger fields of characteristic p it is not, and 6.25 records its role in cryptography.

6.4 Cyclicity of the multiplicative group

The multiplicative group 𝔽q× is a finite abelian group of order q−1, since every nonzero element of a field is invertible. Finite abelian groups need not be cyclic: the unit group (ℤ/8⁢ℤ)× of Example 3.22 has order 4 and no element of order 4. The proof that 𝔽q× is cyclic is a counting argument of Gauss, resting on an identity for the totient function φ and using only its counting definition (Definition 2.26): φ(n) is the number of integers a with 1≤a≤n and gcd(a,n)=1.

Lemma 6.17 (Gauss’s divisor-sum identity).

For every integer n≥1,

∑d∣nφ⁢(d)=n,

the sum running over the positive divisors d of n.

Proof.

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

Cd={a:1≤a≤n,gcd⁡(a,n)=d},d∣n,

are disjoint and cover {1,…,n}; hence n=∑d∣n|Cd|.

We claim |Cd|=φ(n/d). A member of Cd is divisible by d, so it has the form a=db with 1≤b≤n/d; we show that, for such a,

gcd⁡(d⁢b,n)=d⟺gcd⁡(b,n/d)=1.

For the forward direction, suppose e=gcd(b,n/d)>1; then de divides both db=a and d⋅(n/d)=n, so de is a common divisor exceeding d and gcd(a,n)≥de>d. For the converse, suppose gcd(b,n/d)=1. The integer d is a common divisor of a and n, so d divides g=gcd(a,n) by the strongest-common-divisor property (Remark 2.12); write g=dc with c≥1. From dc∣db we get c∣b, and from dc∣n=d(n/d) we get c∣n/d (cancel d in each divisibility); so c divides gcd(b,n/d)=1, forcing c=1 and g=d.

The members of Cd are therefore exactly the integers db with 1≤b≤n/d and gcd(b,n/d)=1, and by the counting definition of the totient (Definition 2.26) there are precisely φ(n/d) of them. Summing,

n=∑d∣nφ⁢(nd)=∑d∣nφ⁢(d),

the second equality because d↦n/d is a bijection of the set of positive divisors of n onto itself. □

Theorem 6.18 (Finite subgroups of F× are cyclic).

Let F be any field and let G≤F× be a finite subgroup of the multiplicative group, of order N. Then G is cyclic. In particular, for a finite field 𝔽q the whole multiplicative group 𝔽q× is cyclic of order q−1.

Proof.

For each divisor d∣N, let

ψ⁢(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 N=|G| (Corollary 3.30), so the sets counted by the ψ(d) partition G and

∑d∣Nψ⁢(d)=N. (6)

We claim that for each d∣N, either ψ(d)=0 or ψ(d)=φ(d). Suppose ψ(d)>0 and choose a∈G of order d. The powers a0,a1,…,ad−1 are d distinct elements of G (Proposition 3.12(3)), and each satisfies

(aj)d=(ad)j=1j=1,

so each is a root in F of the polynomial Xd−1∈F[X]. That polynomial has degree d, so it has at most d roots in F (Theorem 5.18); the d distinct powers of a therefore account for all of its roots. Now take any b∈G of order d. Then bd=1, so b is a root of Xd−1 and hence b=aj for some 0≤j<d. By Corollary 3.23,

ord⁡(aj)=dgcd⁡(d,j),

which equals d exactly when gcd(j,d)=1. The elements of order d in G are thus precisely the powers aj with 0≤j<d and gcd(j,d)=1, and by the counting definition of the totient there are φ(d) of them: ψ(d)=φ(d). This proves the claim, and with it the inequality ψ(d)≤φ(d) for every d∣N.

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: ψ(d)=φ(d) for every divisor d∣N. In particular

ψ⁢(N)=φ⁢(N)≥1,

since a=1 always witnesses gcd(1,N)=1 in the totient count. Hence G contains an element g of order N; its powers form a subgroup of G with N distinct elements (Proposition 3.12(3)), which must be all of G. So G=⟨g⟩ is cyclic.

For the final statement, let F=𝔽q be finite. The multiplicative group 𝔽q× has q−1 elements—every nonzero element of a field is a unit—and is a finite subgroup of itself, so it is cyclic of order q−1. □

Corollary 6.19 (Element-order census in cyclic groups).

A cyclic group G of order N contains, for each divisor d∣N, exactly φ(d) elements of order d, and no elements of any other order. In particular G has exactly φ(N) generators.

Proof.

Write G=⟨g⟩ with ord(g)=N; the elements of G are the powers gj, 0≤j<N, each appearing once (Proposition 3.12(3)). By Corollary 3.23, ord(gj)=N/gcd(N,j), which is always a divisor of N; and ord(gj)=d if and only if gcd(j,N)=N/d. By the gcd computation in the proof of Lemma 6.17 (applied with n=N and divisor N/d), the exponents j∈{1,…,N} with gcd(j,N)=N/d are exactly j=(N/d)t with 1≤t≤d and gcd(t,d)=1, of which there are φ(d) by Definition 2.26. The generators are the elements of order N, numbering φ(N). □

Definition 6.20 (Primitive root).

A generator of the cyclic group 𝔽q× is called a primitive root (or primitive element) of 𝔽q. Equivalently, an element g∈𝔽q× is primitive if and only if ord(g)=q−1.

Primitive roots exist by 6.18; by 6.19 there are exactly φ(q−1) of them.

Remark 6.21.

The group-theoretic term “generator of 𝔽q×” and the polynomial term “primitive (q−1)-th root of unity” (9.3) denote the same elements; the identification is restated once roots of unity have been defined in general.

Example 6.22 (Primitive roots of 𝔽7).

The group 𝔽7× has order 6. Testing g=3, the successive powers modulo 7 are

31=3,32=2,33=6,34=4,35=5,36=1,

which run through all of {1,…,6}: the element 3 is a primitive root of 𝔽7. By contrast 2 is not: its powers are 2,4,1, so ord(2)=3<6. The complete set of primitive roots consists of the powers 3j with gcd(j,6)=1 (Corollary 3.23), namely j=1 and j=5: the primitive roots of 𝔽7 are 31=3 and 35=5, and there are φ(6)=2 of them, as the census predicts.

Cyclicity also determines the number of solutions of the equation xn=1 in a finite field, on which the evaluation domains of later sections depend.

Corollary 6.23 (Roots of unity in 𝔽q).

Let 𝔽q be a finite field and n≥1. The solutions of xn=1 in 𝔽q× number exactly gcd(n,q−1), and they form the cyclic subgroup of 𝔽q× of that order. In particular, when n∣q−1 the equation has exactly n solutions.

Proof.

Fix a primitive root g (6.18) and write each element of 𝔽q× uniquely as x=gj with 0≤j≤q−2 (Proposition 3.12(3)). Then xn=gj⁢n, and gj⁢n=1 holds if and only if (q−1)∣jn (Proposition 3.12(1)). Set d=gcd(n,q−1) and write q−1=dm, n=dn′ with gcd(m,n′)=1. Then

(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 gcd(m,n′)=1). The qualifying exponents in {0,…,q−2} are therefore the multiples of m=(q−1)/d, namely j=tm for t=0,1,…,d−1: exactly d of them. The corresponding solutions x=(gm)t are exactly the powers of gm, which by Corollary 3.23 has order (q−1)/gcd(q−1,m)=(q−1)/m=d; so the solution set is the cyclic subgroup ⟨gm⟩ of order d=gcd(n,q−1). When n∣q−1 we have d=n, giving exactly n solutions. □

Remark 6.24 (Two-adicity and proof-system fields).

The corollary makes a curve such as Pallas or Vesta suitable for Halo 2: the field size q is chosen so that q−1 is divisible by a large power of 2, and the corollary then guarantees a multiplicative subgroup of 2-power order. That subgroup is the evaluation domain of the number-theoretic transform, on which efficient polynomial arithmetic rests. The construction of these domains and the transform itself are treated in 9; the curves are introduced in 10.

Remark 6.25 (Cyclicity and Frobenius in cryptography).

The cyclicity of 𝔽q× (6.18) underlies the discrete-logarithm problem—every nonzero element has the form gj, 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 𝔽p, an endomorphism of the curve whose characteristic polynomial T2−tT+p encodes the number of curve points as N=p+1−t, where t is the Hasse trace; the order of the cryptographic group is thus determined by the field-theoretic Frobenius. Both connections are taken up in 10.