# What area's of mathematics are needed to make a basic understanding of the FFT algorithm ?

I know FFT is used in signal processing ( at last check), the Lucas-Lehmer Test and probably many other things. But what is the Fast Fourier Transform and what area's of math will help me understand transforms like it ( and yes I know of the area Fourier analysis, just not if anything about it) I've read a little of the FFT wikipedia article and some on DFT etc. But I'm not even sure I understand them enough. and yes I know it's not for simpletons like me.

• You can understand the discrete Fourier transform (and the FFT algorithm) using only linear algebra. I gave a short explanation of the DFT here: math.stackexchange.com/a/1944778/40119 – littleO Jul 27 '17 at 23:34
• The algorithm itself, at its core, is just a straightforward divide-and-conquer algorithm: if you have a vector $x$ of length $2^n$; divide it into the two vectors of length $2^{n-1}$ consisting of the even-index and the odd-index elements; and calculate the Fourier transforms of these two vectors recursively - then a small amount of mathematics allows you to express the Fourier transform of the original vector in terms of the Fourier transforms of the smaller vectors. – Daniel Schepler Jul 27 '17 at 23:41
• so is karatsuba in theory but I guess I'm just too stupid right now. – user451844 Jul 28 '17 at 11:28