Engineering/Mathematics/Algorithm engineering

Polynomial Arithmetic and Applications

Every integer algorithm in this library has a polynomial twin, and the polynomial version is usually cleaner: degree bounds are exact, there are no carries, and the Chinese remainder theorem becomes interpolation. Reed–Solomon coding is the payoff.

Core algorithm
Computing
Coding theory
≈16 min read
Powers erasure coding

O(k²)ClassicalMultiplication and gcd of degree-k polynomials; no carry propagation, so the analysis is exact.

O(k log k)FFTMultiplication via evaluation at roots of unity, when the field supports them.

n − k + 1RS distanceReed–Solomon codes attain the Singleton bound: maximum distance separable.

⌊(n−k)/2⌋Correctable errorsHalf the redundancy, recovered by one rational function reconstruction.

Executive summary

Polynomials over a field admit division with remainder, so every algorithm built on that primitive transfers directly: Euclid, extended Euclid, modular inverses, Chinese remaindering, rational reconstruction. The cost model uses degree in place of bit length and counts field operations.

Two features are genuinely better than the integer case. Evaluation and interpolation give a second representation of a polynomial — its values at enough points — in which multiplication is pointwise; and the CRT specialises to interpolation, which makes error correction a reconstruction problem. Reed–Solomon codes are the direct consequence, and they are deployed in essentially every storage and transmission system in use.

Integer and polynomial algorithms side by side
Task	Over ℤ	Over F[X]	Cost over F[X]
Multiply	Karatsuba, FFT	Karatsuba, FFT	O(k²) or O(k log k)
gcd	Euclid	Euclid	O(k²)
Inverse mod m	extended gcd	extended gcd mod f	O(k²)
CRT	coprime moduli	coprime polynomials; linear moduli give interpolation	O(k²) or O(k log² k)
Rational reconstruction	size bounds	degree bounds	O(k²)
Factor	hard (subexponential)	easy (polynomial time)	Õ(k² + k log q)

The last row is the sharpest contrast: factoring polynomials over a finite field is easy, while factoring integers is not — a difference with no obvious a priori reason.

Contents

Basic and fast arithmetic

Cost of the primitives on degree-k polynomials over F_q
Operation	Classical	Fast	Notes
Addition	O(k)	O(k)	Componentwise; no carries
Multiplication	O(k²)	O(k log k) with FFT	Karatsuba O(k^1.585) in between
Division with remainder	O(k²)	O(k log k) via Newton inversion	Uses the reversed polynomial
gcd	O(k²)	O(k log² k) half-gcd	Crossover at high degree
Multipoint evaluation at k points	O(k²)	O(k log² k) remainder tree	The dual of interpolation
Interpolation from k points	O(k²)	O(k log² k)	CRT with linear moduli

FFT multiplication needs a principal root of unity of the right order; when the field lacks one, work in an extension or use Kronecker substitution into integer multiplication.

Why the FFT is the same idea as evaluation

A polynomial of degree below k is determined by its values at k distinct points. Multiplication is pointwise in that representation, so the recipe is: evaluate both operands, multiply pointwise, interpolate back. The FFT is nothing more than doing the evaluation and interpolation at the 2^m-th roots of unity, where a divide-and-conquer structure makes both steps O(k log k).

Contents

Euclid, inverses and Chinese remaindering

The extended Euclidean algorithm over F[X] is the integer version with degree as the size measure, and it terminates because degrees strictly decrease.

Extended Euclid over F[X]

(r₀,s₀,t₀) ← (f,1,0); (r₁,s₁,t₁) ← (g,0,1)
while r₁ ≠ 0:
q ← r₀ div r₁
(r₀,r₁) ← (r₁, r₀ − q·r₁)
(s₀,s₁) ← (s₁, s₀ − q·s₁)
(t₀,t₁) ← (t₁, t₀ − q·t₁)
normalise r₀ to monic and scale s₀,t₀ accordingly
return (r₀, s₀, t₀) // r₀ = gcd(f,g) = s₀f + t₀g

O(k²) field operations; deg r₀ + deg s₁ = deg g and deg r₀ + deg t₁ = deg f, so the coefficient degrees stay bounded throughout.

Inverses in F[X]/(f). Run the algorithm on (a, f). When f is irreducible the gcd is always 1 and an inverse always exists; when it is not, a gcd above 1 hands you a proper factor of f.
Polynomial CRT. For pairwise coprime f_i, F[X]/(∏f_i) ≅ ∏ F[X]/(f_i). With f_i = X − x_i the residues are the values h(x_i), and reconstruction is exactly Lagrange interpolation.
Modular algorithms. Polynomial gcds over ℤ[X] suffer from coefficient growth; the fix is to compute modulo several primes and reconstruct, exactly as in the integer case.

h(X) = ∑_i y_i ∏_{j ≠ i} (X − x_j)/(x_i − x_j)Lagrange interpolation: the CRT reconstruction formula specialised to linear moduli.

Contents

Rational function reconstruction

Theorem T1

Reconstruction with degree bounds

Given z and a modulus f of degree k, and bounds k_r + k_t < k, there is at most one pair (r,t) up to scaling with deg r ≤ k_r, deg t ≤ k_t, t ≠ 0 and r ≡ zt (mod f). It is produced by running the extended Euclidean algorithm on (f, z) and stopping at the first remainder of degree at most k_r.

Reed–Solomon decoding

The received word defines z; the error locator and evaluator are the reconstructed t and r.

