Radix conversion for polynomials

We describe various approaches to the problem of expressing a polynomial $f(x) = \sum_{i=0}^{m} a_i x^i$ in terms of a different radix $r(x)$ as $f(x) = \sum_{j=0}^{n} b_j(x) r(x)^j$ with $0 \leq \deg(b_j) < \deg(r)$. Two approaches, the naive repeated division by $r(x)$ and the divide and conquer strategy, are well known. We also describe an approach based on the use of precomputed Newton inverses, which appears to offer significant practical improvements. A potential application of interest to number theorists is the fibration method for point counting, in current implementations of which the runtime is typically dominated by radix conversions.