Math Guide Mathematical foundations for Halo 2 and Zcash Orchard 5 Polynomials over a field 7 Number theory for cryptography

6 Finite fields

A processor stores a number in a word of fixed width. A 64-bit word can hold exactly $2^{64}$ distinct values, and the hardware’s arithmetic wraps around on overflow: what the machine natively computes is addition and multiplication modulo $2^{64}$ . For a verifier that must add, multiply, and divide, this built-in arithmetic falls at the last hurdle: in $\mathbb{Z}/2^{64}\mathbb{Z}$ no even class has an inverse, since a class is a unit only when its representative is coprime to the modulus (Theorem 2.24). The question this section answers is the natural one to ask next. Among all finite arithmetics—finite sets closed under an addition and a multiplication obeying the ring laws—which ones allow division by every nonzero element? In the language of §4: what are the finite fields, what sizes do they come in, and what structure do they carry?

Part of the answer is already in hand. The residue ring $\mathbb{Z}/n\mathbb{Z}$ is a field exactly when $n$ is prime (4.26), giving one finite field $\mathbb{F}_{p}$ for every prime $p$ ; and the quotient recipe of Example 4.22 promised further examples of prime-power size $p^{k}$ . This section completes the picture with two theorems. The first, 6.9, is a prohibition: no other sizes occur—every finite field has exactly $p^{k}$ elements for some prime $p$ , so there is no field with $6$ , $10$ , or $12$ elements. This constrains cardinalities, not binary representation widths: fields of size $2^{k}$ exist for every positive $k$ . The second, 6.17, is the section’s payoff and one of the most consequential facts in the volume: the multiplicative group $\mathbb{F}_{q}^{\times}$ is cyclic—the powers of a single well-chosen element sweep out every nonzero value. Cyclicity is what makes discrete logarithms meaningful and what guarantees the roots of unity on which the polynomial machinery of later sections runs.

The route is as follows. We first make the prime field $\mathbb{F}_{p}$ computational, with two inversion algorithms and the square-and-multiply technique that powers one of them. We then determine the possible sizes of a finite field through the characteristic and the prime subfield, meet the Frobenius map $x\mapsto x^{p}$ —the symmetry peculiar to characteristic $p$ —and finally prove cyclicity by a counting argument of Gauss.

6.1 The prime field and two inversion routes

The field $\mathbb{F}_{p}=\mathbb{Z}/p\mathbb{Z}$ certified by 4.26 is the workhorse of the entire series, and the first order of business is to compute in it. Addition, subtraction, and multiplication are residue arithmetic as in §2; the operation that needs an algorithm is inversion. As §4 stressed, an existence proof and an algorithm are different assets, and cryptography needs both. For inversion in $\mathbb{F}_{p}$ there are two standard routes, with different characters.

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\nmid a$ , the gcd is $1$ , and the algorithm outputs integers $u, v$ with $au+pv=1$ . Reducing modulo $p$ gives $au\equiv 1\pmod{p}$ , that is,

a^{-1}=[u]_{p}\quad\text{in }\mathbb{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 $[17]_{43}^{-1}=[38]_{43}$ by exactly this route.

The second route rests on Fermat’s little theorem and on a technique for fast exponentiation that is used throughout cryptography, so we record the technique first, in the generality it deserves.

Construction 6.2 (Square-and-multiply).

Let $a$ be an element of any structure with an associative multiplication, and let $e\geq 1$ have binary expansion $e=\sum_{i}e_{i}2^{i}$ with digits $e_{i}\in\{0,1\}$ . Squaring repeatedly produces the values

a^{2^{0}}=a,\qquad a^{2^{i+1}}=\bigl{(}a^{2^{i}}\bigr{)}^{2},

and multiplying together the factors indexed by the nonzero digits gives

a^{e}=\prod_{i\,:\,e_{i}=1}a^{2^{i}}.

The computation uses $\lfloor\log_{2}e\rfloor$ squarings and at most $\lfloor\log_{2}e\rfloor$ further multiplications— $O(\log e)$ multiplications in all, against the $e-1$ multiplications of the naive product $a\cdot a\cdots a$ . For the $255$ -bit exponents of later sections the difference is that between a few hundred multiplications and a count that no conceivable computer could finish.

Remark 6.3.

Written additively, the same algorithm computes the multiple $e\cdot 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), where the group operation is written $+$ ; the two names denote one algorithm in two notations.

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

