Math Guide Mathematical foundations for Halo 2 and Zcash Orchard 4 Rings and fields 6 Finite fields

5 Polynomials over a field

Throughout this section $F$ denotes a field. Consider a problem that sounds impossible. Two parties each hold a polynomial of enormous degree—millions of coefficients, say, the encoding of an entire computation—and wish to convince themselves that the two polynomials are equal. Comparing coefficient lists costs as much as reading the computation itself. Could a single spot check suffice: pick one value $\alpha$ at random, evaluate both polynomials there, and declare them equal if the two field elements agree? The astonishing answer is yes—with an error probability so small that no adversary can exploit it—and this section develops exactly the algebra that makes the answer honest.

Polynomials are the engine behind finite fields, error-correcting codes, and—most importantly here—the polynomial commitment schemes and arithmetisation (the encoding of a computation as identities between polynomials) underlying Halo 2 and Zcash Orchard. The single most exploited fact in that edifice is elementary: a nonzero polynomial of degree $d$ over a field has at most $d$ roots. From this one fact the section extracts Lagrange interpolation and the Schwartz–Zippel principle, the probabilistic heart of every interactive proof we eventually construct. The only prerequisite is the field theory of the preceding section.

5.1 The polynomial ring

One point of principle governs everything that follows, so we state it before the first definition: a polynomial is not a function. It is a formal expression—at bottom, a finite list of coefficients—which one may evaluate to obtain a function, but which in general carries more information than that function. Over the finite fields of cryptographic interest the distinction is not pedantic but essential, and the closing subsections of this section (§5.9) return to it at length.

Definition 5.1 (Polynomial).

A polynomial over $F$ in the indeterminate $X$ is a formal expression

f\;=\;a_{0}+a_{1}X+a_{2}X^{2}+\dots+a_{n}X^{n}\;=\;\sum_{i=0}^{n}a_{i}X^{i},

where $n\in\mathbb{N}=\{0,1,2,\dots\}$ and the coefficients $a_{0},\dots,a_{n}$ lie in $F$ . Formally, $f$ is identified with its coefficient sequence $(a_{0},a_{1},a_{2},\dots)$ , in which only finitely many entries are nonzero. Two polynomials are equal precisely when their coefficient sequences agree term by term:

\sum_{i}a_{i}X^{i}=\sum_{i}b_{i}X^{i}\quad\Longleftrightarrow\quad a_{i}=b_{i}% \text{ for every }i\in\mathbb{N}.

The symbol $X$ is an indeterminate (a formal variable): it is not an element of $F$ and stands for nothing in particular; it is merely a placeholder organising the coefficients. The set of all polynomials over $F$ in $X$ is denoted $F[X]$ .

Remark 5.2 (The sequence model).

The fully rigorous rendering of 5.1 takes $F[X]$ to be the set of all functions $a\colon\mathbb{N}\to F$ that are eventually zero: there is some $N$ with $a(i)=0$ for all $i>N$ . The expression $\sum_{i}a_{i}X^{i}$ is then merely suggestive notation for the sequence $(a_{0},a_{1},\dots)$ . We use the two viewpoints interchangeably; the notation is justified because the arithmetic of these sequences, defined next, is exactly the arithmetic the notation suggests.

Definition 5.3 (Ring operations on $F[X]$ ).

Let $f=\sum_{i}a_{i}X^{i}$ and $g=\sum_{i}b_{i}X^{i}$ lie in $F[X]$ , with the shorter coefficient sequence zero-padded so that both run over the same index set. Their sum and product are

f+g\;=\;\sum_{i\geq 0}(a_{i}+b_{i})\,X^{i},\qquad fg\;=\;\sum_{k\geq 0}c_{k}X^% {k}\quad\text{where}\quad c_{k}\;=\;\sum_{i+j=k}a_{i}b_{j}\;=\;\sum_{i=0}^{k}a% _{i}b_{k-i}.

The coefficient $c_{k}$ is the convolution of the two coefficient sequences. Both defining sums are finite—only finitely many $a_{i}$ and $b_{j}$ are nonzero, hence only finitely many $c_{k}$ are nonzero—so the sum and the product are again polynomials.

The convolution formula is exactly what multiplying out $(\sum_{i}a_{i}X^{i})(\sum_{j}b_{j}X^{j})$ and collecting like powers of $X$ gives, using $X^{i}\cdot X^{j}=X^{i+j}$ . Stated as a convolution, however, it makes no appeal to substituting a value for $X$ : it is a purely formal manipulation of coefficient sequences. The formal/functional distinction announced above is thereby kept intact at the level of the operations themselves.

The verification that these operations obey the ring axioms (4.1) is a single device applied over and over: to prove an identity between polynomials, compute the coefficient of $X^{m}$ on each side as a finite sum over index decompositions, then reindex or regroup that sum. No evaluation is ever involved. The associativity step below is the archetype.

Theorem 5.4 ( $F[X]$ is a commutative ring).

With the operations of 5.3, the set $F[X]$ is a commutative ring whose additive identity is the zero polynomial $0=(0,0,0,\dots)$ and whose multiplicative identity is the constant polynomial $1=(1,0,0,\dots)$ . Moreover the map $c\mapsto(c,0,0,\dots)$ embeds $F$ into $F[X]$ as a subring, the constant polynomials; in this sense $F\subseteq F[X]$ .

Proof.

Additive structure. Addition is coordinatewise, so its commutativity and associativity are inherited directly from the corresponding laws of the additive group of $F$ , the sequence $(0,0,\dots)$ is an additive identity, and $(-a_{0},-a_{1},\dots)$ is an additive inverse of $(a_{0},a_{1},\dots)$ . Hence $(F[X],+)$ is an abelian group.

Commutativity of multiplication. The coefficient of $X^{k}$ in $f g$ is $\sum_{i+j=k}a_{i}b_{j}$ ; reindexing the sum by $(i,j)\mapsto(j,i)$ and using commutativity of multiplication in $F$ ,

\sum_{i+j=k}a_{i}b_{j}\;=\;\sum_{i+j=k}b_{i}a_{j},

which is the coefficient of $X^{k}$ in $g f$ .

Associativity of multiplication. Write $h=\sum_{l}c_{l}X^{l}$ . The coefficient of $X^{m}$ in $(fg)h$ is

\sum_{k+l=m}\Bigl{(}\sum_{i+j=k}a_{i}b_{j}\Bigr{)}c_{l}\;=\;\sum_{i+j+l=m}a_{i% }b_{j}c_{l},

and expanding $f(gh)$ instead produces $\sum_{i+j+l=m}a_{i}(b_{j}c_{l})$ , the same symmetric triple sum by associativity in $F$ . Hence $(fg)h=f(gh)$ coefficient by coefficient.

Distributivity. The coefficient of $X^{k}$ in $f(g+h)$ is $\sum_{i+j=k}a_{i}(b_{j}+c_{j})$ , which distributivity in $F$ splits as $\sum_{i+j=k}a_{i}b_{j}+\sum_{i+j=k}a_{i}c_{j}$ : the coefficient of $X^{k}$ in $fg+fh$ . The other distributive law follows from this one and commutativity.

Identity. With $1=(1,0,0,\dots)$ , the $k$ -th coefficient of $1\cdot f$ is $\sum_{i+j=k}\mathbf{1}[i=0]\,a_{j}=a_{k}$ , where $\mathbf{1}[i=0]$ denotes the coefficient sequence of $1$ (equal to $1$ at index $0$ and $0$ elsewhere); so $1\cdot f=f$ .

Embedding. Let $\iota(c)=(c,0,0,\dots)$ . The map $\iota$ preserves sums coordinatewise, and $\iota(c)\iota(d)$ has $k$ -th coefficient $c d$ for $k=0$ and $0$ otherwise, so $\iota(c)\iota(d)=\iota(cd)$ ; also $\iota(1)=1$ . Distinct constants give distinct sequences, so $\iota$ is an injective ring homomorphism (4.21) and its image is a subring of $F[X]$ isomorphic to $F$ . □