Padé approximation

Reconstructing a rational function from a power series prefix is the same computation over F[[X]].

Minimal polynomials

Recovering the shortest recurrence of a linearly generated sequence, hence Wiedemann's algorithm.

Sparse interpolation

Recovering a rational function from evaluations, used in computer algebra for gcd and factorization.

Contents

Reed–Solomon codes

Definition D1

The code

Fix distinct evaluation points x₁, …, x_n ∈ F_q with n ≤ q. A message is a polynomial h of degree less than k; the codeword is the vector of values (h(x₁), …, h(x_n)). The code has length n, dimension k and minimum distance n−k+1.

The distance follows from the root bound: two distinct polynomials of degree below k agree in at most k−1 positions, so their codewords differ in at least n−k+1. That meets the Singleton bound with equality, making the code maximum distance separable.

What the parameters buy
Quantity	Value	Meaning
Redundancy	n − k	Number of parity symbols
Erasures corrected	n − k	Erasures have known positions, so interpolation suffices
Errors corrected	⌊(n−k)/2⌋	Unknown positions cost two symbols each
Errors and erasures	2·errors + erasures ≤ n − k	The combined budget
Field size	q ≥ n	Enough distinct evaluation points; F_2⁸ gives n ≤ 255

Decoding via rational function reconstruction (Berlekamp–Welch view)

input: received values y₁ … y_n, at most e = ⌊(n−k)/2⌋ errors
interpolate z with z(xᵢ) = yᵢ for all i // degree < n
f ← ∏(X − xᵢ) // degree n
run extended Euclid on (f, z), stopping at deg r ≤ k + e − 1
if t divides r: h ← r / t is the transmitted message
else: more than e errors occurred — declare failure

O(n²) field operations classically, or Õ(n) with fast arithmetic. The error locator t vanishes exactly at the corrupted positions.

Erasure coding in storage. RAID-6 and modern object stores use Reed–Solomon over F_2⁸: k data blocks and n−k parity blocks tolerate any n−k simultaneous device failures.
Optical media and 2D barcodes. CDs use cross-interleaved Reed–Solomon to survive scratches; QR codes offer four selectable redundancy levels using the same construction.
Deep-space telemetry. The concatenated Reed–Solomon and convolutional scheme became a CCSDS standard and remains in use.
Secret sharing. Shamir's scheme is the same object viewed differently: a random polynomial of degree k−1, with shares as evaluations, so any k shares interpolate the secret and fewer reveal nothing.

Contents

Quick reference and FAQ

Facts
Fact	Statement
Division	f = gq + r, deg r < deg g
gcd cost	O(k²) field operations
Interpolation	k points determine a polynomial of degree < k
FFT requirement	A principal 2^m-th root of unity in the field
Reconstruction condition	deg r + deg t < deg f
RS distance	n − k + 1 (MDS)
RS error capacity	⌊(n−k)/2⌋
RS field size	q ≥ n

Why is polynomial factorization easy while integer factorization is hard?

Finite fields provide the Frobenius map, which lets an algorithm separate factors by degree using gcds with X^{q^d} − X. The integers offer no analogous structure, and no analogue of the Frobenius map is known that would help.

When is FFT-based multiplication actually worth it?

For degrees in the thousands, and only when the field has suitable roots of unity or an extension can be used cheaply. For the degrees typical in coding applications — a few hundred — classical or Karatsuba multiplication with a well-tuned inner loop is faster.

Are erasures really twice as cheap as errors?

Yes. An erasure has a known position, so only its value is unknown and one parity symbol suffices; an error costs one symbol to locate and one to correct. Storage systems exploit this by having the device report failed reads as erasures rather than returning corrupt data.

How is Reed–Solomon related to the Chinese remainder theorem?

A codeword is the image of the message polynomial under the CRT isomorphism F[X]/(∏(X−x_i)) ≅ ∏ F. Decoding is CRT reconstruction from partially corrupted residues, and rational function reconstruction is what tolerates the corruption.

Contents

References and further reading

V. Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2005 — Chapter 18.
J. von zur Gathen and J. Gerhard, Modern Computer Algebra, 3rd ed., Cambridge, 2013 — Chapters 8–11.
I. S. Reed and G. Solomon, 'Polynomial codes over certain finite fields', J. SIAM 8 (1960) 300–304.
L. R. Welch and E. R. Berlekamp, 'Error correction for algebraic block codes', US Patent 4,633,470, 1986.
A. Shamir, 'How to share a secret', Communications of the ACM 22 (1979) 612–613.

KEVOS® Knowledge LibraryEngineering → MathematicsTaxonomy ID: ENG-MATHPage ID: polynomial-arithmetic-algorithmsReview cycle: annual

Polynomial Arithmetic and Applications

Executive summary

Basic and fast arithmetic

Euclid, inverses and Chinese remaindering

Rational function reconstruction

Reconstruction with degree bounds

Reed–Solomon decoding

Padé approximation

Minimal polynomials

Sparse interpolation

Reed–Solomon codes

The code

Quick reference and FAQ

References and further reading

Continue learning

KEVOS Intelligence

Executive summary

Basic and fast arithmetic

Euclid, inverses and Chinese remaindering

Rational function reconstruction

Reconstruction with degree bounds

Reed–Solomon decoding

Padé approximation

Minimal polynomials

Sparse interpolation

Reed–Solomon codes

The code

Quick reference and FAQ

Related pages in this library

References and further reading

Continue learning