Number Theoretic Transform Argument

Given two polynomials P, Q ∈ \mathbb{F}[X]/X^n, we can write them as

\begin{aligned} P(X) &= \sum_i p_i ⋅ L_i(X) & Q(X) &= \sum_i q_i ⋅ L_i(X) \end{aligned}

where p_i, q_i ∈ \mathbb{F}^n and L_i(X) are the Lagrange polynomials on \{ \omega_n^i \} where ω_n is an nth-root of unity. We want to proof that q_i is the number theoretic transform of p_i, that is

q_i = \sum_j p_j ⋅ ω_n^{i⋅j}

This is equivalent to proving that Q(X) = \sum_i p_i ⋅ X^i. To see this note that the Vandermonde matrix for the basis is also the Fourier matrix:

\begin{bmatrix} ω_n^0 & ω_n^0 & ω_n^0 & ⋯ & ω_n^0 \\ ω_n^0 & ω_n^1 & ω_n^2 & ⋯ & ω_n^{n-1} \\ ω_n^0 & ω_n^2 & ω_n^4 & ⋯ & ω_n^{2(n-1)} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ ω_n^0 & ω_n^{n-1} & ω_n^{2(n-1)} & ⋯ & ω_n^{(n-1)^2} \\ \end{bmatrix}

Argument

1. Commit to P and Q.
2. Sample random τ.
3. Commit n-term polynomial H(X) containing progressive Horner evaluations:

\begin{array}{l l} P(ω_n^i) & H(ω_n^i) \\ \hline p_0 & p_0 + τ ⋅ (p_1 + τ ⋅ (p_2+⋯ \\ p_1 & p_1 + τ ⋅ (p_2 + τ ⋅ (p_3+⋯ \\ ⋮ & ⋮ \\ p_{n - 3} & p_{n - 3} + τ ⋅ (p_{n - 2} + τ ⋅ p_{n - 1}) \\ p_{n - 2} & p_{n - 2} + τ ⋅ p_{n - 1} \\ p_{n - 1} & p_{n - 1} \\ \end{array}

4. Now proof the constraints

\begin{aligned} &H(X) = P(X) + τ ⋅ H(ω_n ⋅ X) && \forall X ∈ \{ω_n^0, …, ω_n^{n-2}\} \\ &H(ω_n^{n-1}) = P(ω_n^{n-1}) \\ &Q(τ) = H(ω_n^0) \end{aligned}