Let $a\in\mathbb{F}_{p}$ be nonzero. Fermat’s little theorem (Corollary 3.32) gives $a^{p-1}=1$ , hence $a\cdot a^{p-2}=1$ , and so

a^{-1}=a^{p-2},

computed by square-and-multiply (6.2) with exponent $p-2$ , at a cost of $O(\log p)$ 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.

Remark 6.5 (Constant-time inversion).

The two routes are asymptotically comparable, but they differ in a respect invisible to asymptotics and central to practice. 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 route, 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 route despite its slightly larger constant factor.

6.2 Characteristic, prime subfield, and prime-power order

We turn to the sizes question: which cardinalities can a finite field have? The tool is the characteristic of 4.5. Recall the canonical homomorphism

\iota\colon\mathbb{Z}\to F,\qquad\iota(n)=n\cdot 1_{F},

whose kernel is an ideal $n\mathbb{Z}$ of $\mathbb{Z}$ ; the characteristic $\operatorname{char}(F)$ is its nonnegative generator (Definition 4.30).

Theorem 6.6.

Every finite field $F$ has prime characteristic: $\operatorname{char}(F)=p$ for some prime $p$ . In particular $\operatorname{char}(\mathbb{F}_{p})=p$ .

Proof.

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

The characteristic locates a canonical copy of $\mathbb{F}_{p}$ inside every field of characteristic $p$ . Remark 4.33 described this copy informally; we now make it precise, beginning with the notion of a subfield.

Definition 6.7 (Subfield; prime subfield).

A subfield of a field $F$ is a subset $K\subseteq 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 $1_{F}$ .

Two words on the equivalences. The intersection of any family of subfields is again a subfield, since each defining closure property survives intersection; and 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 the closure of $\{1_{F}\}$ .

Proposition 6.8 (Classification of prime subfields).

Let $F$ be a field. If $\operatorname{char}(F)=p>0$ , the prime subfield of $F$ is isomorphic to $\mathbb{F}_{p}$ . If $\operatorname{char}(F)=0$ , it is isomorphic to $\mathbb{Q}$ .

Proof.

Suppose first that $\operatorname{char}(F)=p>0$ , so that $\ker\iota=p\mathbb{Z}$ . Define

\bar{\iota}\colon\mathbb{F}_{p}=\mathbb{Z}/p\mathbb{Z}\to F,\qquad\bar{\iota}(% [a]_{p})=a\cdot 1_{F}.

The map is well defined and injective at a stroke: $a\cdot 1_{F}=b\cdot 1_{F}$ holds if and only if $(a-b)\cdot 1_{F}=0$ , i.e. $a-b\in\ker\iota=p\mathbb{Z}$ , i.e. $[a]_{p}=[b]_{p}$ . It is a ring homomorphism because $\iota$ is one (4.5) and $\bar{\iota}$ merely re-reads $\iota$ on residue classes. Its image $K=\{\,a\cdot 1_{F}:a\in\mathbb{Z}\,\}$ is therefore a subring of $F$ isomorphic to the field $\mathbb{F}_{p}$ , and $K$ is in fact a subfield: for $[a]_{p}\neq[0]_{p}$ the computation $\bar{\iota}([a]_{p})\,\bar{\iota}([a]_{p}^{-1})=\bar{\iota}([1]_{p})=1_{F}$ exhibits the inverse of each nonzero element of $K$ inside $K$ . Finally, $K$ lies in every subfield: a subfield contains $1_{F}$ , hence all its additive multiples $a\cdot 1_{F}$ by closure under addition and negation. So $K$ is contained in the intersection of all subfields and is itself a subfield, forcing $K$ to be that intersection: the prime subfield is $K\cong\mathbb{F}_{p}$ .

