# Fast extrapolation from ⟨𝜔⟩

$$
\def\F{\mathbb F}
$$

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](https://hackmd.io/ZxR4-iKsRRqqcMtHYj8duA) we find:

$$
\left. \frac{X^n - 1}{X-𝜔^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{𝜔^i}{n} \frac{X^n - 1}{X-𝜔^i}
$$

---

$$
\begin{aligned}
P(z) &=
\sum_i a_i ⋅ L_i(z) \\&=
\sum_i a_i ⋅ \frac{𝜔^i}{n} \frac{z^n - 1}{z - 𝜔^i} \\&=
\frac{z^n - 1}{n} \sum_i \frac{a_i ⋅ 𝜔^i}{z - 𝜔^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$.