Remark 5.5 (Scalar multiplication).

Multiplying $f=\sum_{i}a_{i}X^{i}$ by a constant $c\in F$ , viewed as the constant polynomial $\iota(c)$ , gives the scalar multiple $cf=\sum_{i}(ca_{i})X^{i}$ . Together with addition, this makes $F[X]$ a vector space over $F$ —a structure studied systematically in the linear-algebra section later in the volume; informally, a system closed under addition and under scaling by field elements, in which the monomials $1,X,X^{2},X^{3},\dots$ play the role of an infinite coordinate system (a basis). This linear structure is relied on constantly, for instance whenever we count polynomials of bounded degree.

5.2 Degree

Definition 5.6 (Degree, leading coefficient, monic).

Let $f=\sum_{i}a_{i}X^{i}\in F[X]$ be nonzero. The degree $\deg f$ is the largest index $n$ with $a_{n}\neq 0$ ; the coefficient $a_{n}$ is the leading coefficient $\operatorname{lc}(f)$ , the term $a_{n}X^{n}$ is the leading term, and $a_{0}$ is the constant term. A nonzero polynomial is monic if its leading coefficient is $1$ . The constant polynomials are the elements of $F$ embedded by 5.4; the nonzero ones have degree $0$ . The zero polynomial is assigned $\deg 0=-\infty$ , with the conventions $-\infty<n$ , $-\infty+n=-\infty$ , and $-\infty+(-\infty)=-\infty$ for every $n\in\mathbb{Z}$ . Polynomials of degree $1$ , $2$ , and $3$ are called linear, quadratic, and cubic respectively.

The convention $\deg 0=-\infty$ is not pedantry: it makes the degree formulas below hold without exceptions, which streamlines every later induction on degree. Induction on degree is thereby set up as a reusable device for the rest of the volume.

Proposition 5.7 (Degree of sums and products).

For all $f,g\in F[X]$ ,

\deg(f+g)\;\leq\;\max\{\deg f,\deg g\},

(1)

with equality whenever $\deg f\neq\deg g$ , and

\deg(fg)\;=\;\deg f+\deg g.

(2)

Proof.

If either polynomial is zero, both statements reduce to the $-\infty$ conventions of 5.6. So let $f$ and $g$ be nonzero, of degrees $m$ and $n$ with leading coefficients $a_{m}$ and $b_{n}$ .

Sum. The coefficient of $X^{k}$ in $f+g$ is $a_{k}+b_{k}$ , which vanishes for $k>\max\{m,n\}$ ; this is (1). If $m>n$ , the coefficient of $X^{m}$ is $a_{m}+0=a_{m}\neq 0$ , giving equality (symmetrically for $n>m$ ). When $m=n$ , cancellation $a_{m}+b_{m}=0$ can lower the degree, which is why the sum bound is only an inequality.

Product. The coefficient $c_{m+n}=\sum_{i+j=m+n}a_{i}b_{j}$ has only the surviving term $i=m$ , $j=n$ : terms with $i>m$ have $a_{i}=0$ , and terms with $i<m$ force $j>n$ , so $b_{j}=0$ . Hence $c_{m+n}=a_{m}b_{n}$ , and the same argument shows $c_{k}=0$ for $k>m+n$ . Since $F$ is a field it has no zero divisors (4.28), so $a_{m}b_{n}\neq 0$ ; therefore $\deg(fg)=m+n$ and $\operatorname{lc}(fg)=\operatorname{lc}(f)\operatorname{lc}(g)$ . □

The product formula (2) is the first place the field hypothesis does real work: it required $a_{m}b_{n}\neq 0$ , that is, the absence of zero divisors in $F$ . This single fact has sweeping consequences for everything that follows, beginning with the next three corollaries.

Corollary 5.8 ( $F[X]$ is an integral domain).

The ring $F[X]$ has no zero divisors: if $fg=0$ , then $f=0$ or $g=0$ .

Proof.

If $f$ and $g$ are both nonzero, then $\deg(fg)=\deg f+\deg g\geq 0$ by (2), so $fg\neq 0$ . Contrapositively, $fg=0$ forces $f=0$ or $g=0$ . □

Corollary 5.9 (Cancellation).

Let $f,g,h\in F[X]$ with $h\neq 0$ . If $fh=gh$ , then $f=g$ .

Proof.

From $fh=gh$ we get $(f-g)h=0$ ; since $h\neq 0$ , 5.8 forces $f-g=0$ . □

Proposition 5.10 (Units of $F[X]$ ).

A polynomial $f\in F[X]$ is a unit—has a multiplicative inverse in $F[X]$ —if and only if it is a nonzero constant. Thus $F[X]^{\times}=F^{\times}$ .

Proof.

A nonzero constant $c$ has the inverse $c^{-1}\in F\subseteq F[X]$ . Conversely, $fg=1$ gives $\deg f+\deg g=\deg 1=0$ by (2); since degrees of nonzero polynomials are nonnegative, $\deg f=\deg g=0$ , and $f$ is a nonzero constant. □

Definition 5.11 (Associates).

Two polynomials $f,g\in F[X]$ are associates if $f=ug$ for some unit $u\in F^{\times}$ , that is, if they differ only by a nonzero scalar factor.

Every nonzero polynomial $f$ has exactly one monic associate, obtained by dividing through by its leading coefficient: $\operatorname{lc}(f)^{-1}f$ . Choosing the monic representative is the standard way to pin down the greatest common divisor or the irreducible factor uniquely, and we adopt this normalisation below.

5.3 Division with remainder

The arithmetic of $F[X]$ parallels that of the integers $\mathbb{Z}$ with remarkable fidelity: greatest common divisors, a Euclidean algorithm, a Bézout identity, primes (here called irreducibles), and unique factorisation all reappear. The source of the parallel is a single statement, division with remainder, in which degree plays the role that absolute value plays in $\mathbb{Z}$ .

Theorem 5.12 (Division algorithm).

Let $f,g\in F[X]$ with $g\neq 0$ . There exist unique polynomials $q,r\in F[X]$ such that

f=qg+r\qquad\text{and}\qquad\deg r<\deg g.

We call $q$ the quotient and $r$ the remainder, and write $q=f\operatorname{div}g$ and $r=f\bmod g$ .

Proof.

Existence. Fix $g$ , of degree $n$ with leading coefficient $b_{n}$ , and induct on $\deg f$ . If $\deg f<n$ —including $f=0$ with $\deg f=-\infty$ —take $q=0$ and $r=f$ . Otherwise let $m=\deg f\geq n$ , with leading coefficient $a_{m}$ , and form

f_{1}\;=\;f-\frac{a_{m}}{b_{n}}\,X^{m-n}\,g.

The subtracted term has degree $m$ and leading coefficient $(a_{m}/b_{n})\,b_{n}=a_{m}$ , so it cancels the leading term of $f$ : either $f_{1}=0$ or $\deg f_{1}<m$ . By the induction hypothesis $f_{1}=q_{1}g+r$ with $\deg r<n$ , and then $f=\bigl{(}q_{1}+(a_{m}/b_{n})X^{m-n}\bigr{)}g+r$ . The field hypothesis enters visibly here: division by the leading coefficient $b_{n}$ requires $b_{n}^{-1}$ to exist.

Uniqueness. Suppose $f=qg+r=q^{\prime}g+r^{\prime}$ with both remainders of degree $<n$ . Then $(q-q^{\prime})g=r^{\prime}-r$ . If $q\neq q^{\prime}$ , then $\deg\bigl{(}(q-q^{\prime})g\bigr{)}=\deg(q-q^{\prime})+n\geq n$ by (2), whereas $\deg(r^{\prime}-r)\leq\max\{\deg r^{\prime},\deg r\}<n$ by (1)—a contradiction. Hence $q=q^{\prime}$ , and then $r=f-qg=r^{\prime}$ . □

