The natural way to go here is through Discrete Fourier transform. Let be a root of unity, namely . Define Then it is clear that . Log in to Reply

The natural way to go here is through Discrete Fourier transform. Let be a root of unity, namely . Define

Then it is clear that .