Refined complexity bounds for rational reconstruction and XGCD through Padé approximants and Cauchy interpolants

Vincent Neiger, Mohab Safey El Din, Kevin Tran

When computing with univariate polynomials, two fundamental and related problems are the XGCD and rational reconstruction, classically solved in quasi-linear complexity using the h…