THE VECTOR RATIONAL FUNCTION RECONSTRUCTION PROBLEM
ZACH OLESH, Arne Storjohann · 2007
The final step of some algebraic algorithms is to reconstruct the common denominator d of a collection of rational functions v∗/d from their polynomial images modulo m. Using elementwise rational reconstruction requires that deg m> N + D, where N and D are such that deg v ∗ ≤ N and deg d ≤ D. We present an algorithm, based on minimal approximant basis computation, that can perform the reconstruction for many problem instances even when the modulus has considerably smaller degree, for example deg m> N + D/k for k a small constant.