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 $n$-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} $$

  1. 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} $$

Remco Bloemen
Math & Engineering
https://2π.com