Now suppose $\operatorname{char}(F)=0$ , so that $\iota$ is injective and $b\cdot 1_{F}\neq 0$ for every nonzero integer $b$ . Define

j\colon\mathbb{Q}\to F,\qquad j\!\left(\frac{a}{b}\right)=(a\cdot 1_{F})(b% \cdot 1_{F})^{-1}.

The map is well defined: if $a/b=c/d$ with $b,d\neq 0$ , then $ad=bc$ in $\mathbb{Z}$ , so $(a\cdot 1_{F})(d\cdot 1_{F})=(b\cdot 1_{F})(c\cdot 1_{F})$ by applying $\iota$ , and multiplying both sides by $(b\cdot 1_{F})^{-1}(d\cdot 1_{F})^{-1}$ gives $(a\cdot 1_{F})(b\cdot 1_{F})^{-1}=(c\cdot 1_{F})(d\cdot 1_{F})^{-1}$ . That $j$ preserves sums, products, and $1$ is the usual arithmetic of fractions, transported by the homomorphism $\iota$ and commutativity. Injectivity is immediate: $j(a/b)=0$ forces $a\cdot 1_{F}=0$ , hence $a=0$ . The image of $j$ is thus a subfield of $F$ isomorphic to $\mathbb{Q}$ ; and it lies in every subfield $K$ , since $K$ contains $1_{F}$ , hence every $a\cdot 1_{F}$ , hence—being closed under inversion and multiplication—every $(a\cdot 1_{F})(b\cdot 1_{F})^{-1}$ . As before the image must equal the intersection of all subfields, and the prime subfield is a copy of $\mathbb{Q}$ . □

The size constraint now falls out of a counting device worth naming, for it recurs whenever a field sits over a subfield: vector-space counting over the prime subfield. Every field $F$ of characteristic $p$ is a vector space over its prime subfield $\mathbb{F}_{p}$ : vectors are the elements of $F$ , vector addition is the field addition, and scalar multiplication $c\cdot x$ for $c\in\mathbb{F}_{p}\subseteq F$ is the field multiplication, so the vector-space axioms are instances of the ring axioms of $F$ . The proof below uses exactly two facts about vector spaces: a space with a finite spanning set has a basis, and coordinates with respect to a basis are unique. Both are stated and proved in the linear-algebra section (8), whose development is independent of the present theorem, so no circularity arises.

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

Every finite field $F$ has cardinality $\lvert F\rvert=p^{k}$ for some prime $p$ and integer $k\geq 1$ , where $p=\operatorname{char}(F)$ .

Proof.

By 6.6 the characteristic of $F$ is a prime $p$ , and by 6.8 the prime subfield of $F$ is a copy of $\mathbb{F}_{p}$ , with which we identify it. As explained above, $F$ is then a vector space over $\mathbb{F}_{p}$ . It is spanned by the finite set $F$ itself, so it has a finite basis $e_{1},\dots,e_{k}$ ; and $k\geq 1$ because $1\neq 0$ makes $F$ nonzero. Every element of $F$ is thus

c_{1}e_{1}+c_{2}e_{2}+\dots+c_{k}e_{k}

for a unique tuple $(c_{1},\dots,c_{k})$ with each $c_{i}\in\mathbb{F}_{p}$ : existence because the $e_{i}$ span, uniqueness because coordinates with respect to a basis are unique (8). The assignment $(c_{1},\dots,c_{k})\mapsto\sum_{i}c_{i}e_{i}$ is therefore a bijection from $\mathbb{F}_{p}^{\,k}$ to $F$ , and counting tuples gives $\lvert F\rvert=p\cdot p\cdots p=p^{k}$ . □

Fields of every prime-power size do exist, and are unique; we state the fact in full, but prove only the part the series stands on.

Theorem 6.10 (Existence and uniqueness of $\mathbb{F}_{q}$ ).

