Efficient FFT with modular arithmetic. The FFT we presented in class relies on the ability to do idealized operations on complex numbers. Implementations will need to deal with issues of numerical stability, etc. In many cases it makes sense to work over a different group. Here we will look at an efficient implementation using modular arithmetic. We first need to review some facts. If p is a prime number, then Zp, the multiplicative group of integers mod p, has elements [1,2,...,p- 1 and group operation multiplication mod p. Any such group is cyclic, so it has a generator g, i.e., Ig.g1...,g"-2 gives us all the elements. Fermat's Little Theorem states that for any integer a, a a (mod p) (which also means that aP1 1 (mod p).) Let n be a power of 2, and let k be the smallest number such that p nk + 1 . Using the prime number theorem, we expect k to be around ign. Let g be a generator of Tp, and let w gk How does the expected length of the binary representation of p compare to that of n? Prove that w is a principle nth root of unity in a. b. Show how, using w, we can define the DFT and its inverse mod p, and prove that, assuming that arithmetic operations on words of length Olgn) have unit cost, we can perform the FFT mod p in time 0(nlgn). c. d. Using 3 as a generator of Zi7, compute the DFT mod 17 of (0,5,3,7,7,2,1,6) Efficient FFT with modular arithmetic. The FFT we presented in class relies on the ability to do idealized operations on complex numbers. Implementations will need to deal with issues of numerical stability, etc. In many cases it makes sense to work over a different group. Here we will look at an efficient implementation using modular arithmetic. We first need to review some facts. If p is a prime number, then Zp, the multiplicative group of integers mod p, has elements [1,2,...,p- 1 and group operation multiplication mod p. Any such group is cyclic, so it has a generator g, i.e., Ig.g1...,g"-2 gives us all the elements. Fermat's Little Theorem states that for any integer a, a a (mod p) (which also means that aP1 1 (mod p).) Let n be a power of 2, and let k be the smallest number such that p nk + 1 . Using the prime number theorem, we expect k to be around ign. Let g be a generator of Tp, and let w gk How does the expected length of the binary representation of p compare to that of n? Prove that w is a principle nth root of unity in a. b. Show how, using w, we can define the DFT and its inverse mod p, and prove that, assuming that arithmetic operations on words of length Olgn) have unit cost, we can perform the FFT mod p in time 0(nlgn). c. d. Using 3 as a generator of Zi7, compute the DFT mod 17 of (0,5,3,7,7,2,1,6)
