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 np-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 zn=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 zn=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

See also

External link

 

<< PreviousWord BrowserNext >>
physical review focus
operation driftwood
the roundup
list of postage stamps
johnny wakelin
the mystery project
operation dunhill
kbs 3
ratio test
media art
operation defoe
finkleman's 45s
uss liscome bay (cve 56)
national fancy rat society
mars rover
nahuel moreno
greece (disambiguation)
mile basly
david korner
marquion
vocal group hall of fame
irish fiction
mricourt
sabotage (album)
alan thornett
north caledonian football league
boystown, chicago
scottish junior football association
biograph theater
richard verrall
the pied pipers
uss archerfish (ssn 678)
beleg
timeline of hacker history
colorblind james experience
david gascoyne
kings of arnor
chieftains of the dnedain
kappa (letter)
rho (letter)
list of romanian language poets
psi (letter)
david strickland
british surrealist group
Copyright 2005-2009 OnPedia.com. All Rights Reserved