Remark 5.13 (Polynomial long division).

The existence proof is constructive, and it is precisely polynomial long division: repeatedly eliminate the current leading term by subtracting an appropriate monomial multiple of $g$ . Each step strictly lowers the degree of the running remainder, so the process terminates after at most $\deg f-\deg g+1$ steps when $\deg f\geq\deg g$ , and takes no steps when $f=0$ or $\deg f<\deg g$ . The device is reusable in both of its guises: as an algorithm, and as the leading-term-elimination pattern for inductions on degree.

For a concrete instance, divide $f=X^{3}+2X+1$ by $g=X^{2}+1$ over $\mathbb{Q}$ . Subtracting $X\cdot g=X^{3}+X$ leaves $X+1$ , whose degree $1$ is already below $\deg g=2$ ; hence $q=X$ and $r=X+1$ , and indeed

X^{3}+2X+1\;=\;X\,(X^{2}+1)+(X+1).

One elimination step suffices here.

Definition 5.14 (Divisibility).

For $f,g\in F[X]$ , we say $g$ divides $f$ , written $g\mid f$ , if $f=qg$ for some $q\in F[X]$ ; equivalently, for $g\neq 0$ , if the remainder $f\bmod g$ is $0$ . In that case $g$ is a divisor (or factor) of $f$ .

5.4 Roots and the factor theorem

The destination of this subsection is the central counting bound of the whole section, stated at once so that the reader knows what the machinery is for: a nonzero polynomial of degree $d$ over a field has at most $d$ distinct roots (5.18 below). Everything the volume later builds on polynomials—the cyclicity of the multiplicative group of a finite field, Lagrange interpolation, the Schwartz–Zippel principle—is load-bearing on this one fact. To reach it we must first say what a root is, and that requires making substitution precise: this is the first place where a polynomial gives rise to a function.

Definition 5.15 (Evaluation and roots).

Let $f=\sum_{i=0}^{n}a_{i}X^{i}\in F[X]$ and $\alpha\in F$ . The evaluation of $f$ at $\alpha$ is the field element

f(\alpha)\;=\;\sum_{i=0}^{n}a_{i}\alpha^{i}\;\in\;F,

obtained by substituting $\alpha$ for the indeterminate $X$ . An element $\alpha\in F$ is a root (or zero) of $f$ if $f(\alpha)=0$ .

Proposition 5.16 (Evaluation is a ring homomorphism).

Fix $\alpha\in F$ . The evaluation map $\operatorname{ev}_{\alpha}\colon F[X]\to F$ , $f\mapsto f(\alpha)$ , satisfies

(f+g)(\alpha)=f(\alpha)+g(\alpha),\qquad(fg)(\alpha)=f(\alpha)\,g(\alpha),% \qquad 1(\alpha)=1

for all $f,g\in F[X]$ ; that is, $\operatorname{ev}_{\alpha}$ is a ring homomorphism.

Proof.

Additivity is immediate from the coordinatewise definition of addition. For multiplicativity, with $c_{k}=\sum_{i+j=k}a_{i}b_{j}$ as in 5.3,

(fg)(\alpha)=\sum_{k}c_{k}\alpha^{k}=\sum_{k}\sum_{i+j=k}a_{i}b_{j}\,\alpha^{i% +j}=\Bigl{(}\sum_{i}a_{i}\alpha^{i}\Bigr{)}\Bigl{(}\sum_{j}b_{j}\alpha^{j}% \Bigr{)}=f(\alpha)\,g(\alpha),

the middle equality because expanding the product of the two finite sums and grouping terms by $k=i+j$ produces exactly the double sum. The formal reason evaluation respects the algebra is that the convolution defining polynomial multiplication collapses to ordinary multiplication in $F$ via $\alpha^{i}\alpha^{j}=\alpha^{i+j}$ . Finally $1(\alpha)=1$ by direct substitution. □

Theorem 5.17 (Remainder theorem; factor theorem).

Let $f\in F[X]$ and $\alpha\in F$ .

1.

(Remainder theorem.) The remainder of $f$ upon division by the linear polynomial $X-\alpha$ is the constant $f(\alpha)$ : there is $q\in F[X]$ with $f=q\,(X-\alpha)+f(\alpha)$ .
2.

(Factor theorem.) The element $\alpha$ is a root of $f$ if and only if $(X-\alpha)\mid f$ .

Proof.

(1) Divide $f$ by $X-\alpha$ (5.12): since $\deg(X-\alpha)=1$ , the remainder has degree $<1$ , hence is a constant $r\in F$ . Evaluating $f=q\,(X-\alpha)+r$ at $\alpha$ via 5.16 gives $f(\alpha)=q(\alpha)(\alpha-\alpha)+r=r$ .

(2) By (1) and the uniqueness of the remainder, $(X-\alpha)\mid f$ holds exactly when the remainder $f(\alpha)$ is $0$ , that is, when $\alpha$ is a root of $f$ . □

The factor theorem is an immediate but powerful consequence of the division algorithm: it converts a statement about values (a root) into a statement about divisibility (a linear factor). Iterating that conversion proves the promised bound.

Theorem 5.18 (At most $d$ roots).

A nonzero polynomial $f\in F[X]$ of degree $d$ has at most $d$ distinct roots in $F$ .

Proof.

We induct on $d=\deg f$ . If $d=0$ , then $f$ is a nonzero constant, which evaluates to itself everywhere and so has $0\leq d$ roots. Let $d\geq 1$ . If $f$ has no root in $F$ the claim holds; otherwise let $\alpha$ be a root. By the factor theorem, $f=(X-\alpha)\,q$ , and $\deg q=d-1$ by (2). Now let $\beta\neq\alpha$ be any other root of $f$ . Evaluating with 5.16,

0=f(\beta)=(\beta-\alpha)\,q(\beta);

since $\beta-\alpha\neq 0$ and $F$ has no zero divisors (4.28), we get $q(\beta)=0$ . Every root of $f$ other than $\alpha$ is therefore a root of $q$ , and by the induction hypothesis $q$ has at most $d-1$ distinct roots. Hence $f$ has at most $(d-1)+1=d$ . □

Remark 5.19 (Why a field is needed).

Both ingredients of the proof—the absence of zero divisors and the degree bookkeeping—are essential. Over a ring with zero divisors the bound fails outright: in $\mathbb{Z}/8\mathbb{Z}$ the quadratic $X^{2}-1$ has the four roots $\overline{1},\overline{3},\overline{5},\overline{7}$ , since $1^{2}=1$ , $3^{2}=9\equiv 1$ , $5^{2}=25\equiv 1$ , and $7^{2}=49\equiv 1\pmod{8}$ —a degree- $2$ polynomial with four roots. This is why the polynomial methods underlying Halo 2 require a field, and indeed a finite field $\mathbb{F}_{p}$ or $\mathbb{F}_{q}$ , beneath them.

Corollary 5.20 (Few points determine a low-degree polynomial).

Let $f,g\in F[X]$ both have degree at most $d$ . If $f(\alpha)=g(\alpha)$ for $d+1$ distinct values $\alpha\in F$ , then $f=g$ as polynomials.

Proof.

The difference $h=f-g$ has $\deg h\leq\max\{\deg f,\deg g\}\leq d$ by (1) and vanishes at $d+1$ distinct points. Were $h$ nonzero, it would be a polynomial of degree at most $d$ with $d+1$ distinct roots, contradicting 5.18. Hence $h=0$ , that is, $f=g$ . □

The corollary is the deterministic skeleton of two constructions developed later in this section: Lagrange interpolation (§5.7), its constructive converse, and the Schwartz–Zippel principle (§5.10), its probabilistic refinement. The root bound is thus positioned as the load-bearing fact behind the polynomial identity testing and interpolation machinery used by the proving system.

