Fast extrapolation from ⟨ω⟩

Given P ∈ \F[X] with \deg P < n and ω a n-primitive root of unity. Evaluate P on the subgroup generated by ω:

a_i = P(ω^i)

Goal. Given only a_i and arbitrary z ∈ \F, efficiently evaluate P(z).

Observe the Lagrange basis for ⟨ω⟩:

L_i(X) = c_i \frac{X^n - 1}{X-ω^i}

where c_i is set such that L_i(ω^j) = \delta_{ij} (i.e. one when i = j and zero otherwise). Using L'Hospital rule we find:

\left. \frac{X^n - 1}{X-\omega^i} \right\vert_{X=ω^i} = \left. \frac{n⋅X^{n-1}}{1} \right\vert_{X=ω^i} = n ⋅ ω^{i(n-1)} = \frac{n}{ω^i}

and thus

L_i(X) = \frac{\omega^i}{n} \frac{X^n - 1}{X-\omega^i}

\begin{aligned} P(z) &= \sum_i a_i ⋅ L_i(z) \\&= \sum_i a_i ⋅ \frac{\omega^i}{n} \frac{z^n - 1}{z - \omega^i} \\&= \frac{z^n - 1}{n} \sum_i \frac{a_i ⋅ \omega^i}{z - \omega^i} \end{aligned}

This can be evaluated in \mathcal{O}(1) space and \mathcal{O}(m + \log n) time, where m is the number of non-zero entries in \vec a.