Lagmental Vicfred

NTT Performs the Fourier Transform inside a Finite Field by Vicfred

tags: mathematics, polynomial algorithms, optimization, duality

A primitive power-of-two root modulo p replaces complex roots and avoids rounding error. I want the notation, the mechanism, and the failure mode visible at the same time.

Objects and notation

Fast algebraic algorithms exploit structure in a transform, matrix, or convex objective. The Fourier transform evaluates \(A(x)\) at roots \(\omega_n^k\), while linear-programming duality supplies certificates.

$$ \omega^n\equiv1\pmod p,\qquad\omega^k\not\equiv1\pmod p\ (0<k<n) $$

There are two layers here: the object \(\mathsf D\) and the law \(\mathsf C\). Writing them separately makes the direction of \(\Longrightarrow\) visible and keeps an accidental converse from slipping in.

$$ \widehat a_j=\sum_{k=0}^{n-1}a_k\omega^{jk}\pmod p $$

Push the symbols

Here is a concrete symbolic test. Reading it from left to right reveals which transformation is reversible and which is only an implication.

$$ a_k=n^{-1}\sum_{j=0}^{n-1}\widehat a_j\omega^{-jk}\pmod p,\qquad n\mid(p-1) $$

Structural reading

The two-row display is also a debugging tool: if the conclusion changes when only notation changes, some hidden choice has entered the argument.

$$ \begin{aligned} \mathsf{D}\;&:\quad \omega^n\equiv1\pmod p,\qquad\omega^k\not\equiv1\pmod p\ (0<k<n),\\[5pt] \mathsf{C}\;&:\quad \widehat a_j=\sum_{k=0}^{n-1}a_k\omega^{jk}\pmod p. \end{aligned} $$

A hypothesis worth keeping

An asymptotically fast method still needs algebraic preconditions: an NTT modulus needs suitable roots, and convex-hull optimization needs monotone slopes or queries for its simplest form.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \widehat a_j=\sum_{k=0}^{n-1}a_k\omega^{jk}\pmod p \end{gathered}} $$

The important habit is to remember what was fixed before the calculation began and what was proved only afterward. The final display preserves that order.

This article was posted on Mon 22 June 2015. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.