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
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 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 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
The inverse number-theoretic transform is given by
Note that
ωp-1-ξ=
ω-ξ, the reciprocal of
ωξ, and
np-2=
n-1, the reciprocal of
n. (mod p)
The inverse works because 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
- (subtracting zn=1)
- (dividing both sides)
If
z=1 then we could trivially see that . 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.
-
- (since ωξn=1)
See also:
External link