Discrete Fourier transform over a ring#Finite fields

Let {{mvar|R}} be any ring, let $n\backslash geq\; 1$ be an integer, and let $\backslash alpha\; \backslash in\; R$ be a principal nth root of unity, defined by:Martin Fürer, "[https://web.archive.org/web/20130425232048/http://www.cse.psu.edu/~furer/Papers/mult.pdf Faster Integer Multiplication]", STOC 2007 Proceedings, pp. 57–66. Section 2: The Discrete Fourier Transform.

{{NumBlk|:| $$

\begin{align}

& \alpha^n = 1 \\

& \sum_{j=0}^{n-1} \alpha^{jk} = 0 \text{ for } 1 \leq k < n

\end{align}

|{{EquationRef|1}}}}

The discrete Fourier transform maps an n-tuple $(v\_0,\backslash ldots,v\_\{n-1\})$ of elements of {{mvar|R}} to another n-tuple $(f\_0,\backslash ldots,f\_\{n-1\})$ of elements of {{mvar|R}} according to the following formula:

{{NumBlk|:|$f\_k\; =\; \backslash sum\_\{j=0\}^\{n-1\}\; v\_j\backslash alpha^\{jk\}.$|{{EquationRef|2}}}}

By convention, the tuple $(v\_0,\backslash ldots,v\_\{n-1\})$ is said to be in the time domain and the index {{mvar|j}} is called time. The tuple $(f\_0,\backslash ldots,f\_\{n-1\})$ is said to be in the frequency domain and the index {{mvar|k}} is called frequency. The tuple $(f\_0,\backslash ldots,f\_\{n-1\})$ is also called the spectrum of $(v\_0,\backslash ldots,v\_\{n-1\})$. This terminology derives from the applications of Fourier transforms in signal processing.

If {{mvar|R}} is an integral domain (which includes fields), it is sufficient to choose $\backslash alpha$ as a primitive nth root of unity, which replaces the condition ({{EquationNote|1}}) by:

:$\backslash alpha^\{k\}\; \backslash ne\; 1$ for

{{Math proof|1=Take $\backslash beta\; =\; \backslash alpha^k$ with . Since $\backslash alpha^n=1$, $\backslash beta^n=(\backslash alpha^n)^k=1$, giving:

:$\backslash beta^n-1\; =\; (\backslash beta-1)\backslash left(\backslash sum\_\{j=0\}^\{n-1\}\; \backslash beta^j\backslash right)\; =\; 0$

where the sum matches ({{EquationNote|1}}). Since $\backslash alpha$ is a primitive root of unity, $\backslash beta\; -\; 1\; \backslash ne\; 0$. Since {{mvar|R}} is an integral domain, the sum must be zero. ∎}}

Another simple condition applies in the case where n is a power of two: ({{EquationNote|1}}) may be replaced by $\backslash alpha^\{n/2\}\; =\; -1$.

The inverse of the discrete Fourier transform is given as:

{{NumBlk|:|$v\_j\; =\; \backslash frac\{1\}\{n\}\backslash sum\_\{k=0\}^\{n-1\}\; f\_k\backslash alpha^\{-jk\}.$|{{EquationRef|3}}}}

where $1/n$ is the multiplicative inverse of {{mvar|n}} in {{mvar|R}} (if this inverse does not exist, the DFT cannot be inverted).

