Number-theoretic transform

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}^{n}z^{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}\neq 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.