This is true. I looked up CLR's treatment recently, and it was surprisingly readable (for CLR). It describes the FT as transforming a polynomial between its coefficient representation and point-value representation (n point values are sufficient to fully represent a polynomial of order-bound n). To yield the point values, the polynomial is evaluated at the n complex roots of unity, because these numbers have useful properties.
My background in math is thin when it comes to things like complex numbers, but the explanation more or less made sense to me. CLR was focused on how the FFT was useful for multiplication, so it didn't really go into all the things I would have liked to know.
My background in math is thin when it comes to things like complex numbers, but the explanation more or less made sense to me. CLR was focused on how the FFT was useful for multiplication, so it didn't really go into all the things I would have liked to know.