5.5 Greatest common divisors

Because $F[X]$ supports division with remainder, the entire theory of greatest common divisors from elementary number theory (§2) transfers verbatim from $\mathbb{Z}$ to $F[X]$ , with degree replacing absolute value as the measure that decreases. We run through the transfer explicitly, both because the statements are used constantly and because the polynomial Euclidean algorithm is itself a tool of the trade.

Definition 5.21 (Greatest common divisor).

Let $f,g\in F[X]$ , not both zero. A greatest common divisor of $f$ and $g$ is a polynomial $d$ such that

1.

$d\mid f$ and $d\mid g$ ; and
2.

every common divisor $c$ of $f$ and $g$ satisfies $c\mid d$ .

A greatest common divisor is determined only up to multiplication by a unit; the unique monic one (5.23) is singled out and denoted $\gcd(f,g)$ . When $\gcd(f,g)=1$ , the polynomials $f$ and $g$ are called coprime (or relatively prime). Since every polynomial divides $0$ , we have $\gcd(f,0)=\operatorname{lc}(f)^{-1}f$ for $f\neq 0$ .

Lemma 5.22 (Euclidean step).

Let $f,g\in F[X]$ with $g\neq 0$ , and let $f=qg+r$ be the division of 5.12. Then the pairs $(f,g)$ and $(g,r)$ have exactly the same common divisors; in particular, their greatest common divisors coincide.

Proof.

If $c\mid f$ and $c\mid g$ , then $c\mid(f-qg)=r$ ; so $c$ is a common divisor of $(g,r)$ . Conversely, if $c\mid g$ and $c\mid r$ , then $c\mid(qg+r)=f$ . The two sets of common divisors are therefore equal, hence so are their maximal elements under divisibility. □

Theorem 5.23 (Euclidean algorithm; Bézout’s identity).

Let $f,g\in F[X]$ , not both zero. Then $\gcd(f,g)$ exists and is unique as a monic polynomial, and there exist $s,t\in F[X]$ with

\gcd(f,g)\;=\;sf+tg.

(3)

Concretely: set $r_{0}=f$ and $r_{1}=g$ , and while $r_{i}\neq 0$ divide

r_{i-1}=q_{i}\,r_{i}+r_{i+1},\qquad\deg r_{i+1}<\deg r_{i}.

The degrees strictly decrease, so some $r_{N+1}=0$ ; the last nonzero remainder $r_{N}$ , made monic, is $\gcd(f,g)$ .

Proof.

Termination. If $r_{1}=0$ , the algorithm stops at once with $N=0$ and $r_{N}=f\neq 0$ . Otherwise the degrees $\deg r_{1}>\deg r_{2}>\dots$ form a strictly decreasing sequence of nonnegative integers, which cannot continue forever; so some $r_{N+1}=0$ with $r_{N}\neq 0$ .

The gcd property. 5.22, applied at each division, preserves the set of common divisors:

	$\displaystyle\{\text{common divisors of }(f,g)\}$	$\displaystyle=\{\text{common divisors of }(r_{1},r_{2})\}$
		$\displaystyle=\dots=\{\text{common divisors of }(r_{N},0)\},$

and the last set is exactly the set of divisors of $r_{N}$ , since every polynomial divides $0$ . Thus $r_{N}$ divides both $f$ and $g$ , and every common divisor of $f$ and $g$ divides $r_{N}$ : the monic associate $\operatorname{lc}(r_{N})^{-1}r_{N}$ is a monic greatest common divisor.

Uniqueness. Two monic greatest common divisors divide each other, so they differ by a unit $u\in F^{\times}$ (5.10); comparing leading coefficients of monic polynomials forces $u=1$ .

Bézout. We show by induction on $i$ that each remainder $r_{i}$ is an $F[X]$ -linear combination of $f$ and $g$ . The bases $r_{0}=1\cdot f+0\cdot g$ and $r_{1}=0\cdot f+1\cdot g$ are trivial, and the recurrence $r_{i+1}=r_{i-1}-q_{i}r_{i}$ expresses $r_{i+1}$ as a combination once $r_{i-1}$ and $r_{i}$ are. Hence $r_{N}=s_{0}f+t_{0}g$ for some $s_{0},t_{0}\in F[X]$ ; dividing through by $\operatorname{lc}(r_{N})$ yields (3). □

Remark 5.24 (Extended Euclidean algorithm).

Carrying the linear-combination coefficients along with the remainders, exactly as in the integer case (Theorem 2.13), produces $s$ and $t$ explicitly alongside the gcd. The standard application is inversion in a quotient $F[X]/(m)$ for irreducible $m$ : if $\gcd(f,m)=1$ , then $sf+tm=1$ , so $s$ is the inverse of $f$ modulo $m$ . This is how one divides in the extension fields $\mathbb{F}_{q}$ constructed in 6. The polynomial version matters both because it parallels the integer one exactly and because it computes gcds of the polynomials a proof system manipulates. A caveat on deployed practice: the curves of Halo 2 and Orchard are defined over prime fields $\mathbb{F}_{p}$ , not extension fields, and field inversion there uses the integer extended Euclidean algorithm (Theorem 2.13) or Fermat’s little theorem—not the polynomial algorithm in $F[X]/(m)$ .

Corollary 5.25 (Euclid’s lemma in $F[X]$ ).

Let $p,f,g\in F[X]$ .

1.

If $\gcd(p,f)=1$ and $p\mid fg$ , then $p\mid g$ .
2.

If $p$ is irreducible and $p\mid fg$ , then $p\mid f$ or $p\mid g$ .

Here irreducible is the polynomial analogue of prime, made precise in 5.26 below.

Proof.

(1) Multiplying the Bézout identity $sp+tf=1$ by $g$ gives $spg+tfg=g$ . The polynomial $p$ divides both terms on the left—the second because $p\mid fg$ —hence divides $g$ .

(2) Suppose $p\nmid f$ . The gcd $\gcd(p,f)$ is a monic divisor of $p$ that is not the monic associate of $p$ (otherwise $p\mid f$ ). By irreducibility the only monic divisors of $p$ are $1$ and its monic associate, so $\gcd(p,f)=1$ and part (1) applies. □

5.6 Unique factorisation

Definition 5.26 (Irreducible polynomial).

A polynomial $p\in F[X]$ is irreducible over $F$ if $\deg p\geq 1$ and $p$ admits no factorisation $p=gh$ with both $\deg g\geq 1$ and $\deg h\geq 1$ ; equivalently, $p$ is nonconstant and its only factorisations are the trivial ones, $(\text{unit})\times(\text{associate of }p)$ . A nonconstant polynomial that is not irreducible is reducible.

Remark 5.27 (Irreducibility is relative to the base field).

The polynomial $X^{2}+1$ is irreducible over $\mathbb{R}$ (it has no real root, and a real quadratic factors precisely when it has a root, by the test below), yet splits as $(X-i)(X+i)$ over $\mathbb{C}$ , and factors as $(X+1)^{2}$ over $\mathbb{F}_{2}$ , by direct expansion in characteristic $2$ . Degree- $1$ polynomials are irreducible over every field. A useful rootlessness test: a polynomial of degree $2$ or $3$ is irreducible over $F$ if and only if it has no root in $F$ , because any nontrivial factorisation of a quadratic or cubic must include a linear factor, which by the factor theorem (5.17) supplies a root. The test fails from degree $4$ onward: a product of two irreducible quadratics has no roots yet is reducible.

Theorem 5.28 ( $F[X]$ is a unique factorisation domain).

Every nonconstant $f\in F[X]$ factors as

f\;=\;c\,p_{1}p_{2}\cdots p_{k}