{{Math proof|1=Substituting ({{EquationNote|2}}) into the right-hand-side of ({{EquationNote|3}}), we get

:$$

\begin{align}

& \frac{1}{n}\sum_{k=0}^{n-1} f_k\alpha^{-jk} \\

= {} & \frac{1}{n}\sum_{k=0}^{n-1}\sum_{j'=0}^{n-1} v_{j'}\alpha^{j'k}\alpha^{-jk} \\

= {} & \frac{1}{n}\sum_{j'=0}^{n-1} v_{j'} \sum_{k=0}^{n-1}\alpha^{(j'-j)k}.

\end{align}

This is exactly equal to $v\_j$, because

$\backslash sum\_\{k=0\}^\{n-1\}\backslash alpha^\{(j\text{'}-j)k\}=0$ when $j\text{'}\backslash neq$

j (by ({{EquationNote|1}}) with $k=j\text{'}-j$), and

$\backslash sum\_\{k=0\}^\{n-1\}\backslash alpha^\{(j\text{'}-j)k\}=n$ when $j\text{'}=j$. ∎}}

Since the discrete Fourier transform is a linear operator, it can be described by matrix multiplication. In matrix notation, the discrete Fourier transform is expressed as follows:

:$$

\begin{bmatrix}f_0\\f_1\\\vdots\\f_{n-1}\end{bmatrix}

= \begin{bmatrix}

1&1&1&\cdots &1 \\

1&\alpha&\alpha^2&\cdots&\alpha^{n-1} \\

1&\alpha^2&\alpha^4&\cdots&\alpha^{2(n-1)}\\

\vdots&\vdots&\vdots&\ddots&\vdots\\

1&\alpha^{n-1}&\alpha^{2(n-1)}&\cdots&\alpha^{(n-1)(n-1)}\\

\end{bmatrix}

\begin{bmatrix}v_0\\v_1\\\vdots\\v_{n-1}\end{bmatrix}.

The matrix for this transformation is called the DFT matrix.

Similarly, the matrix notation for the inverse Fourier transform is

:$$

\begin{bmatrix}v_0\\v_1\\\vdots\\v_{n-1}\end{bmatrix}

= \frac{1}{n}\begin{bmatrix}

1&1&1&\cdots &1 \\

1&\alpha^{-1}&\alpha^{-2}&\cdots&\alpha^{-(n-1)} \\

1&\alpha^{-2}&\alpha^{-4}&\cdots&\alpha^{-2(n-1)}\\

\vdots&\vdots&\vdots&\ddots&\vdots\\

1&\alpha^{-(n-1)}&\alpha^{-2(n-1)}&\cdots&\alpha^{-(n-1)(n-1)}

\end{bmatrix}

\begin{bmatrix}f_0\\f_1\\\vdots\\f_{n-1}\end{bmatrix}.

Sometimes it is convenient to identify an {{mvar|n}}-tuple $(v\_0,\backslash ldots,v\_\{n-1\})$ with a formal polynomial

:$p\_v(x)\; =\; v\_0\; +\; v\_1x\; +\; v\_2x^2\; +\; \backslash cdots\; +\; v\_\{n-1\}x^\{n-1\}.\; \backslash ,$

By writing out the summation in the definition of the discrete Fourier transform ({{EquationNote|2}}), we obtain:

:$f\_k\; =\; v\_0\; +\; v\_1\backslash alpha^\{k\}\; +\; v\_2\backslash alpha^\{2k\}\; +\; \backslash cdots\; +\; v\_\{n-1\}\backslash alpha^\{(n-1)k\}.\; \backslash ,$

This means that $f\_k$ is just the value of the polynomial $p\_v(x)$ for $x=\backslash alpha^k$, i.e.,

{{NumBlk|:|$f\_k\; =\; p\_v(\backslash alpha^k).\backslash ,$|{{EquationRef|4}}}}

The Fourier transform can therefore be seen to relate the coefficients and the values of a polynomial: the coefficients are in the time-domain, and the values are in the frequency domain. Here, of course, it is important that the polynomial is evaluated at the {{mvar|n}}th roots of unity, which are exactly the powers of $\backslash alpha$.

Similarly, the definition of the inverse Fourier transform ({{EquationNote|3}}) can be written:

{{NumBlk|:|$v\_j\; =\; \backslash frac\{1\}\{n\}(f\_0\; +\; f\_1\backslash alpha^\{-j\}\; +\; f\_2\backslash alpha^\{-2j\}\; +\; \backslash cdots\; +\; f\_\{n-1\}\backslash alpha^\{-(n-1)j\}).$|{{EquationRef|5}}}}

With

:$p\_f(x)\; =\; f\_0\; +\; f\_1x\; +\; f\_2x^2\; +\; \backslash cdots\; +\; f\_\{n-1\}x^\{n-1\},$

this means that

:$v\_j\; =\; \backslash frac\{1\}\{n\}p\_f(\backslash alpha^\{-j\}).$

We can summarize this as follows: if the values of $p\_v(x)$ are the coefficients of $p\_f(x)$, then the values of $p\_f(x)$ are the coefficients of $p\_v(x)$, up to a scalar factor and reordering.R. Lidl and G. Pilz. Applied Abstract Algebra, 2nd edition. Wiley, 1999, pp. 217–219.

If $F=\{\backslash mathbb\; C\}$ is the field of complex numbers, then the $n$th roots of unity can be visualized as points on the unit circle of the complex plane. In this case, one usually takes

:$\backslash alpha=e^\{\backslash frac\{-2\backslash pi\; i\}\{n\}\},$

which yields the usual formula for the complex discrete Fourier transform:

:$f\_k\; =\; \backslash sum\_\{j=0\}^\{n-1\}\; v\_j\; e^\{\backslash frac\{-2\backslash pi\; i\}\{n\}jk\}.$

Over the complex numbers, it is often customary to normalize the formulas for the DFT and inverse DFT by using the scalar factor $\backslash frac\{1\}\{\backslash sqrt\{n\}\}$ in both formulas, rather than $1$ in the formula for the DFT and $\backslash frac\{1\}\{n\}$ in the formula for the inverse DFT. With this normalization, the DFT matrix is then unitary.

Note that $\backslash sqrt\{n\}$ does not make sense in an arbitrary field.

If $F=\backslash mathrm\{GF\}(q)$ is a finite field, where {{mvar|q}} is a prime power, then the existence of a primitive {{mvar|n}}th root automatically implies that {{mvar|n}} divides $q-1$, because the multiplicative order of each element must divide the size of the multiplicative group of {{mvar|F}}, which is $q-1$. This in particular ensures that $n=\backslash underbrace\{1+1+\backslash cdots+1\}\_\{n\backslash \; \backslash rm\; times\}$ is invertible, so that the notation $\backslash frac\{1\}\{n\}$ in ({{EquationNote|3}}) makes sense.

An application of the discrete Fourier transform over $\backslash mathrm\{GF\}(q)$ is the reduction of Reed–Solomon codes to BCH codes in coding theory. Such transform can be carried out efficiently with proper fast algorithms, for example, cyclotomic fast Fourier transform.

Suppose $F=\backslash mathrm\{GF\}(p)$. If $p\backslash nmid\; n$, it may be the case that $n\; \backslash nmid\; p-1$. This means we cannot find an $n^\{th\}$ root of unity in $F$. We may view the Fourier transform as an isomorphism $\backslash mathrm\{F\}[C\_n]=\backslash mathrm\{F\}[x]/(x^n-1)\; \backslash cong\; \backslash bigoplus\_i\; \backslash mathrm\{F\}[x]/(P\_i(x))$ for some polynomials $P\_i(x)$, in accordance with Maschke's theorem. The map is given by the Chinese remainder theorem, and the inverse is given by applying Bézout's identity for polynomials.{{cite web | url=https://github.com/jacksonwalters/dft-finite-groups | title=Jacksonwalters/DFT-finite-groups | website=GitHub }}

$x^n-1=\backslash prod\_\{d|n\}\; \backslash Phi\_d(x)$, a product of cyclotomic polynomials. Factoring $\backslash Phi\_d(x)$ in $F[x]$ is equivalent to factoring the prime ideal $(p)$ in $\backslash mathrm\{Z\}[\backslash zeta]\; =\; \backslash mathrm\{Z\}[x]/(\backslash Phi\_d(x))$. We obtain $g$ polynomials $P\_1\; \backslash ldots\; P\_g$ of degree $f$ where $fg\; =\; \backslash varphi(d)$ and $f$ is the order of $p\; \backslash text\{\; mod\; \}\; d$.

As above, we may extend the base field to $\backslash mathrm\{GF\}(q)$ in order to find a primitive root, i.e. a splitting field for $x^n-1$. Now $x^n-1\; =\; \backslash prod\_k\; (x-\backslash alpha^\{k\})$, so an element $\backslash sum\_\{j=0\}^\{n-1\}\; v\_j\; x^j\; \backslash in\; F[x]/(x^n-1)$ maps to $\backslash sum\_\{j=0\}^\{n-1\}\; v\_j\; x^j\; \backslash mod\; (x-\backslash alpha^k)\; \backslash equiv\; \backslash sum\_\{j=0\}^\{n-1\}\; v\_j\; (\backslash alpha^k)^j$ for each $k$.

When $p|n$, we may still define an $F\_p$-linear isomorphism as above. Note that $(x^n-1)=(x^m-1)^\{p^s\}$ where $n=m\; p^s$ and $p\; \backslash nmid\; m$. We apply the above factorization to $x^m-1$, and now obtain the decomposition $F[x]/(x^n-1)\; \backslash cong\; \backslash bigoplus\_i\; F[x]/(P\_i(x)^\{p^s\})$. The modules occurring are now indecomposable rather than irreducible.

Suppose $p\; \backslash nmid\; n$ so we have an $n^\{th\}$ root of unity $\backslash alpha$. Let $A$ be the above DFT matrix, a Vandermonde matrix with entries $A\_\{ij\}=\backslash alpha^\{ij\}$ for . Recall that $\backslash sum\_\{j=0\}^\{n-1\}\; \backslash alpha^\{(k-l)j\}\; =\; n\backslash delta\_\{k,l\}$ since if $k=l$, then every entry is 1. If $k\; \backslash ne\; l$, then we have a geometric series with common ratio $\backslash alpha^\{k-l\}$, so we obtain $\backslash frac\{1-\backslash alpha^\{n(k-l)\}\}\{1-\backslash alpha^\{k-l\}\}$. Since $\backslash alpha^n=1$ the numerator is zero, but $k-l\; \backslash ne\; 0$ so the denominator is nonzero.

First computing the square, $(A^2)\_\{ik\}\; =\; \backslash sum\_\{j=0\}^\{n-1\}\; \backslash alpha^\{j(i+k)\}\; =\; n\backslash delta\_\{i,-k\}$. Computing $A^4=(A^2)^2$ similarly and simplifying the deltas, we obtain $(A^4)\_\{ik\}=n^2\backslash delta\_\{i,k\}$. Thus, $A^4=n^2\; I\_n$ and the order is $4\backslash cdot\; \backslash text\{ord\}(n^2)$.

In order to align with the complex case and ensure the matrix is order 4 exactly, we can normalize the above DFT matrix $A$ with $\backslash frac\{1\}\{\backslash sqrt\{n\}\}$. Note that though $\backslash sqrt\{n\}$ may not exist in the splitting field $F\_q$ of $x^n-1$, we may form a quadratic extension $F\_\{q^2\}\; \backslash cong\; F\_q[x]/(x^2-n)$ in which the square root exists. We may then set $U=\backslash frac\{1\}\{\backslash sqrt\{n\}\}A$, and $U^4=I\_n$.

Suppose $p\; \backslash nmid\; n$. One can ask whether the DFT matrix is unitary over a finite field. If the matrix entries are over $F\_q$, then one must ensure $q$ is a perfect square or extend to $F\_\{q^2\}$ in order to define the order two automorphism $x\; \backslash mapsto\; x^q$. Consider the above DFT matrix $A\_\{ij\}=\backslash alpha^\{ij\}$. Note that $A$ is symmetric. Conjugating and transposing, we obtain $A\_\{ij\}^\{*\}=\backslash alpha^\{qji\}$.

$(AA^*)\_\{ik\}\; =\; \backslash sum\_\{j=0\}^\{n-1\}\backslash alpha^\{j(i+qk)\}\; =\; n\backslash delta\_\{i,-qk\}$

by a similar geometric series argument as above. We may remove the $n$ by normalizing so that $U\; =\; \backslash frac\{1\}\{\backslash sqrt\{n\}\}A$ and $(UU^*)\_\{ik\}\; =\; \backslash delta\_\{i,-qk\}$. Thus $U$ is unitary iff $q\; \backslash equiv\; -1\; \backslash ,(\backslash text\{mod\}\; \backslash ,\; n)$. Recall that since we have an $n^\{th\}$ root of unity, $n|q^2-1$. This means that $q^2\; -\; 1\; \backslash equiv\; (q+1)(q-1)\; \backslash equiv\; 0\; \backslash ,(\backslash text\{mod\}\; \backslash ,\; n)$. Note if $q$ was not a perfect square to begin with, then $n|q-1$ and so $q\; \backslash equiv\; 1\; \backslash ,\; (\backslash text\{mod\}\; \backslash ,\; n)$.

For example, when $p=3,\; n=5$ we need to extend to $q^2=3^4$ to get a 5th root of unity. $q=9\; \backslash equiv\; -1\; \backslash ,\; (\backslash text\{mod\}\; \backslash ,\; 5)$.

For a nonexample, when $p=3,\; n=8$ we extend to $F\_\{3^2\}$ to get an 8th root of unity. $q^2=9$, so $q\; \backslash equiv\; 3\; \backslash ,(\backslash text\{mod\}\; \backslash ,\; 8)$, and in this case $q+1\; \backslash not\backslash equiv\; 0$ and $q-1\; \backslash not\backslash equiv\; 0$. $UU^*$ is a square root of the identity, so $U$ is not unitary.

When $p\; \backslash nmid\; n$, we have an $n^\{th\}$ root of unity $\backslash alpha$ in the splitting field $F\_q\; \backslash cong\; F\_p[x]/(x^n-1)$. Note that the characteristic polynomial of the above DFT matrix may not split over $F\_q$.

The DFT matrix is order 4. We may need to go to a further extension $F\_\{q\text{'}\}$, the splitting extension of the characteristic polynomial of the DFT matrix, which at least contains fourth roots of unity. If $a$ is a generator of the multiplicative group of $F\_\{q\text{'}\}$, then the eigenvalues are $\backslash \{\backslash pm\; 1,\backslash pm\; a^\{(q\text{'}-1)/4\}\backslash \}$, in exact analogy with the complex case. They occur with some nonnegative multiplicity.

The number-theoretic transform (NTT){{Cite journal|last1=Agarwal|first1=R.|last2=Burrus|first2=C.|date=April 1974|title=Fast Convolution using fermat number transforms with applications to digital filtering|url=https://ieeexplore.ieee.org/document/1162555|journal=IEEE Transactions on Acoustics, Speech, and Signal Processing|language=en|volume=22|issue=2|pages=87–97|doi=10.1109/TASSP.1974.1162555|issn=0096-3518}} is obtained by specializing the discrete Fourier transform to $F=\{\backslash mathbb\; Z\}/p$, the modular arithmetic. This is a finite field, and primitive {{mvar|n}}th roots of unity exist whenever {{mvar|n}} divides $p-1$, so we have $p=\backslash xi\; n+1$ for a positive integer {{mvar|ξ}}. Specifically, let $\backslash omega$ be a primitive $(p-1)$th root of unity, then an {{mvar|n}}th root of unity $\backslash alpha$ can be found by letting $\backslash alpha=\backslash omega^\{\backslash xi\}$.

e.g. for $p=5$, $\backslash alpha\; =\; 2$

:

when $N=4$

:$$

\begin{bmatrix}

F(0) \\

F(1) \\

F(2) \\

F(3) \end{bmatrix}

=

\begin{bmatrix}

1 & 1 & 1 & 1 \\

1 & 2 & 4 & 3 \\

1 & 4 & 1 & 4 \\

1 & 3 & 4 & 2 \end{bmatrix}

\begin{bmatrix}

f(0) \\

f(1) \\

f(2) \\

f(3) \end{bmatrix}

The number theoretic transform may be meaningful in the ring $\backslash mathbb\{Z\}/m$, even when the modulus {{mvar|m}} is not prime, provided a principal root of order {{mvar|n}} exists. Special cases of the number theoretic transform such as the Fermat Number Transform ({{math|1=m = 2^k+1}}), used by the Schönhage–Strassen algorithm, or Mersenne Number Transform{{Cite journal|last=Rader|first=C.M.|date=December 1972|title=Discrete Convolutions via Mersenne Transforms|url=https://ieeexplore.ieee.org/document/1672090|journal=IEEE Transactions on Computers|volume=C-21|issue=12|pages=1269–1273|doi=10.1109/T-C.1972.223497|s2cid=1939809 |issn=0018-9340}} ({{math|1=m = 2^k − 1}}) use a composite modulus.

In general, if $m\; =\; \backslash prod\_i\; p\_i^\{e\_i\}$, then one may find an Root of unity modulo n by finding primitive $n^\{th\}$ roots of unity $g\_i$ mod $p\_i^\{e\_i\}$, yielding a tuple $g=\backslash left(g\_i\backslash right)\_i\; \backslash in\; \backslash prod\_i\; \backslash left(\backslash mathbb\{Z\}/p\_i^\{e\_i\}\backslash mathbb\{Z\}\backslash right)^\backslash ast$. The preimage of $g$ under the Chinese remainder theorem isomorphism is an $n^\{th\}$ root of unity $\backslash alpha$ such that $\backslash alpha^\{n/2\}\; =\; -1\; \backslash mod\; m$. This ensures that the above summation conditions are satisfied. We must have that $n|\backslash varphi(p\_i^\{e\_i\})$ for each $i$, where $\backslash varphi$ is the Euler's totient function function. {{Cite web

| title = ntt

| url = https://crates.io/crates/ntt

| last1 = Walters

| first1 = Jackson

| last2 = Silverman

| first2 = Thomas

| website = crates.io

| access-date = 2025-02-14

| language =

}}

The discrete weighted transform (DWT) is a variation on the discrete Fourier transform over arbitrary rings involving weighting the input before transforming it by multiplying elementwise by a weight vector, then weighting the result by another vector.{{Citation | last1 = Crandall | first1 = Richard | last2 = Fagin | first2 = Barry | title = Discrete weighted transforms and large-integer arithmetic | journal = Mathematics of Computation | volume = 62 | issue = 205 | year = 1994 | pages = 305–324 | url = http://www.faginfamily.net/barry/Papers/Discrete%20Weighted%20Transforms.pdf | doi=10.2307/2153411| jstor = 2153411 | doi-access = free }} The Irrational base discrete weighted transform is a special case of this.

Most of the important attributes of the complex DFT, including the inverse transform, the convolution theorem, and most fast Fourier transform (FFT) algorithms, depend only on the property that the kernel of the transform is a principal root of unity. These properties also hold, with identical proofs, over arbitrary rings. In the case of fields, this analogy can be formalized by the field with one element, considering any field with a primitive nth root of unity as an algebra over the extension field $\backslash mathbf\{F\}\_\{1^n\}.${{Clarify|reason=I don't understand|date=November 2018}}

In particular, the applicability of $O(n\; \backslash log\; n)$ fast Fourier transform algorithms to compute the NTT, combined with the convolution theorem, mean that the number-theoretic transform gives an efficient way to compute exact convolutions of integer sequences. While the complex DFT can perform the same task, it is susceptible to round-off error in finite-precision floating point arithmetic; the NTT has no round-off because it deals purely with fixed-size integers that can be exactly represented.

For the implementation of a "fast" algorithm (similar to how FFT computes the DFT), it is often desirable that the transform length is also highly composite, e.g., a power of two. However, there are specialized fast Fourier transform algorithms for finite fields, such as Wang and Zhu's algorithm,Yao Wang and Xuelong Zhu, "A fast algorithm for the Fourier transform over finite fields and its VLSI implementation", IEEE Journal on Selected Areas in Communications 6(3)572–577, 1988 that are efficient regardless of the transform length factors.

• Discrete Fourier transform (complex)
• Fourier transform on finite groups
• Gauss sum
• Convolution
• Least-squares spectral analysis
• Multiplication algorithm

• http://www.apfloat.org/ntt.html

{{DEFAULTSORT:Discrete Fourier Transform (General)}}

Category:Fourier analysis