Number-theoretic transform

In mathematics, the discrete Fourier transform over an arbitrary ring generalizes the discrete Fourier transform of a function whose values are complex numbers.

Let ${\displaystyle R}$ be any ring, let ${\displaystyle n\geq 1}$ be an integer, and let ${\displaystyle \alpha \in R}$ be a principal nth root of unity, defined by:

The discrete Fourier transform maps an n-tuple ${\displaystyle (v_{0},\ldots ,v_{n-1})}$ of elements of ${\displaystyle R}$ to another n-tuple ${\displaystyle (f_{0},\ldots ,f_{n-1})}$ of elements of ${\displaystyle R}$ according to the following formula:

...
Wikipedia