with $c=\operatorname{lc}(f)\in F^{\times}$ a constant and each $p_{i}$ monic irreducible. The factorisation is unique up to order: if also $f=c^{\prime}\,q_{1}\cdots q_{l}$ with $c^{\prime}\in F^{\times}$ and each $q_{j}$ monic irreducible, then $c=c^{\prime}$ , $k=l$ , and the $q_{j}$ are a reordering of the $p_{i}$ .

Proof.

The proof is templated on the fundamental theorem of arithmetic (Theorem 2.18), with degree in place of absolute value.

Existence, by induction on $\deg f\geq 1$ . If $f$ is irreducible, then $f=\operatorname{lc}(f)\cdot p_{1}$ with $p_{1}$ its monic associate. If $f=gh$ is reducible with $1\leq\deg g,\deg h<\deg f$ , the induction hypothesis factors $g$ and $h$ , and multiplying the two factorisations—collecting the two constants into one—factors $f$ .

Uniqueness. Comparing leading coefficients in the two factorisations gives $c=c^{\prime}=\operatorname{lc}(f)$ , since monic factors contribute leading coefficient $1$ by (2). Cancelling the constants (5.9) leaves $p_{1}\cdots p_{k}=q_{1}\cdots q_{l}$ ; we induct on $k$ . For $k=1$ the left side is irreducible, so $l=1$ and $p_{1}=q_{1}$ . For $k\geq 2$ : $p_{1}$ divides $q_{1}\cdots q_{l}$ , so iterating Euclid’s lemma (5.25(2)) gives $p_{1}\mid q_{j}$ for some $j$ . A monic irreducible dividing a monic irreducible equals it: $q_{j}=p_{1}h$ forces $\deg h=0$ by irreducibility of $q_{j}$ , and comparing leading coefficients gives $h=1$ . Cancel $p_{1}=q_{j}$ from both sides (5.9). If $l=1$ , the cancellation leaves $p_{2}\cdots p_{k}=1$ , which is impossible: the left side is a product of $k-1\geq 1$ nonconstant polynomials and so has degree at least $1$ by (2), while $\deg 1=0$ . Hence $l\geq 2$ , and the induction hypothesis, applied to $p_{2}\cdots p_{k}=\prod_{j^{\prime}\neq j}q_{j^{\prime}}$ , concludes $k=l$ and matches the remaining factors. □

Remark 5.29 (The structural reason: $F[X]$ is a PID).

The deeper explanation of unique factorisation is structural. The degree function and 5.12 make $F[X]$ a Euclidean domain—an integral domain with division with remainder relative to a size measure—and every Euclidean domain is a principal ideal domain (PID): each ideal (4.17) of $F[X]$ is $(g)=\{\,qg:q\in F[X]\,\}$ for a single generator $g$ , namely any nonzero element of least degree in a nonzero ideal (the zero ideal is generated by $0$ ), by the same division-and-minimality argument that proved every ideal of $\mathbb{Z}$ principal (Example 4.18(2)). The generator of the ideal $\{\,sf+tg:s,t\in F[X]\,\}$ is a gcd of $f$ and $g$ , and Bézout’s identity (3) is the concrete shadow of this principality. The standard chain

\text{Euclidean}\;\Longrightarrow\;\text{PID}\;\Longrightarrow\;\text{UFD}

has thus been walked explicitly for $F[X]$ , ending at 5.28.

5.7 Lagrange interpolation

The corollary “few points determine a low-degree polynomial” (5.20) says that a polynomial of degree at most $d$ is pinned down by its values at $d+1$ points. The present subsection proves the constructive converse: any $d+1$ prescribed values at distinct points are attained by exactly one polynomial of degree at most $d$ , and there is an explicit formula for it. This is the algebraic backbone of secret sharing, of Reed–Solomon error-correcting codes, and of the polynomial encodings in Halo 2.

Theorem 5.30 (Lagrange interpolation).

Let $x_{0},\dots,x_{d}\in F$ be distinct (the nodes) and let $y_{0},\dots,y_{d}\in F$ be arbitrary targets. There exists a unique $f\in F[X]$ with $\deg f\leq d$ and $f(x_{i})=y_{i}$ for all $i$ , given explicitly by

f(X)\;=\;\sum_{i=0}^{d}y_{i}\,\ell_{i}(X),\qquad\text{where}\qquad\ell_{i}(X)% \;=\;\prod_{j\neq i}\frac{X-x_{j}}{x_{i}-x_{j}}

are the Lagrange basis polynomials for the nodes.

Proof.

The $\ell_{i}$ are genuine polynomials. Each denominator $\prod_{j\neq i}(x_{i}-x_{j})$ is a product of nonzero field elements, the nodes being distinct, hence is an invertible constant; so $\ell_{i}$ is a polynomial, of degree exactly $d$ (a product of $d$ linear factors divided by a nonzero constant).

The delta property. Writing $\delta_{im}$ for the Kronecker symbol (equal to $1$ if $i=m$ and $0$ otherwise),

\ell_{i}(x_{m})\;=\;\delta_{im}\qquad(0\leq i,m\leq d):

(4)

at $m=i$ every factor $(x_{i}-x_{j})/(x_{i}-x_{j})$ is $1$ , while at $m\neq i$ the factor with $j=m$ has numerator $x_{m}-x_{m}=0$ . Consequently $f(x_{m})=\sum_{i}y_{i}\,\ell_{i}(x_{m})=y_{m}$ for each $m$ , and $\deg f\leq d$ by (1), each summand having degree at most $d$ .

Uniqueness. Two interpolants of degree at most $d$ agree at the $d+1$ distinct nodes, hence are equal by 5.20. □

Example 5.31 (A worked interpolation over $\mathbb{Q}$ ).

Find the polynomial of degree at most $2$ with $f(0)=1$ , $f(1)=3$ , and $f(2)=7$ . The basis polynomials for the nodes $0,1,2$ are

	$\displaystyle\ell_{0}$	$\displaystyle=\frac{(X-1)(X-2)}{(0-1)(0-2)}=\frac{(X-1)(X-2)}{2},$
	$\displaystyle\ell_{1}$	$\displaystyle=\frac{(X-0)(X-2)}{(1-0)(1-2)}=-X(X-2),$
	$\displaystyle\ell_{2}$	$\displaystyle=\frac{(X-0)(X-1)}{(2-0)(2-1)}=\frac{X(X-1)}{2}.$

Hence

f\;=\;1\cdot\ell_{0}+3\cdot\ell_{1}+7\cdot\ell_{2}\;=\;\tfrac{1}{2}(X^{2}-3X+2% )+3(2X-X^{2})+\tfrac{7}{2}(X^{2}-X)\;=\;X^{2}+X+1,

and indeed $f(0)=1$ , $f(1)=3$ , $f(2)=7$ .

Remark 5.32 (The evaluation isomorphism).

Fix $d+1$ distinct nodes and let $V=\{\,f\in F[X]:\deg f\leq d\,\}$ . In the language of the linear-algebra section later in the volume, $V$ is a $(d+1)$ -dimensional vector space over $F$ with basis $1,X,\dots,X^{d}$ , and the evaluation map

\operatorname{ev}\colon V\to F^{d+1},\qquad f\longmapsto\bigl{(}f(x_{0}),\dots% ,f(x_{d})\bigr{)},

is $F$ -linear. Its surjectivity is exactly the existence half of 5.30, and its injectivity exactly the uniqueness half; so $\operatorname{ev}$ is a linear isomorphism $V\cong F^{d+1}$ . The Lagrange basis $\{\ell_{i}\}$ is precisely the basis of $V$ matched to the standard coordinates of $F^{d+1}$ , by the delta property (4): the polynomial with prescribed values $(y_{0},\dots,y_{d})$ has coordinates $(y_{0},\dots,y_{d})$ in the basis $\{\ell_{i}\}$ . This switching between a polynomial’s coefficient representation and its evaluation representation is the conceptual core of fast polynomial arithmetic via the fast Fourier transform, treated with the roots of unity later in the volume, and of the evaluation-domain encodings used throughout Halo 2.