For every prime power $q=p^{k}$ 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 $\mathbb{F}_{p}[x]/(f)$ of the polynomial ring by the ideal generated by an irreducible polynomial $f$ of degree $k$ —the recipe recorded in Example 4.22.

Remark 6.11.

The theorem is deliberately left unproved, and the omission costs the series nothing. The fields on the critical path of Halo 2 and Orchard are prime fields, the case $q=p$ with $k=1$ , and there the theorem is already proved: existence is 4.26, and uniqueness is immediate from the classification, since a field with $p$ elements has order $p^{k}=p$ with $k=1$ by 6.9, so it equals its own prime subfield, a copy of $\mathbb{F}_{p}$ (6.8). The general case $k\geq 2$ would require a development of polynomial factorisation over field extensions on which nothing later in the series relies, so we state it for orientation only. Convention, fixed henceforth: the letter $q=p^{k}$ denotes a prime power, and $\mathbb{F}_{q}$ a field with $q$ elements, of characteristic $p$ ; results are stated for general $\mathbb{F}_{q}$ whenever the proof is identical to the prime case, and the reader focused on Halo 2 may read $q=p$ throughout.

6.3 The Frobenius endomorphism

Characteristic $p$ is not merely a bookkeeping invariant; it changes what algebra is true. The most famous instance is the schoolroom error $(a+b)^{p}=a^{p}+b^{p}$ , false over $\mathbb{Q}$ and $\mathbb{R}$ for every $p\geq 2$ , which in characteristic $p$ becomes a theorem.

The proof expands $(a+b)^{p}$ by the binomial theorem, so we first fix its coefficients and their two readings.

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

Let $R$ be a commutative ring. For all $a,b\in R$ and every integer $n\geq 0$ ,

(a+b)^{n}\;=\;\sum_{k=0}^{n}\binom{n}{k}\,a^{k}b^{\,n-k},

where the integer coefficient $\binom{n}{k}$ acts as the additive multiple $\binom{n}{k}\cdot x=x+\dots+x$ , equals the number of $k$ -element subsets of an $n$ -element set, and satisfies

\binom{n}{k}=\frac{n!}{k!\,(n-k)!}.

Proof.

