Polynomial Evaluation Over Finite Fields

Polynomials and the Functions They Define

Over the real numbers, a nonzero polynomial cannot vanish at every input. Over a finite field, however, the field has only finitely many inputs. A polynomial can be nonzero as a formal expression and still evaluate to zero at every element of the field. Understanding this distinction is essential whenever polynomials over finite fields are used to describe data or build algebraic constructions.

Fix a prime \(p\). The field \(\mathbb{F}_p\) consists of the residue classes \(0,1,\dots,p-1\), with addition and multiplication performed modulo \(p\). A polynomial in \(\mathbb{F}_p[x]\) is a formal expression \(f(x)=a_0+a_1x+\cdots+a_dx^d\) with coefficients \(a_i\in\mathbb{F}_p\). Two polynomials are formally equal exactly when their coefficients of each power of \(x\) are equal. Evaluating \(f\) at \(a\in\mathbb{F}_p\) gives an element \(f(a)\in\mathbb{F}_p\); this defines a function from \(\mathbb{F}_p\) to itself.

The reason the converse can fail is that evaluation records only the values at the \(p\) elements of the field. A polynomial has coefficients at every power of \(x\), so the formal expression contains more information than its list of evaluations may preserve.

Why \(x^p-x\) Vanishes Everywhere

The key arithmetic fact is that every element of \(\mathbb{F}_p\) satisfies \(a^p=a\). Here is a proof that includes both zero and nonzero elements.

Proof. If \(a=0\), then \(a^p=0=a\). Now suppose \(a\ne0\). Multiplication by \(a\) sends the nonzero elements of \(\mathbb{F}_p\) to nonzero elements. It is one-to-one: if \(au=av\), then multiplying by \(a^{-1}\) gives \(u=v\). Since the set \(\mathbb{F}_p\setminus\{0\}\) is finite, this one-to-one map permutes its elements. Let \(P\) be the product of all \(p-1\) nonzero elements. Since none of those elements is zero, \(P\ne0\). The permutation gives \(P=\prod_{u\ne0}(au)=a^{p-1}P\). Multiplying by \(P^{-1}\) gives \(a^{p-1}=1\), and hence \(a^p=a\). \(\square\)

Consequently, the polynomial \(x^p-x\) evaluates to zero at every field element. But as a formal polynomial it has coefficient \(1\) on \(x^p\), so it is not the zero polynomial.

How Many Roots Can a Polynomial Have?

A root of \(f\) is an element \(a\) for which \(f(a)=0\). The usual root bound remains valid over a finite field: a nonzero polynomial of degree \(d\) has at most \(d\) distinct roots. The bound does not say that a polynomial cannot have more roots than there are elements in its field; it says only that the number of roots cannot exceed its degree.

Proof. We use induction on \(d\). If \(d=0\), then \(f\) is a nonzero constant and has no roots. Suppose \(d\ge1\), and assume the result holds for degree \(d-1\). If \(f\) has no roots, the claim holds. Otherwise choose a root \(a\). For each integer \(k\ge1\), the identity \(x^k-a^k=(x-a)(x^{k-1}+x^{k-2}a+\cdots+a^{k-1})\) shows that \(x^k-a^k\) is divisible by \(x-a\). Applying this to each term of \(f(x)-f(a)\), and using \(f(a)=0\), gives \(f(x)=(x-a)q(x)\) for a polynomial \(q\) of degree \(d-1\). If \(b\ne a\) is another root of \(f\), then \(0=f(b)=(b-a)q(b)\). Because \(b-a\ne0\) in the field, \(q(b)=0\). Thus all roots other than \(a\) are roots of \(q\), which has at most \(d-1\) roots by induction. Including \(a\), \(f\) has at most \(d\) distinct roots. \(\square\)

In the example over \(\mathbb{F}_5\), \(x^5-x\) has degree \(5\) and has exactly five roots. This reaches the bound; it does not violate it.

Characterizing Polynomials with the Same Values