Remark 5.33 (The vanishing polynomial).

The companion object to the Lagrange basis is the vanishing polynomial of the node set $\{x_{0},\dots,x_{d}\}$ ,

Z(X)\;=\;\prod_{i=0}^{d}(X-x_{i}),

the unique monic polynomial of degree $d+1$ vanishing at every node. A polynomial $g$ vanishes on the whole node set if and only if $Z\mid g$ . One direction is immediate from 5.16. For the other, apply the factor theorem repeatedly: $g(x_{0})=0$ gives $g=(X-x_{0})\,g_{1}$ ; evaluating at $x_{1}\neq x_{0}$ gives $0=(x_{1}-x_{0})\,g_{1}(x_{1})$ , so $g_{1}(x_{1})=0$ since $F$ has no zero divisors, and $g_{1}=(X-x_{1})\,g_{2}$ ; continuing through the remaining nodes strips off one linear factor per node. The repetition is legitimate precisely because the nodes are distinct—the linear factors $X-x_{i}$ are pairwise coprime. The pair (Lagrange basis, vanishing polynomial) is exactly the data a proof system manipulates when arguing that a committed polynomial agrees with prescribed values on an evaluation domain.

5.8 Multiplicity and the formal derivative

A root can be a root “several times over”: the quadratic $X^{2}-2X+1=(X-1)^{2}$ vanishes at $1$ doubly. Counting roots correctly requires making that idea precise, and detecting it requires a derivative—which we define with no limits at all.

Definition 5.34 (Multiplicity of a root).

Let $f\in F[X]$ be nonzero and let $\alpha\in F$ be a root of $f$ . The multiplicity $\operatorname{mult}_{\alpha}(f)$ is the largest integer $m\geq 1$ with $(X-\alpha)^{m}\mid f$ . A root of multiplicity $1$ is simple; a root of multiplicity at least $2$ is repeated (or multiple).

The largest such $m$ exists: the powers $(X-\alpha)^{m}$ have strictly increasing degrees, so only finitely many can divide the fixed $f$ , and at least one does by the factor theorem. An equivalent characterisation is often handier: $m=\operatorname{mult}_{\alpha}(f)$ exactly when $f=(X-\alpha)^{m}g$ with $g(\alpha)\neq 0$ . Indeed, writing $f=(X-\alpha)^{m}g$ with $m$ maximal forces $g(\alpha)\neq 0$ , else the factor theorem would split a further factor $X-\alpha$ off $g$ ; conversely, if $f=(X-\alpha)^{m}g$ with $g(\alpha)\neq 0$ , then $(X-\alpha)^{m+1}\mid f$ would give $(X-\alpha)^{m}g=(X-\alpha)^{m+1}h$ , and cancelling (5.9) $g=(X-\alpha)h$ , making $\alpha$ a root of $g$ .

The count of roots with multiplicity still respects the degree. The proof rests on a small device worth isolating, since it recurs.

Lemma 5.35 (Coprime factors multiply).

Let $f_{1},\dots,f_{r}\in F[X]$ be pairwise coprime ( $\gcd(f_{i},f_{j})=1$ for $i\neq j$ ) and suppose each $f_{i}$ divides $f$ . Then $f_{1}f_{2}\cdots f_{r}\mid f$ .

Proof.

First let $r=2$ , and write $f=f_{1}u=f_{2}v$ . Bézout (3) gives $sf_{1}+tf_{2}=1$ , so

f\;=\;sf_{1}f+tf_{2}f\;=\;sf_{1}(f_{2}v)+tf_{2}(f_{1}u)\;=\;f_{1}f_{2}\,(sv+tu),

and $f_{1}f_{2}\mid f$ . For $r>2$ , induct: by hypothesis $f_{1}\cdots f_{r-1}\mid f$ , and the product $f_{1}\cdots f_{r-1}$ is coprime to $f_{r}$ —a nonconstant common divisor would have a monic irreducible factor (5.28), which by Euclid’s lemma (5.25(2)) would divide some $f_{i}$ with $i<r$ as well as $f_{r}$ , contradicting $\gcd(f_{i},f_{r})=1$ . Now apply the case $r=2$ . □

Proposition 5.36 (Counting roots with multiplicity).

Let $f\in F[X]$ be nonzero of degree $d$ , with all its distinct roots $\alpha_{1},\dots,\alpha_{r}\in F$ of multiplicities $m_{1},\dots,m_{r}$ . Then

f\;=\;(X-\alpha_{1})^{m_{1}}\cdots(X-\alpha_{r})^{m_{r}}\,g

for some $g\in F[X]$ with no roots in $F$ , and $\sum_{i}m_{i}\leq d$ . The number of roots counted with multiplicity is thus at most $d$ , with equality if and only if $f$ splits into linear factors over $F$ .

Proof.

We first check that the powers $(X-\alpha_{i})^{m_{i}}$ are pairwise coprime. Each $X-\alpha_{i}$ is monic irreducible (degree $1$ ), and by unique factorisation the monic divisors of $(X-\alpha_{i})^{m_{i}}$ are exactly the powers $(X-\alpha_{i})^{e}$ with $0\leq e\leq m_{i}$ . For $i\neq j$ the only monic polynomial that is simultaneously a power of $X-\alpha_{i}$ and of $X-\alpha_{j}$ is $1$ , since $X-\alpha_{i}=X-\alpha_{j}$ would force $\alpha_{i}=\alpha_{j}$ ; so $\gcd\bigl{(}(X-\alpha_{i})^{m_{i}},(X-\alpha_{j})^{m_{j}}\bigr{)}=1$ .

Each $(X-\alpha_{i})^{m_{i}}$ divides $f$ by the definition of multiplicity, so 5.35 gives $f=(X-\alpha_{1})^{m_{1}}\cdots(X-\alpha_{r})^{m_{r}}\,g$ . Maximality of each $m_{i}$ gives $g(\alpha_{i})\neq 0$ : a further factor $X-\alpha_{i}$ inside $g$ would raise the multiplicity. And $g$ has no other roots either: a root $\beta$ of $g$ is a root of $f$ , hence one of the $\alpha_{i}$ . Taking degrees with (2),

m_{1}+\dots+m_{r}+\deg g\;=\;d,

so $\sum_{i}m_{i}\leq d$ , with equality precisely when $\deg g=0$ , that is, when $f$ is a constant times a product of linear factors. □

Definition 5.37 (Formal derivative).

The formal derivative is the map $D\colon F[X]\to F[X]$ defined on $f=\sum_{i=0}^{n}a_{i}X^{i}$ by

f^{\prime}\;=\;Df\;=\;\sum_{i=1}^{n}i\,a_{i}\,X^{i-1}\;=\;a_{1}+2a_{2}X+\dots+% na_{n}X^{n-1},

where the coefficient $i\,a_{i}$ means $a_{i}$ added to itself $i$ times in $F$ —that is, $a_{i}$ multiplied by the image of the integer $i$ under the canonical map $\mathbb{Z}\to F$ (4.30). No limits are involved: the definition is purely formal and algebraic, valid over any field, and it is introduced for one purpose—to detect repeated roots without any appeal to analysis.

Proposition 5.38 (Rules of formal differentiation).

For all $f,g\in F[X]$ , $c\in F$ , $\alpha\in F$ , and $m\geq 1$ :

1.

(Linearity.) $(f+g)^{\prime}=f^{\prime}+g^{\prime}$ and $(cf)^{\prime}=cf^{\prime}$ .
2.

(Product rule.) $(fg)^{\prime}=f^{\prime}g+fg^{\prime}$ .
3.

(Power rule.) $\bigl{(}(X-\alpha)^{m}\bigr{)}^{\prime}=m\,(X-\alpha)^{m-1}$ .

Proof.

(1) is immediate from the coordinatewise, visibly linear definition of $D$ .