Expand the product $(a+b)^{n}=(a+b)\cdots(a+b)$ by distributivity without collecting terms: the result is a sum of $2^{n}$ products, one for each way of choosing, from every factor, either its $a$ or its $b$ . By commutativity such a product equals $a^{k}b^{n-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 $a^{k}b^{n-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)\cdots(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.13 (Freshman’s dream).

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

(a+b)^{p}=a^{p}+b^{p},

and more generally $(a+b)^{p^{n}}=a^{p^{n}}+b^{p^{n}}$ for every $n\geq 1$ .

Proof.

By the binomial theorem (6.12),

(a+b)^{p}\;=\;\sum_{i=0}^{p}\binom{p}{i}\,a^{i}b^{\,p-i},

where the integer coefficient $\binom{p}{i}$ acts as the additive multiple $\binom{p}{i}\cdot x=x+\dots+x$ . We claim that $p\mid\binom{p}{i}$ for $0<i<p$ . From the factorial identity of the same lemma

\binom{p}{i}\;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 $\binom{p}{i}$ , say $\binom{p}{i}=pm$ .

Now let $0<i<p$ and consider the corresponding term. Writing $\iota(n)=n\cdot 1_{R}$ for the canonical homomorphism of 4.5, the coefficient acts as multiplication by $\iota\bigl{(}\tbinom{p}{i}\bigr{)}=\iota(pm)=\iota(p)\,\iota(m)=0\cdot\iota(m)=0$ , since $\operatorname{char}(R)=p$ means exactly $\iota(p)=p\cdot 1_{R}=0$ . Every middle term of the binomial expansion therefore vanishes, and the terms $i=p$ and $i=0$ leave $(a+b)^{p}=a^{p}+b^{p}$ .

The general case follows by induction on $n$ , the base case $n=1$ being the identity just proved. For $n\geq 2$ , apply the base case to the elements $a^{p^{n-1}}$ and $b^{p^{n-1}}$ :

(a+b)^{p^{n}}=\bigl{(}(a+b)^{p^{n-1}}\bigr{)}^{p}=\bigl{(}a^{p^{n-1}}+b^{p^{n-% 1}}\bigr{)}^{p}=a^{p^{n}}+b^{p^{n}},

using the inductive hypothesis in the middle step. □

The identity says that in characteristic $p$ , raising to the $p$ -th power respects addition—and it obviously respects multiplication. A map respecting both operations is a homomorphism, and a homomorphism from a structure to itself is called an endomorphism; this one has a name of its own.

Definition 6.14 (Frobenius endomorphism).

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

\operatorname{Frob}\colon F\to F,\qquad\operatorname{Frob}(x)=x^{p}.

Proposition 6.15.

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

Proof.

Multiplicativity is commutativity and associativity alone: $(xy)^{p}=x^{p}y^{p}$ . Additivity is the freshman’s dream (Lemma 6.13), and $1^{p}=1$ ; so $\operatorname{Frob}$ is a ring homomorphism.

Injectivity holds for a reason worth isolating, since it recurs: every ring homomorphism between fields is injective. Indeed, if $\phi\colon F\to F^{\prime}$ had $\phi(x)=0$ for some $x\neq 0$ , then

1=\phi(1)=\phi(x^{-1}x)=\phi(x^{-1})\,\phi(x)=\phi(x^{-1})\cdot 0=0

in $F^{\prime}$ , contradicting $1\neq 0$ in a field. In particular $\operatorname{Frob}$ is injective.

The prime subfield is fixed pointwise. By 6.8 its elements are the values $\bar{\iota}([a]_{p})=a\cdot 1_{F}$ , and since $\bar{\iota}$ is a ring homomorphism,

\operatorname{Frob}\bigl{(}\bar{\iota}([a]_{p})\bigr{)}=\bar{\iota}([a]_{p})^{% p}=\bar{\iota}\bigl{(}[a]_{p}^{\,p}\bigr{)}=\bar{\iota}\bigl{(}[a^{p}]_{p}% \bigr{)}=\bar{\iota}([a]_{p}),

the last step because $a^{p}\equiv a\pmod{p}$ 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 device of 4.4—so $\operatorname{Frob}$ is a bijective ring homomorphism of $F$ onto itself, an automorphism. □

The iterates $\operatorname{Frob}^{n}(x)=x^{p^{n}}$ are again homomorphisms, as the general case of the freshman’s dream states directly. On the prime field $\mathbb{F}_{p}$ itself the Frobenius map is the identity; on larger fields of characteristic $p$ it is a genuine, structure-preserving symmetry, and 6.24 below records where it re-enters the cryptographic story.

6.4 Cyclicity of the multiplicative group

The multiplicative group $\mathbb{F}_{q}^{\times}$ of a finite field is a finite abelian group of order $q-1$ : every one of the $q-1$ nonzero elements is invertible, precisely because $\mathbb{F}_{q}$ is a field. Finite abelian groups can in general be quite far from cyclic—the unit group $(\mathbb{Z}/8\mathbb{Z})^{\times}$ of Example 3.22 has order $4$ with no element of order $4$ —so it is a genuinely strong fact that $\mathbb{F}_{q}^{\times}$ is always cyclic. The proof is a counting argument of Gauss, and its arithmetic engine is an identity about the totient function $\varphi$ . Everything we use about $\varphi$ is its counting definition (Definition 2.26): $\varphi(n)$ is the number of integers $a$ with $1\leq a\leq n$ and $\gcd(a,n)=1$ . No further totient theory is needed or assumed.

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

For every integer $n\geq 1$ ,

\sum_{d\mid n}\varphi(d)=n,

the sum running over the positive divisors $d$ of $n$ .

Proof.

Partition the set $\{1,2,\dots,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\leq a\leq n,\ \gcd(a,n)=d\,\},\qquad d\mid n,

are disjoint and cover $\{1,\dots,n\}$ ; hence $n=\sum_{d\mid n}\lvert C_{d}\rvert$ .

We claim $\lvert C_{d}\rvert=\varphi(n/d)$ . A member of $C_{d}$ is divisible by $d$ , so it has the form $a=db$ with $1\leq b\leq n/d$ ; we show that, for such $a$ ,

\gcd(db,n)=d\quad\Longleftrightarrow\quad\gcd(b,n/d)=1.

For the forward direction, suppose $e=\gcd(b,n/d)>1$ ; then $d e$ divides both $db=a$ and $d\cdot(n/d)=n$ , so $d e$ is a common divisor exceeding $d$ and $\gcd(a,n)\geq 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\geq 1$ . From $dc\mid db$ we get $c\mid b$ , and from $dc\mid n=d(n/d)$ we get $c\mid n/d$ (cancel $d$ in each divisibility); so $c$ divides $\gcd(b,n/d)=1$ , forcing $c=1$ and $g=d$ .

The members of $C_{d}$ are therefore exactly the integers $d b$ with $1\leq b\leq n/d$ and $\gcd(b,n/d)=1$ , and by the counting definition of the totient (Definition 2.26) there are precisely $\varphi(n/d)$ of them. Summing,

n=\sum_{d\mid n}\varphi\!\left(\frac{n}{d}\right)=\sum_{d\mid n}\varphi(d),

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

The theorem now follows from a beautiful squeeze. We count the elements of each possible order twice over—once inside the group, once through the totient—and Gauss’s identity leaves the two counts no room to differ.

Theorem 6.17 (Finite subgroups of $F^{\times}$ are cyclic).

Let $F$ be any field and let $G\leq F^{\times}$ be a finite subgroup of the multiplicative group, of order $N$ . Then $G$ is cyclic. In particular, for a finite field $\mathbb{F}_{q}$ the whole multiplicative group $\mathbb{F}_{q}^{\times}$ is cyclic of order $q-1$ .

Proof.

For each divisor $d\mid N$ , let

\psi(d)=\lvert\{\,a\in G:\operatorname{ord}(a)=d\,\}\rvert

count the elements of $G$ of order exactly $d$ . Every element of the finite group $G$ has finite order dividing $N=\lvert G\rvert$ (Corollary 3.30), so the sets counted by the $\psi(d)$ partition $G$ and

\sum_{d\mid N}\psi(d)=N.

(6)

The key claim is that for each $d\mid N$ , either $\psi(d)=0$ or $\psi(d)=\varphi(d)$ . Suppose $\psi(d)>0$ and choose $a\in G$ of order $d$ . The powers $a^{0},a^{1},\dots,a^{d-1}$ are $d$ distinct elements of $G$ (Proposition 3.12(3)), and each satisfies

\bigl{(}a^{j}\bigr{)}^{d}=\bigl{(}a^{d}\bigr{)}^{j}=1^{j}=1,

so each is a root in $F$ of the polynomial $X^{d}-1\in 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\in G$ of order $d$ . Then $b^{d}=1$ , so $b$ is a root of $X^{d}-1$ and hence $b=a^{j}$ for some $0\leq j<d$ . By Corollary 3.23,

\operatorname{ord}\bigl{(}a^{j}\bigr{)}=\frac{d}{\gcd(d,j)},

which equals $d$ exactly when $\gcd(j,d)=1$ . The elements of order $d$ in $G$ are thus precisely the powers $a^{j}$ with $0\leq j<d$ and $\gcd(j,d)=1$ , and by the counting definition of the totient there are $\varphi(d)$ of them: $\psi(d)=\varphi(d)$ . This proves the claim, and with it the inequality $\psi(d)\leq\varphi(d)$ for every $d\mid N$ .

Summing the inequality over the divisors of $N$ and comparing (6) with Gauss’s identity (Lemma 6.16),

N=\sum_{d\mid N}\psi(d)\;\leq\;\sum_{d\mid N}\varphi(d)=N.

The two ends are equal, so the inequality is an equality term by term: $\psi(d)=\varphi(d)$ for every divisor $d\mid N$ . In particular

\psi(N)=\varphi(N)\geq 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=\langle g\rangle$ is cyclic.

For the final statement, let $F=\mathbb{F}_{q}$ be finite. The multiplicative group $\mathbb{F}_{q}^{\times}$ 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$ . □

The equality $\psi(d)=\varphi(d)$ established along the way is worth extracting: it was proved for subgroups of a field’s multiplicative group, but it holds in any cyclic group, by the same gcd computation and with no field in sight.

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

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

Proof.

Write $G=\langle g\rangle$ with $\operatorname{ord}(g)=N$ ; the elements of $G$ are the powers $g^{j}$ , $0\leq j<N$ , each appearing once (Proposition 3.12(3)). By Corollary 3.23, $\operatorname{ord}(g^{j})=N/\gcd(N,j)$ , which is always a divisor of $N$ ; and $\operatorname{ord}(g^{j})=d$ if and only if $\gcd(j,N)=N/d$ . By the gcd computation in the proof of Lemma 6.16 (applied with $n=N$ and divisor $N/d$ ), the exponents $j\in\{1,\dots,N\}$ with $\gcd(j,N)=N/d$ are exactly $j=(N/d)\,t$ with $1\leq t\leq d$ and $\gcd(t,d)=1$ , of which there are $\varphi(d)$ by Definition 2.26. The generators are the elements of order $N$ , numbering $\varphi(N)$ . □

Definition 6.19 (Primitive root).

A generator of the cyclic group $\mathbb{F}_{q}^{\times}$ is called a primitive root (or primitive element) of $\mathbb{F}_{q}$ . Equivalently, an element $g\in\mathbb{F}_{q}^{\times}$ is primitive if and only if $\operatorname{ord}(g)=q-1$ .

Existence is 6.17, and the census refines it: $\mathbb{F}_{q}$ has exactly $\varphi(q-1)$ primitive roots (6.18), always at least one.

Remark 6.20.

The name has a second reading, developed later in the volume: a primitive root of $\mathbb{F}_{q}$ is precisely a primitive $(q-1)$ -th root of unity in the sense of 9.3, where the identification is restated once roots of unity have been defined in general. The two vocabularies—group-theoretic “generator of $\mathbb{F}_{q}^{\times}$ ” and polynomial-flavoured “primitive $(q-1)$ -th root of unity”—name the same elements.

Example 6.21 (Primitive roots of $\mathbb{F}_{7}$ ).

The group $\mathbb{F}_{7}^{\times}$ has order $6$ . Testing $g=3$ , the successive powers modulo $7$ are

3^{1}=3,\quad 3^{2}=2,\quad 3^{3}=6,\quad 3^{4}=4,\quad 3^{5}=5,\quad 3^{6}=1,

which run through all of $\{1,\dots,6\}$ : the element $3$ is a primitive root of $\mathbb{F}_{7}$ . By contrast $2$ is not: its powers are $2,4,1$ , so $\operatorname{ord}(2)=3<6$ . The full roster of primitive roots consists of the powers $3^{j}$ with $\gcd(j,6)=1$ (Corollary 3.23), namely $j=1$ and $j=5$ : the primitive roots of $\mathbb{F}_{7}$ are $3^{1}=3$ and $3^{5}=5$ , and there are $\varphi(6)=2$ of them, as the census predicts.

Cyclicity settles, in one stroke, how many solutions the equation $x^{n}=1$ has in a finite field—the question on which the evaluation domains of later sections turn.

Corollary 6.22 (Roots of unity in $\mathbb{F}_{q}$ ).

Let $\mathbb{F}_{q}$ be a finite field and $n\geq 1$ . The solutions of $x^{n}=1$ in $\mathbb{F}_{q}^{\times}$ number exactly $\gcd(n,q-1)$ , and they form the cyclic subgroup of $\mathbb{F}_{q}^{\times}$ of that order. In particular, when $n\mid q-1$ the equation has exactly $n$ solutions.

Proof.

Fix a primitive root $g$ (6.17) and write each element of $\mathbb{F}_{q}^{\times}$ uniquely as $x=g^{j}$ with $0\leq j\leq q-2$ (Proposition 3.12(3)). Then $x^{n}=g^{jn}$ , and $g^{jn}=1$ holds if and only if $(q-1)\mid jn$ (Proposition 3.12(1)). Set $d=\gcd(n,q-1)$ and write $q-1=dm$ , $n=dn^{\prime}$ with $\gcd(m,n^{\prime})=1$ . Then

(q-1)\mid jn\iff dm\mid j\,dn^{\prime}\iff m\mid jn^{\prime}\iff m\mid j,

the last step by Euclid’s lemma (Proposition 2.15(1), with $\gcd(m,n^{\prime})=1$ ). The qualifying exponents in $\{0,\dots,q-2\}$ are therefore the multiples of $m=(q-1)/d$ , namely $j=tm$ for $t=0,1,\dots,d-1$ : exactly $d$ of them. The corresponding solutions $x=(g^{m})^{t}$ are exactly the powers of $g^{m}$ , 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 $\langle g^{m}\rangle$ of order $d=\gcd(n,q-1)$ . When $n\mid q-1$ we have $d=n$ , giving exactly $n$ solutions. □

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

The corollary is precisely what renders a curve such as Pallas or Vesta suitable for Halo 2: one chooses the field size $q$ so that $q-1$ is divisible by a large power of $2$ , and the corollary then guarantees a multiplicative subgroup of $2$ -power order—the evaluation domain on which the number-theoretic transform, and hence efficient polynomial arithmetic, operates. The construction of these domains and the transform itself are the business of 9; the curves are introduced in 10.

Remark 6.24 (Cyclicity and Frobenius in cryptography).

The section’s two structural discoveries each carry cryptographic weight. First, the cyclicity of $\mathbb{F}_{q}^{\times}$ (6.17) underlies the discrete-logarithm problem—writing every nonzero element as $g^{j}$ invites the question of recovering $j$ , and the presumed hardness of doing so is a foundational assumption of later volumes—and, through 6.22, guarantees the existence of the roots of unity used in polynomial commitment schemes. Second, the Frobenius endomorphism (6.14) is not merely abstract: on an elliptic curve over $\mathbb{F}_{p}$ it induces an endomorphism of the curve whose characteristic polynomial $T^{2}-tT+p$ encodes the number of curve points as $N=p+1-t$ , where $t$ is the Hasse trace—tying the size of the cryptographic group directly to the field-theoretic Frobenius. Both connections are taken up in 10.

The question that opened the section is now answered in full. A finite arithmetic in which every nonzero element inverts exists only at prime-power sizes—6.9 forbids every other cardinality—and at each admissible size $q=p^{k}$ there is exactly one field, up to isomorphism (6.10). The machine’s own wrap-around arithmetic is instructive here: $2^{64}$ is a prime-power size, so a field with $2^{64}$ elements exists, but it is not the ring $\mathbb{Z}/2^{64}\mathbb{Z}$ of word arithmetic—whose even classes have no inverses—but the polynomial-quotient construction of 6.10, with a different multiplication altogether. The proof systems of this series instead take the prime route: a prime $p$ of roughly $255$ bits, the field $\mathbb{F}_{p}$ , inversion by 6.1 or 6.4. The payoff theorem then delivers the structure that everything later rides on: the multiplicative group of the chosen field is a single cycle, generated by one element, with exactly $\varphi(d)$ elements of each order $d\mid q-1$ and a guaranteed subgroup of every size dividing $q-1$ . Polynomials over these fields, the subject that the volume develops next into evaluation domains, fast transforms, and commitment schemes, will draw on that guarantee constantly.