The Ultimate Number-theoretic transform - American History Information Guide and Reference

The number-theoretic transform is similar to the discrete Fourier transform, but operates with modular arithmetic instead of complex numbers.

The discrete Fourier transform is given by

$f_j=\sum_{k=0}^{n-1}x_k\left(e^{-\frac{2\pi i}{n}}\right)^{jk}\quad\quad j=0,\dots,n-1$

The number-theoretic transform operates on a sequence of n numbers, modulus a prime number p of the form p=ξn+1, where ξ can be any positive integer.

The number $e^{-\frac{2\pi i}{n}}$ is substituted with a number ω^ξ where ω is a "primitive root" of p, a number where the lowest positive integer ж where ω^ж=1 is ж=p-1. There should be plenty of ω which fit this condition. Note that both $e^{-\frac{2\pi i}{n}}$ and ω^ξ raised to the power of n are equal to 1 (mod p), all lesser positive powers not equal to 1.

The number-theoretic transform is then given by

$f(x)_j=\sum_{k=0}^{n-1}x_k(\omega^\xi)^{jk}\mod p\quad\quad j=0,\dots,n-1$

The inverse number-theoretic transform is given by

$f^{-1}(x)_h=n^{p-2}\sum_{j=0}^{n-1}x_j(\omega^{p-1-\xi})^{hj}\mod p\quad\quad h=0,\dots,n-1$

Note that ω^p-1-ξ=ω^-ξ, the reciprocal of ω^ξ, and n^p-2=n^-1, the reciprocal of n. (mod p)

The inverse works because $\sum_{k=0}^{n-1}z^k$ is n for z=1 and 0 for all other z where zⁿ=1. A proof of this (should work for any division algebra) is

$z\left(\sum_{k=0}^{n-1}z^k\right)+1=\sum_{k=0}^nz^k$

$z\sum_{k=0}^{n-1}z^k=\sum_{k=0}^{n-1}z^k$ (subtracting zⁿ=1)

$z=1\ \mathrm{if}\ \sum_{k=0}^{n-1}z^k\ne 0$ (dividing both sides)

If z=1 then we could trivially see that $\sum_{k=0}^{n-1}z^k=\sum_{k=0}^{n-1}1=n$ . If z≠1 then the right side must be false to avoid a contradiction.

It is now straightforward to complete the proof. We take the putative inverse transform of the transform.

$f^{-1}(f(x))_h=n^{p-2}\sum_{j=0}^{n-1}\left(\sum_{k=0}^{n-1}x_k\left(\omega^\xi\right)^{jk}\right)(\omega^{p-1-\xi})^{hj}\mod p$

$f^{-1}(f(x))_h=n^{p-2}\sum_{j=0}^{n-1}\sum_{k=0}^{n-1}x_k(\omega^\xi)^{jk-hj}\mod p$

$f^{-1}(f(x))_h=n^{p-2}\sum_{k=0}^{n-1}x_k\sum_{j=0}^{n-1}(\omega^{\xi(k-h)})^j\mod p$

$f^{-1}(f(x))_h=n^{p-2}\sum_{k=0}^{n-1}x_k\left\{\begin{matrix}n,&k=h\\0,&k\ne h\end{matrix}\right\}\mod p$ (since ω^ξn=1)

$f^{-1}(f(x))_h=n^{p-2}x_hn\mod p$

$f^{-1}(f(x))_h=x_h\mod p$

External link

Site which (hopefully) says the same as this article

Categories: Fourier analysis

Your American History Reference Guide!
- Number-theoretic transform

Number-theoretic transform

See also

External link

Your American History Reference Guide! - Number-theoretic transform

Number-theoretic transform

See also

External link

Your American History Reference Guide!
- Number-theoretic transform