Engineering / Mathematics — Polynomial Algorithms
Chinese Remaindering and Polynomial Interpolation
The Chinese remainder theorem for polynomials, and Lagrange interpolation as its special case.
Executive summary
The Chinese remainder theorem holds for polynomials with pairwise coprime moduli, and taking the moduli to be distinct linear polynomials gives exactly Lagrange interpolation.
Recognising interpolation as a CRT instance explains why it is unique and why the formula takes the shape it does.
Learning objectives
- State the polynomial Chinese remainder theorem.
- Derive Lagrange interpolation as a special case.
- Compare the interpolation methods and their costs.
01The theorem
Chinese remainder theorem for polynomials
For pairwise coprime h₁, ..., h_k with product H,
F[X]/(H) ≅ F[X]/(h₁) × ··· × F[X]/(h_k).
The construction of the isomorphism's inverse is identical to the integer case: form Hᵢ = H/hᵢ, invert it modulo hᵢ, and take the appropriate combination.
f = Σᵢ aᵢ · Hᵢ · (Hᵢ⁻¹ mod hᵢ) mod H02Interpolation as a special case
Take hᵢ = X − xᵢ for distinct points xᵢ. These are pairwise coprime, and a residue modulo X − xᵢ is a constant — namely the value of the polynomial at xᵢ.
Lagrange interpolation
Given distinct points x₀, ..., x_n and values y₀, ..., y_n, there is a unique polynomial of degree at most n with f(xᵢ) = yᵢ, given by
f(X) = Σᵢ yᵢ ∏_{j ≠ i} (X − xⱼ)/(xᵢ − xⱼ).
03Interpolation methods
- Lagrange form
O(n²)Explicit; poor for adding a new point - Newton form
O(n²)Incremental; adding a point costs O(n) - Fast interpolation
O(n log² n)Subproduct tree; the asymptotic method - Vandermonde solve
O(n³)Never do this — it is the same problem stated worse
| Method | Adding a point | Numerical behaviour |
|---|---|---|
| Lagrange | Recompute everything | Poor over the reals |
| Newton | One extra divided difference | Better over the reals |
| Fast | Recompute the tree | Exact over finite fields |
Over finite fields the numerical column is irrelevant and the choice is purely about cost and incrementality. Newton form is the practical default; the fast method matters only for large degree.
04Frequently asked questions
Why must the points be distinct?
Because the moduli X − xᵢ must be pairwise coprime, which fails when two points coincide. Repeated points correspond to derivative conditions and give Hermite interpolation instead.
Does interpolation work over any field?
Yes, provided enough distinct points exist. Over F_q there are only q elements, so interpolating a degree-n polynomial requires n + 1 ≤ q — a real constraint for small fields.
How does this connect to secret sharing?
Directly. Shamir's scheme distributes evaluations of a random polynomial; any k shares interpolate it and recover the constant term, while fewer determine nothing. The threshold is exactly the interpolation requirement.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 406-408.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.