Polynomials: The Foundation of Coding and Cryptography

Data from the Curiosity rover travels 20 minutes to reach Earth and still contains bit errors. Reed-Solomon polynomial interpolation recovers every bit. A QR code can be 30% destroyed and still scan. Not because of backup copies - because of Lagrange's theorem: a degree-n polynomial is uniquely determined by n+1 points. Without this algorithm: silence from space and unreadable codes.

• **Reed-Solomon in QR codes**: level-L correction handles 7% damage, level-H handles 30%. This is polynomial interpolation over GF(2^8) - a finite field with 256 elements
• **NASA Voyager and Deep Space Network**: polynomial coding receives signals from 20+ billion km away using a 22-watt transmitter - less power than a refrigerator bulb
• **Polynomial rolling hash (Rabin-Karp)**: Horner's method for substring search in O(n) - the engine behind grep and search indexing
• **Shamir's Secret Sharing**: Lagrange interpolation splits a cryptographic key into n shares so any t of them reconstruct it - used in hardware security modules and multisig wallets

Предварительные знания

• Inequalities and Absolute Value

Polynomial Arithmetic: Rings, Degrees, Multiplication

A degree-n polynomial is p(x) = aₙxⁿ + aₙ₋₁xⁿ⁻¹ + ... + a₁x + a₀ with aₙ != 0. Addition works termwise: combine coefficients of matching powers. Multiplication distributes: every term of the first polynomial multiplies every term of the second. **Polynomials form a ring** - a closed structure: the sum and product of two polynomials is again a polynomial.

**Degree rules:** - deg(p·q) = deg(p) + deg(q) - degree of a product - deg(p+q) <= max(deg(p), deg(q)) - degree of a sum - Equality can fail when leading coefficients cancel **Polynomial ring F[x]**: when coefficients come from a field F (real numbers, or GF(2)), polynomials form a Euclidean ring - the Euclidean algorithm works in it.

**Reed-Solomon - polynomials over GF(2^8)**: a QR code stores data as a polynomial over a finite field. Level-L redundancy corrects up to 7% damage; level H, up to 30%. This is not backup copies - it is Lagrange's theorem: a degree-n polynomial is uniquely determined by n+1 points. Even if some points are lost, the rest reconstruct everything.

Horner's Method: O(n) Instead of O(n^2)

Evaluating p(x) = aₙxⁿ + ... + a₀ naively requires O(n^2) multiplications: computing xᵏ costs k multiplications. Horner's method rewrites the polynomial as nested multiplications: p(x) = (...((aₙ·x + aₙ₋₁)·x + aₙ₋₂)·x + ... + a₁)·x + a₀. Each step costs one multiplication and one addition. Total: O(n). Not just an optimization - the foundation of polynomial string hashing.

**Polynomial rolling hash** is Horner's method with a prime modulus. The Rabin-Karp algorithm computes hashes for all n-character windows in O(n) via a rolling update: remove the oldest character, shift, add the new one - one multiplication per step. This is the engine behind `grep` and full-text search indexing.

Polynomial Division: Remainder Theorem and CRC

Polynomial division mirrors integer long division: p(x) = q(x)·d(x) + r(x) with deg(r) < deg(d). **Remainder Theorem**: the remainder when dividing p(x) by (x - c) equals p(c). Consequence: (x - c) divides p(x) if and only if c is a root of p. This gives an instant divisibility test without performing the full division.

**Rational Root Theorem:** if p(x) = aₙxⁿ + ... + a₀ has a rational root p/q in lowest terms, then p divides a₀ and q divides aₙ. This narrows the search for candidates to a finite list - essential for hand factoring.

**CRC (Cyclic Redundancy Check)** is the polynomial Euclidean algorithm over GF(2). Data is treated as a polynomial, divided by a generator polynomial; the remainder becomes the checksum. Ethernet, USB, and ZIP all use CRC-32. This is not a hash - it guarantees detection of any single burst error. The mathematics is identical to long division on paper, executed in a binary field.

Lagrange Interpolation: The Theorem and Space Data

**Data from the Curiosity rover takes 20 minutes to reach Earth - and still contains errors.** Reed-Solomon - polynomial interpolation - recovers every bit. The principle: through n+1 points with distinct x-coordinates, exactly one polynomial of degree <= n passes. Lose some points - recover them from the rest. This is Lagrange's theorem at scale.

**Runge's phenomenon:** with many equally-spaced nodes, the Lagrange polynomial can oscillate wildly near the endpoints. Numerical methods use **Chebyshev nodes** xₖ = cos((2k+1)π/(2n+2)) to minimize this. Reed-Solomon sidesteps the issue entirely by working over a finite field GF(2^8), where oscillation is not possible.

**Shamir's Secret Sharing** is a cryptographic protocol: a secret is encoded as p(0), participants hold points on the polynomial. Any t out of n participants recover the key via interpolation; fewer than t learn nothing. Used in hardware security modules and multi-signature cryptocurrency wallets.

Key Ideas

• **Horner's method** evaluates degree-n polynomials in O(n) multiplications - the basis of polynomial rolling hash and CRC
• **Remainder Theorem:** remainder of p(x) / (x-c) equals p(c) - instant root test without full division
• **Polynomial GCD** via the Euclidean algorithm underlies CRC-32 in Ethernet, USB, and ZIP
• **Lagrange interpolation:** n+1 points uniquely determine a degree-<=n polynomial - foundation of Reed-Solomon and Shamir's Secret Sharing

Related Topics

Polynomials are a foundation for discrete math, number theory, and algebraic structures:

• Complex Numbers — Real polynomial roots can be complex - extending R to C
• Rings and Fields — The polynomial ring F[x] is a central example in abstract algebra
• Galois Theory — Solvability of polynomials by radicals is determined by the Galois group

Вопросы для размышления

• Reed-Solomon corrects up to 30% damaged symbols. What happens at 31%? Why is that the exact threshold?
• Polynomial hashes can collide. How do the choices of base and modulus affect collision probability, and why use a prime modulus?
• What is the fundamental difference between interpolation (exact fit through points) and least-squares approximation? When would one be chosen over the other?

Связанные уроки

• alg-03 — Inequalities and absolute value - previous lesson
• alg-05 — Complex roots of real polynomials
• alg-12 — Polynomial ring F[x] - center of abstract algebra
• ar-28-modular — GF(2^8) - polynomials over finite fields in Reed-Solomon
• ar-44-crypto-intro — Shamir's scheme: secret = polynomial value at 0
• la-01-vectors-intro