(2) Both sides are bilinear in the pair $(f,g)$ : by part (1), each is linear in $f$ with $g$ fixed and linear in $g$ with $f$ fixed. It therefore suffices to verify the identity on monomials $f=X^{a}$ , $g=X^{b}$ , since every polynomial is a linear combination of monomials and the general case follows by expanding $f=\sum_{a}u_{a}X^{a}$ , $g=\sum_{b}v_{b}X^{b}$ and applying the monomial case termwise. On monomials,

(X^{a}X^{b})^{\prime}=(X^{a+b})^{\prime}=(a+b)\,X^{a+b-1}=aX^{a-1}X^{b}+X^{a}% \,bX^{b-1}=(X^{a})^{\prime}X^{b}+X^{a}(X^{b})^{\prime},

with the convention that a term carrying the integer coefficient $0$ (the case $a=0$ or $b=0$ ) is the zero polynomial.

(3) Induct on $m$ . The base is $(X-\alpha)^{\prime}=1$ . For the step, the product rule gives

\bigl{(}(X-\alpha)^{m}\bigr{)}^{\prime}=\bigl{(}(X-\alpha)(X-\alpha)^{m-1}% \bigr{)}^{\prime}=(X-\alpha)^{m-1}+(X-\alpha)\,(m-1)(X-\alpha)^{m-2}=m\,(X-% \alpha)^{m-1}.\qed

Part (3) of the next theorem must exhibit a repeated root inside an extension field that is not given in advance; the following lemma manufactures the required extension. It is the quotient recipe of Example 4.22 carried out for polynomial rings, and the proof is the argument that made $\mathbb{Z}/p\mathbb{Z}$ a field (4.26), transposed from $\mathbb{Z}$ to $F[X]$ .

Lemma 5.39 (Adjoining a root).

Let $h\in F[X]$ be irreducible. Then the quotient ring $K=F[X]/(h)$ is a field; the map $a\mapsto a+(h)$ embeds $F$ into $K$ as a subfield, so that $K$ is an extension of $F$ ; and the class $\alpha=X+(h)$ is a root of $h$ in $K$ .

Proof.

The principal ideal $(h)=hF[X]$ is an ideal of the commutative ring $F[X]$ (Example 4.18(2)), so $K$ is a commutative ring under the coset operations (4.20). Its identity is not zero: $1+(h)=0+(h)$ would say $h\mid 1$ , impossible since a factorisation $1=hk$ has degree $\deg h+\deg k=0$ by (2), while $\deg h\geq 1$ .

Every nonzero class is a unit. Let $f+(h)\neq 0+(h)$ , i.e. $h\nmid f$ . The gcd $\gcd(h,f)$ is then a monic divisor of the irreducible $h$ other than its monic associate, hence equals $1$ , exactly as in the proof of 5.25(2); Bézout’s identity (3) supplies $s,t\in F[X]$ with $sf+th=1$ , and reducing modulo $(h)$ gives $(s+(h))(f+(h))=1+(h)$ . So $K$ is a field.

The map $\iota(a)=a+(h)$ on constants preserves sums, products, and $1$ directly from the coset operations of 4.19, and it is injective: $\iota(a)=0$ with $a\neq 0$ would make $h$ divide a nonzero constant, again impossible by degrees. We identify $F$ with its image, making $K$ an extension field of $F$ .

Finally, write $h=\sum_{i}c_{i}X^{i}$ and compute in $K$ :

h(\alpha)=\sum_{i}\iota(c_{i})\,\bigl{(}X+(h)\bigr{)}^{i}=\Bigl{(}\sum_{i}c_{i% }X^{i}\Bigr{)}+(h)=h+(h)=0+(h),

so $\alpha$ is a root of $h$ in $K$ . □

Theorem 5.40 (Derivative test for repeated roots; separability).

Let $f\in F[X]$ be nonzero and $\alpha\in F$ .

1.

The element $\alpha$ is a repeated root of $f$ —a root of multiplicity at least $2$ —if and only if $f(\alpha)=0$ and $f^{\prime}(\alpha)=0$ .
2.

If $f$ has a repeated root in $F$ , then $\gcd(f,f^{\prime})\neq 1$ .
3.

Call $f$ separable if it has no repeated root in any field containing $F$ . Then $f$ is separable if and only if $\gcd(f,f^{\prime})=1$ in $F[X]$ .

Proof.

(1) Let $\alpha$ be a root of multiplicity $m\geq 1$ and write $f=(X-\alpha)^{m}g$ with $g(\alpha)\neq 0$ . The product and power rules give

f^{\prime}\;=\;m\,(X-\alpha)^{m-1}g+(X-\alpha)^{m}g^{\prime}\;=\;(X-\alpha)^{m% -1}\,\bigl{[}\,mg+(X-\alpha)\,g^{\prime}\,\bigr{]}.

If $m=1$ , the first factor is $1$ and evaluating at $\alpha$ gives $f^{\prime}(\alpha)=1\cdot g(\alpha)=g(\alpha)\neq 0$ : a simple root of $f$ is not a root of $f^{\prime}$ . If $m\geq 2$ , then $(X-\alpha)^{m-1}$ divides $f^{\prime}$ and vanishes at $\alpha$ , so $f^{\prime}(\alpha)=0$ . Together with the factor theorem for $f(\alpha)=0$ , this proves the equivalence.

(2) A repeated root $\alpha\in F$ is a common root of $f$ and $f^{\prime}$ by (1), so the factor theorem puts the common factor $X-\alpha$ into both, and $(X-\alpha)\mid\gcd(f,f^{\prime})$ .

(3) The key observation is that gcds are stable under field extension: for an extension field $K$ of $F$ (4.25), the Euclidean algorithm of 5.23 run on $f,f^{\prime}\in F[X]$ uses only field operations on their coefficients, which lie in $F$ ; run inside $K[X]$ on the same inputs it produces the identical quotients and remainders. Hence the gcd computed in $K[X]$ equals the gcd computed in $F[X]$ .

Suppose $\gcd(f,f^{\prime})=1$ in $F[X]$ , and let $K\supseteq F$ be any extension. By stability, $\gcd(f,f^{\prime})=1$ in $K[X]$ as well, so by (2) applied over $K$ , the polynomial $f$ has no repeated root in $K$ : $f$ is separable.

Conversely, suppose $d=\gcd(f,f^{\prime})$ is nonconstant; we exhibit a repeated root in some extension. Let $h$ be a monic irreducible factor of $d$ (5.28), and let $K=F[X]/(h)$ be the extension field supplied by 5.39, in which $h$ has a root $\alpha$ . The polynomial $h$ divides $d$ , which divides both $f$ and $f^{\prime}$ ; evaluating the factorisations at $\alpha$ (5.16) gives $f(\alpha)=f^{\prime}(\alpha)=0$ . By (1), applied over $K$ , the element $\alpha$ is a repeated root of $f$ in $K$ : $f$ is not separable. □

The stability observation in the proof deserves emphasis as a technique: it licenses testing separability—the absence of repeated roots in every extension of the base field at once—by a gcd computation carried out entirely in the base field.

Remark 5.41 (The pitfall of positive characteristic).

The integer coefficient $i$ in $f^{\prime}=\sum_{i}i\,a_{i}X^{i-1}$ is interpreted in $F$ , and may vanish there. Over a field of characteristic $p$ —where $p=0$ in $F$ , $p$ prime, the setting of $\mathbb{F}_{p}$ and $\mathbb{F}_{q}$ (4.30)—the derivative of $X^{p}$ is $p\,X^{p-1}=0$ . Thus $f=X^{p}-1$ over $\mathbb{F}_{p}$ has $f^{\prime}=0$ and $\gcd(f,f^{\prime})=\gcd(f,0)=f\neq 1$ ; and indeed

X^{p}-1\;=\;(X-1)^{p}\quad\text{in }\mathbb{F}_{p}[X],

