Engineering / Mathematics — Polynomial Algorithms
Rational Function Reconstruction
Recovering a rational function from a residue modulo a polynomial, with degree bounds replacing size bounds.
Executive summary
Rational function reconstruction is the polynomial analogue of rational reconstruction: recover a quotient of polynomials of bounded degree from its residue modulo a fixed polynomial.
The algorithm is extended Euclid halted at the right moment, exactly as in the integer case.
Learning objectives
- State the problem and its uniqueness condition.
- Give the algorithm and its termination criterion.
- Identify the applications.
01The problem
Rational function reconstruction
Given h and a in F[X], and degree bounds r and s with r + s < deg h, find u, v with
u ≡ a v (mod h), deg u < r, deg v ≤ s, gcd(v, h) = 1.
Uniqueness
If a solution exists under the degree condition, it is unique up to a constant factor.
Reason. Two solutions give u₁v₂ ≡ u₂v₁ (mod h), and both sides have degree below deg h, so the congruence forces equality.
The condition r + s < deg h is the exact analogue of 2rs < n in the integer case. Degrees add where magnitudes multiply, so the condition is additive rather than multiplicative.
02The algorithm
Rational function reconstruction
h, a, degree bounds r and sthe rational function u/v congruent to a mod h, or failure- Initialise (r₀, t₀) = (h, 0) and (r₁, t₁) = (a, 1).
- While deg r₁ ≥ r:
- Compute q = r₀ div r₁.
- Set (r₀, r₁) = (r₁, r₀ − q r₁) and (t₀, t₁) = (t₁, t₀ − q t₁).
- Set u = r₁ and v = t₁.
- If deg v > s or gcd(v, h) ≠ 1, report failure; else return u/v.
O(deg(h)²) field operationsThe invariant rᵢ ≡ a tᵢ (mod h) holds throughout, exactly as in the integer version. Stopping at the first remainder below the degree bound yields a pair with both degrees small enough.
03Applications
| Application | What is reconstructed | The modulus h |
|---|---|---|
| Pade approximation | A rational function matching a series | X^N |
| Reed-Solomon decoding | The error locator and evaluator | The generator-related polynomial |
| Sparse interpolation | A rational generating function | A power of X |
| Exact linear solving over F(X) | Rational function entries | A product of moduli |
The decoding application is the most consequential. The key equation of algebraic decoding asks for a rational function of bounded numerator and denominator degree congruent to a known syndrome polynomial — precisely this problem — so the decoder is an extended Euclid run halted at the right point.
Recognising decoding as reconstruction rather than as a bespoke procedure is what makes the algorithm short and its correctness proof transparent.
04Frequently asked questions
Why is the degree condition additive rather than multiplicative?
Because degrees add under polynomial multiplication where magnitudes multiply under integer multiplication. Taking logarithms of the integer condition gives the additive form, so the two conditions are the same statement in different measures.
What if the degree bounds are wrong?
The algorithm either fails or returns a wrong answer, so verification matters. In decoding, the recovered error pattern is checked against the received word, which catches any failure.
Is this the same as Pade approximation?
Yes, when the modulus is a power of X. Pade approximation asks for a rational function matching a series to a given order, which is exactly reconstruction with h = X^N.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 410-413.
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.