Main Page | See live article | Alphabetical index

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