a factorisation the finite-fields section establishes through the freshman’s-dream identity $(a+b)^{p}=a^{p}+b^{p}$ of characteristic $p$ (6.13, applied to $(X+(-1))^{p}$ together with $(-1)^{p}=-1$ in every $\mathbb{F}_{p}$ ): a single root $1$ of multiplicity $p$ . This characteristic- $p$ behaviour is a structural feature to respect when working over the finite fields of Orchard, not a pathology to avoid.

5.9 Polynomials versus polynomial functions

The opening of this section insisted that a polynomial is not a function. The debt of that insistence now falls due: we make the relationship precise and show exactly when it is safe—and when it is not—to conflate the two.

Definition 5.42 (Polynomial function).

Every $f\in F[X]$ induces a polynomial function

\tilde{f}\colon F\to F,\qquad\alpha\longmapsto f(\alpha).

The assignment $f\mapsto\tilde{f}$ is a ring homomorphism from $F[X]$ to the ring $F^{F}$ of all functions $F\to F$ under pointwise operations ( $(u+v)(\alpha)=u(\alpha)+v(\alpha)$ and $(uv)(\alpha)=u(\alpha)v(\alpha)$ ), by 5.16 applied at every point.

Proposition 5.43 (When formal equals functional).

Let $f,g\in F[X]$ .

1.

If $F$ is infinite, then $\tilde{f}=\tilde{g}$ as functions implies $f=g$ as polynomials. Equivalently, $f\mapsto\tilde{f}$ is injective, and polynomials over an infinite field may be identified with polynomial functions.
2.

If $F$ is finite, the map is not injective. Over $\mathbb{F}_{p}$ , the nonzero polynomial $X^{p}-X$ induces the zero function, since Fermat’s little theorem (Corollary 3.32) gives $\alpha^{p}=\alpha$ for every $\alpha\in\mathbb{F}_{p}$ .

Proof.

(1) Let $h=f-g$ , so that $\tilde{h}$ is the zero function: $h$ vanishes at every point of the infinite set $F$ . Were $h$ nonzero of degree $d$ , it would have at most $d$ roots (5.18), yet it has infinitely many—a contradiction. Hence $h=0$ .

(2) Let $F$ be finite, with $q=\lvert F\rvert$ elements, and consider the vanishing-polynomial witness

w(X)\;=\;\prod_{\alpha\in F}(X-\alpha),

a monic polynomial of degree $q$ —in particular nonzero as a formal object—which vanishes at every point of $F$ by construction. Thus $\tilde{w}=\tilde{0}$ while $w\neq 0$ : the map $f\mapsto\tilde{f}$ identifies distinct polynomials. Over $F=\mathbb{F}_{p}$ the witness specialises to $X^{p}-X$ : by Fermat’s little theorem every element of $\mathbb{F}_{p}$ is a root of the monic degree- $p$ polynomial $X^{p}-X$ , so 5.36 factors it as $\prod_{\alpha\in\mathbb{F}_{p}}(X-\alpha)$ —the $p$ distinct linear factors exhaust the degree—and $X^{p}-X$ induces the zero function despite having degree $p\geq 1$ . □

Remark 5.44 (Why the formal viewpoint is the correct one).

Part (2) of 5.43 is precisely why polynomials are defined as coefficient sequences and not as functions. Cryptography works over finite fields, where the functional view loses information: the polynomials $X$ and $X^{p}$ induce the same function on $\mathbb{F}_{p}$ , yet have degrees $1$ and $p$ . And the degree of a polynomial—a property of the formal object, invisible to the induced function over a finite field—is what the security of polynomial commitment schemes rests on. A prover commits to a low-degree formal polynomial; the verifier tests it by evaluation; and the gap between agreement-as-function at the tested points and identity to the claimed formal polynomial is exactly what the Schwartz–Zippel lemma, next, quantifies.

5.10 The Schwartz–Zippel lemma

Only one preliminary is needed to state the payoff theorem. To draw $\alpha$ uniformly at random from a finite nonempty set $S$ means to select each element with equal likelihood $1/\lvert S\rvert$ ; the probability of an event is then the fraction of elements of $S$ producing it, so that $\Pr[f(\alpha)=0]=\lvert\{\alpha\in S:f(\alpha)=0\}\rvert/\lvert S\rvert$ . The systematic language of probability is developed later in the volume; this counting case is all the theorem needs.

Theorem 5.45 (Univariate Schwartz–Zippel).

Let $f\in F[X]$ be nonzero of degree at most $d$ , let $S\subseteq F$ be finite and nonempty, and let $\alpha$ be drawn uniformly at random from $S$ . Then

\Pr\bigl{[}f(\alpha)=0\bigr{]}\;\leq\;\frac{d}{\lvert S\rvert}.

(5)

More generally, if $f,g\in F[X]$ are distinct, each of degree at most $d$ , then $\Pr\bigl{[}f(\alpha)=g(\alpha)\bigr{]}\leq d/\lvert S\rvert$ .

Proof.

By 5.18, the nonzero $f$ has at most $d$ roots in $F$ , hence at most $d$ in the subset $S$ . Under the uniform draw,

\Pr\bigl{[}f(\alpha)=0\bigr{]}=\frac{\lvert\{\alpha\in S:f(\alpha)=0\}\rvert}{% \lvert S\rvert}\;\leq\;\frac{d}{\lvert S\rvert}.

For the general form, apply this to $h=f-g$ , which is nonzero and has degree at most $d$ by (1), noting that $f(\alpha)=g(\alpha)$ exactly when $h(\alpha)=0$ . □

Remark 5.46 (The lemma stated plainly, and used).

Inequality (5) formalises the slogan: two low-degree polynomials that agree at many points must be equal. The deterministic version is 5.20—agreement at $d+1$ points forces equality—and Schwartz–Zippel is its probabilistic refinement: a single random evaluation point detects unequal polynomials of degree at most $d$ , except with probability at most $d/\lvert S\rvert$ . With $\lvert S\rvert$ exponentially large—taking $S=\mathbb{F}_{q}$ with $q\approx 2^{254}$ , the 255-bit fields underlying Orchard—and $d$ polynomially bounded, the failure probability is astronomically small; the term negligible receives its precise asymptotic meaning later in the volume. This is the foundational soundness argument for polynomial identity testing, and hence for the polynomial commitment schemes and arithmetisation checks of Halo 2: to verify a purported polynomial identity, evaluate both sides at a random challenge and compare.

Remark 5.47 (Multivariate generalisation).

The full Schwartz–Zippel lemma extends to polynomials in several indeterminates $f\in F[X_{1},\dots,X_{n}]$ : a nonzero polynomial of total degree $d$ —the largest sum of exponents $i_{1}+\dots+i_{n}$ over the monomials with nonzero coefficient—vanishes at a uniformly random point of $S^{n}$ with probability at most $d/\lvert S\rvert$ . The univariate case proved here is both the base case of the multivariate inductive proof and the version most directly used: the later volumes invoke only the univariate lemma directly. Where an identity in several random challenges arises—for instance a permutation argument drawing a pair of challenges $(\beta,\gamma)$ —the multivariate bound applies and follows from the univariate lemma applied once per variable.

The cheque drawn in the section’s opening can now be cashed in full. Two parties hold polynomials $f$ and $g$ of degree at most $d$ over a 255-bit field $\mathbb{F}_{q}$ —even with $d$ in the millions, they agree on a uniformly random challenge $\alpha\in\mathbb{F}_{q}$ with probability at most $d/q\approx d\cdot 2^{-254}$ unless they are literally the same formal polynomial. One evaluation apiece, one comparison of field elements, and the enormous coefficient lists never change hands: that is the trade the proving system makes on every identity it checks, and the entire cost of the bargain is the elementary fact with which the section began—a nonzero polynomial of degree $d$ over a field has at most $d$ roots.