Two polynomials define the same function on \(\mathbb{F}_p\) exactly when their difference is divisible by \(x^p-x\). To see why divisibility is the right condition, first note that \(x^p-x\) vanishes at every field element. Therefore any polynomial multiple of it also vanishes everywhere. For the converse, we need to know that vanishing at all field elements forces divisibility by this particular polynomial.

For a polynomial \(f\), the identity used in the root-bound proof shows that \(f(x)-f(a)\) is divisible by \(x-a\). Thus, if \(f(a)=0\), then \(x-a\) divides \(f\). If \(f\) vanishes at every element of \(\mathbb{F}_p\), we can successively factor out one linear factor for each field element: after factoring out \(x-a\), the remaining quotient still vanishes at every other element \(b\), since \(0=f(b)=(b-a)q(b)\) and \(b-a\ne0\).

Proof. First, \(x^p-x\) has degree \(p\), is monic, and vanishes at all \(p\) elements of \(\mathbb{F}_p\), by the theorem \(a^p=a\). It equals the product of the \(p\) distinct factors \(x-a\) for \(a\in\mathbb{F}_p\): the product is monic of degree \(p\), and its roots are exactly those elements. The difference between that product and \(x^p-x\) has degree at most \(p-1\) because their leading terms cancel, and it vanishes at all \(p\) elements. The root bound forces that difference to be the zero polynomial.

Now suppose \(f\) and \(g\) define the same function. Then \(h=f-g\) vanishes at every \(a\in\mathbb{F}_p\). Factoring out \(x-a\) for each field element as described above shows that their product, \(x^p-x\), divides \(h\). Conversely, suppose \(f-g=(x^p-x)q\) for some \(q\in\mathbb{F}_p[x]\). For every \(a\in\mathbb{F}_p\), \(f(a)-g(a)=(a^p-a)q(a)=0\). Thus \(f(a)=g(a)\) for every \(a\), so the polynomials define the same function. \(\square\)

Every Function Has a Unique Low-Degree Polynomial

The theorem also explains why polynomials of degree less than \(p\) are a useful way to represent functions on \(\mathbb{F}_p\). Each function has exactly one such representing polynomial. “Degree less than \(p\)” here means that all powers appearing have exponent at most \(p-1\); the zero polynomial is included.

Proof. For each \(a\in\mathbb{F}_p\), define \(L_a(x)=\prod_{b\in\mathbb{F}_p,\ b\ne a}\frac{x-b}{a-b}\). Every denominator \(a-b\) is nonzero, so it has an inverse in the field. The polynomial \(L_a\) has degree \(p-1\). At \(x=a\), each factor equals \(1\), so \(L_a(a)=1\). At any other field element \(c\ne a\), the factor for \(b=c\) is zero, so \(L_a(c)=0\). Therefore \(P(x)=\sum_{a\in\mathbb{F}_p}F(a)L_a(x)\) has degree at most \(p-1\) and satisfies \(P(c)=F(c)\) for every \(c\).

For uniqueness, suppose \(P\) and \(Q\) both have degree less than \(p\) and agree with \(F\) at every field element. Then \(P-Q\) vanishes at all \(p\) elements. If \(P-Q\) were nonzero, its degree would be at most \(p-1\), contradicting the root bound. Hence \(P-Q\) is the zero polynomial, so \(P=Q\). \(\square\)

Common Mistake: Confusing Roots with Formal Zero

A tempting but incorrect claim is: “If a polynomial evaluates to zero at every field element, it must be the zero polynomial.” Over \(\mathbb{F}_3\), the concrete counterexample is \(x^3-x\). It is formally nonzero, but its evaluations are \(0^3-0=0\), \(1^3-1=0\), and \(2^3-2=6\equiv0\pmod3\). The correction is to distinguish the polynomial from its induced function. The root bound is still true: \(x^3-x\) has degree \(3\) and exactly \(3\) roots.

In practical terms, evaluation can identify different formal polynomials. The theorem on \(x^p-x\) gives the precise test: \(f\) and \(g\) yield the same values at every field element if and only if their difference is a multiple of \(x^p-x\). Restricting to degree less than \(p\) removes this ambiguity, since each function then has a unique polynomial representation.