Polynomials are one of the most powerful tools in discrete mathematics. They let us encode information, detect and correct errors, share secrets, and prove deep results about computation. The key insight in this note: polynomials behave beautifully not just over the real numbers, but also over finite fields — arithmetic modulo a prime. This makes them useful for computer science where everything is ultimately finite.
Section 1
What is a Polynomial?
Definition — Polynomial
A polynomial in variable $x$ with coefficients $a_0, a_1, \ldots, a_d$ is:
$$p(x) = a_d x^d + a_{d-1}x^{d-1} + \cdots + a_1 x + a_0$$
The degree of $p$ is $d$ (assuming $a_d \neq 0$). A value $r$ is a root of $p$ if $p(r) = 0$.
Think of a polynomial as a recipe: the coefficients $a_i$ are the ingredients, and evaluating $p(x)$ at a specific value of $x$ is cooking the recipe. For example, $p(x) = 5x^3 + 2x + 1$ evaluated at $x = 3$ gives $p(3) = 5(27) + 6 + 1 = 142$.
The polynomial $p(x) = x^2 - 4$ has exactly two roots at $x = \pm 2$. Roots are where the curve crosses the $x$-axis. Click to animate and see a new polynomial.
The coefficients can live in any number system that supports $+$, $-$, $\times$, $\div$. They can be real numbers, complex numbers, or integers modulo a prime. The last case — finite fields — is what makes polynomials so useful in CS.
Section 2
Two Core Properties
Everything in this note (error correction, secret sharing, interpolation) rests on just two fundamental facts about polynomials. Memorize these.
Property 1 — At Most $d$ Roots
A non-zero polynomial of degree $d$ has at most $d$ roots.
Intuition: A line (degree 1) can cross the $x$-axis at most once. A parabola (degree 2) at most twice. A cubic at most three times. This extends to all degrees.
Property 2 — Unique Interpolation
Given $d+1$ pairs $(x_1, y_1), \ldots, (x_{d+1}, y_{d+1})$ with all $x_i$ distinct, there is a unique polynomial of degree at most $d$ passing through all of them.
Intuition: Two points uniquely determine a line. Three points uniquely determine a parabola. In general, $d+1$ points uniquely determine a degree-$d$ polynomial.
⚠ Why "non-zero" matters in Property 1
The zero polynomial $p(x) = 0$ is technically degree $-\infty$ or undefined, and it has every value as a root. Property 1 only applies to non-zero polynomials. This distinction is critical in proofs.
Proof of Property 2 (Uniqueness)
Existence is shown by Lagrange interpolation (next section). For uniqueness: suppose two polynomials $p(x)$ and $q(x)$ both of degree $\leq d$ pass through all $d+1$ points. Then $r(x) = p(x) - q(x)$ is a polynomial of degree $\leq d$ that has $d+1$ roots (one at each $x_i$). By Property 1, a non-zero degree-$d$ polynomial can have at most $d$ roots. Since $r$ has $d+1 > d$ roots, it must be the zero polynomial, meaning $p(x) = q(x)$.
Proof of Property 1
The key is polynomial division. If $a$ is a root of $p(x)$, we can write $p(x) = (x-a)q(x)$ where $q$ has degree $d-1$. Repeating this for each root, if $p$ had $d+1$ distinct roots $a_1, \ldots, a_{d+1}$, then $p(x) = c(x-a_1)(x-a_2)\cdots(x-a_{d+1})$, a polynomial of degree $d+1$. Contradiction with degree $d$.
Section 3
Lagrange Interpolation
Given $d+1$ points, how do we find the unique polynomial? The method is called Lagrange interpolation. The idea is elegant: build $d+1$ "basis polynomials," each of which is 1 at one point and 0 at all others, then combine them.
Lagrange Basis Polynomials
For points $x_1, \ldots, x_{d+1}$, define the $i$-th basis polynomial:
$$\Delta_i(x) = \prod_{j \neq i} \frac{x - x_j}{x_i - x_j}$$
This satisfies: $\Delta_i(x_i) = 1$ and $\Delta_i(x_j) = 0$ for $j \neq i$.
The Full Formula
The unique degree-$d$ polynomial through $(x_1,y_1), \ldots, (x_{d+1},y_{d+1})$ is:
$$p(x) = \sum_{i=1}^{d+1} y_i \cdot \Delta_i(x)$$
Think of it as: "at point $x_i$, only the $i$-th basis polynomial contributes, and it contributes $y_i \cdot 1 = y_i$."
📘 Example — Find the parabola through (1,1), (2,2), (3,4)
We need $d=2$, so we build three basis polynomials using $x_1=1, x_2=2, x_3=3$:
Interactive: Three draggable points determine a unique parabola. Click to reset. Notice how moving any single point changes the entire curve.
Section 4
Polynomial Division
Just like integer division, polynomials can be divided with a quotient and remainder:
Polynomial Division
For any polynomial $p(x)$ and divisor $q(x)$ with $\deg(q) \leq \deg(p)$:
$$p(x) = q'(x) \cdot q(x) + r(x)$$
where $q'(x)$ is the quotient and $r(x)$ is the remainder with $\deg(r) < \deg(q)$.
Key Fact — Root Factoring
If $a$ is a root of $p(x)$, then $(x - a)$ divides $p(x)$ exactly:
$$p(x) = (x-a) \cdot q(x) \quad \text{with no remainder}$$
Proof: Divide $p(x)$ by $(x-a)$: get $p(x) = (x-a)q(x) + r$ where $r$ is a constant. Plugging in $x=a$: $0 = p(a) = 0 + r$, so $r = 0$.
📘 Example — Divide $x^3 + x^2 - 1$ by $x - 1$
Using long division step by step:
Subtract $x^2(x-1)$ from $x^3 + x^2 - 1$: remainder is $2x^2 - 1$
Subtract $2x(x-1)$ from $2x^2 - 1$: remainder is $2x - 1$
Subtract $2(x-1)$ from $2x-1$: remainder is $1$
$$x^3 + x^2 - 1 = (x^2 + 2x + 2)(x-1) + 1$$
Quotient: $x^2 + 2x + 2$. Remainder: $1$. Since remainder $\neq 0$, $x=1$ is not a root.
Section 5
Finite Fields GF(p)
Here is the crucial insight that makes polynomials useful in computer science. Everything we proved about polynomials — Properties 1 and 2, Lagrange interpolation — relied only on being able to add, subtract, multiply, and divide (by nonzero elements). The real numbers support all four operations. So do the integers modulo a prime!
Finite Field GF(p)
For a prime $p$, the set $\{0, 1, 2, \ldots, p-1\}$ with arithmetic done modulo $p$ is called the Galois field $\text{GF}(p)$ (also written $\mathbb{F}_p$). It supports $+$, $-$, $\times$, and $\div$ (by any nonzero element).
Division works because for any $a \not\equiv 0 \pmod{p}$, by Fermat's little theorem $a^{-1} \equiv a^{p-2} \pmod{p}$ exists.
⚠ Why prime? What breaks for composite moduli?
If $m$ is not prime, say $m = 8$, then $2 \times 4 \equiv 0 \pmod{8}$, but neither 2 nor 4 is zero. This means nonzero elements can multiply to zero — catastrophic for our proofs. Over $\text{GF}(8)$, the polynomial $x^3$ has roots $0, 2, 4, 6$ — four roots for a degree-3 polynomial, violating Property 1.
Because GF(p) is a finite set with $p$ elements, we can count polynomials over it:
# Points Given
# Degree-$d$ Polynomials Through Them
$d+1$ points
$1$ (unique)
$d$ points
$p$ (one free parameter)
$d-1$ points
$p^2$
$d-k$ points
$p^{k+1}$
$0$ points
$p^{d+1}$ (all polynomials of degree $\leq d$)
📘 Example — Polynomials mod 5
Let $p(x) = 2x + 3 \pmod{5}$. Find roots.
Set $2x + 3 \equiv 0 \pmod 5$. Then $2x \equiv -3 \equiv 2 \pmod 5$. So $x \equiv 1 \pmod 5$.
Only one root: $x = 1$. Consistent with Property 1 (degree 1 has at most 1 root). ✓
Check
$p(1) = 2(1) + 3 = 5 \equiv 0 \pmod 5$ ✓
Root is $x = 1$ in GF(5).
Section 6
Secret Sharing
Here is a beautiful application: the $(k, n)$-threshold secret sharing scheme. The idea is to split a secret $s$ among $n$ people so that any $k$ people can reconstruct it, but any $k-1$ or fewer people learn nothing.
The Scheme
Let $q$ be a prime larger than both $n$ and $s$. Work over $\text{GF}(q)$.
Choose a random polynomial $P(x)$ of degree $k-1$ with $P(0) = s$.
Give person $i$ the share $P(i)$, for $i = 1, \ldots, n$.
Any $k$ people have $k$ points, which uniquely determine $P$. They compute $P(0) = s$.
Any $k-1$ people have $k-1$ points. There are $q$ possible polynomials through those points (one for each possible secret), so they have zero information.
Illustration of a $(2,3)$-threshold scheme. The secret is $P(0)$. Any 2 people can find the line and recover it. One person alone cannot.
📘 Example — $(k=3, n=5)$ scheme with secret $s=1$ over GF(7)
If persons 1 and 5 meet, they know $P(1)=2$ and $P(5)=3$. For each guess $s = 0,1,\ldots,6$, there exists a unique degree-2 polynomial through $(0,s),(1,2),(5,3)$. So all 7 values of $s$ are equally consistent — they learn nothing.
The scheme achieves perfect information-theoretic secrecy.
Section 7
Hard Practice Problems
🔥 Hard Problem 1
Problem: Let $p(x)$ be a polynomial of degree $\leq d$ over $\text{GF}(q)$ (for prime $q > d+1$). You are given the values $p(1), p(2), \ldots, p(d)$ — that is, $d$ points. Prove that for any target value $T \in \text{GF}(q)$, there exists exactly one degree-$\leq d$ polynomial $p$ satisfying those $d$ constraints AND $p(0) = T$.
📋 Solution to Hard Problem 1
Solution: We need to show the number of valid polynomials is exactly 1 for each value of $T$.
We have $d+1$ constraints: $p(1), p(2), \ldots, p(d)$ are fixed, and $p(0) = T$ for a chosen $T$. These are $d+1$ points $(0,T),(1,p(1)),\ldots,(d,p(d))$.
By Property 2, since all $x$-values $\{0,1,\ldots,d\}$ are distinct, there is exactly one polynomial of degree $\leq d$ through these $d+1$ points.
So for each of the $q$ choices of $T$, there is exactly one polynomial. The $d$ given constraints are consistent with $q$ possible polynomials (one per $T$ value).
Conclusion: This is exactly why $k-1$ shareholders in the secret sharing scheme have no information — no matter their shares, there are $q$ equally valid polynomials (one per possible secret), so the secret could be anything in GF($q$) with equal probability. ∎
🔥 Hard Problem 2
Problem: You are working over GF(7). You know that a polynomial $p(x)$ of degree at most 2 satisfies $p(1) = 3$, $p(2) = 5$, $p(4) = 2$. Find $p(0)$ using Lagrange interpolation mod 7.
📋 Solution to Hard Problem 2
We use Lagrange interpolation with $x_1=1, x_2=2, x_3=4$ and $y_1=3, y_2=5, y_3=2$ over GF(7).
Verify: You can find $p(x)$ explicitly from Lagrange and check $p(0)$. This type of calculation appears frequently in both secret sharing and error correction questions.