Winograd NTT
\gdef\vec#1{\mathbf{#1}} \gdef\F{\mathbb{F}} \gdef\ω{\mathrm{ω}} \gdef\A{\mathsf{\small A}} \gdef\Mc{\mathsf{\small M^c}}
Definition 1. (Number Theoretic Transform). Given a finite field \F with primitive n-th root of unity \omega_n and a vector \vec a \in \F^n the number theoretic transform (NTT) \vec b \in \F^n of \vec a is \begin{equation} b_j = \sum_{i \in [n]} \ω_n^{i ⋅ j} ⋅ a_i. \end{equation}
As stated, equation (1) requires n^2 ⋅ \Mc + n⋅(n-1) ⋅ \A operations in \F where \Mc is the cost of a multiplication by constant and \A is the cost of an addition in \F.
NTT is a Polynomial Evaluation
Construct a polynomial P(x) = a_n ⋅ x^n + a_{n-1} ⋅ x^{n-1} + \ldots + a_1 ⋅ x + a_0, then b_j = P(\omega_n^j).
References
https://cr.yp.to/arith/tangentfft-20070919.pdf
