Radix conversion for polynomials

Radix conversion for polynomials

Mon, 24/10/2011
16:00 		Sebastian Pancratz Junior Number Theory Seminar Add to calendar SR1
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.