CS 170, Spring 2021 Homework 3 A. Chiesa & J. Demmel
CS 170 Homework 3
Due 2/09/2021, at 10:00 pm
1 Study Group
List the names and SIDs of the members in your study group. If you have no collaborators,
write “none”.
2 Modular Fourier Transform
Fourier transforms (FT) have to deal with computations involving irrational numbers which
can be tricky to implement in practice. Motivated by this, in this problem you will demon-
strate how to do a Fourier transform in modular arithmetic, using modulo 5 as an example.
(a) There exists ω ∈ {0, 1, 2, 3, 4} such that ω are 4th roots of unity (modulo 5), i.e., solutions
to z4 = 1. When doing the FT in modulo 5, this ω will serve a similar role to the primitive
root of unity in our standard FT. Show that {1, 2, 3, 4} are the 4th roots of unity (modulo
5). Al
so show that 1 + ω + ω2 + ω3 = 0 (mod 5) for ω = 2.
(b) Using the matrix form of the FT, produce the transform of the sequence (0, 1, 0, 2) modulo
5; that is, multiply this vector by the matrix M4(ω), for the value ω = 2. Be sure to
explicitly write out the FT matrix you will be using (with specific values, not just powers
of ω). In the matrix multiplication, all calculations should be performed modulo 5.
(c) Write down the matrix necessary to perform the inverse FT. Show that multiplying by
this matrix returns the original sequence. (Again all arithmetic should be performed
modulo 5.)
(d) Now show how to multiply the polynomials 2×2 + 3 and x+ 3 using the FT modulo 5.
3 Inverse FFT
Recall that in class we defined Mn, the matrix involved in the Fourier Transform, to be the
following matrix:
Mn =