I just had a course on the fourier transform a few weeks ago.
So let's say you have a finite signal in the form of a series x.
Now that series will have a number of T[0, 1, 2, ... N-1] moments where N>=2
Thus we can define the discrete Fourier Transform as:
f(k) = sum(n=0 -> N-1)(xn * v^kn) where v = e^(-i*2pi/N) and n and k are elements of T
The fast fourirer transform is an algorithm that is supposed to compute the value of this thing because if you were to compute it directly it would take N^2 calculations to do it.
The idea goes somewhat like this, if N is not a prime number than you can write it as N1*N2*...*Nm
For simplicity we're going to take just m=2.
because 0<=n,k<=N-1 you can definitely say that k = k1 * N2 + k2 and n=n2 * N1 + n1 where 0<=k1,n1<=N1-1 and 0<=k2,n2<=N2
In the light of these new relations you've got:
f(k) = sum(n=0->N-1)(x (n1,n2) * (v ^ k2 * n2 * N1) * v ^ k * n1)
which is sum(n1=0->N1-1)(sum(n2=0->N2-1)(x(n1,n2) * (v ^ k2 * n2 * N1) * v ^ k * n1))
Now we compute G(n1,k2) = sum(n2=0->N2-1)(x(n1,n2) * (v ^ k2 * n2 * N1)) which takes N*N2 steps
We then compute f(k1,k2) = sum(n1=0->N1-1)(G(n1,k2)*v^k*n1) which is going to take N*N1 steps
So this algorithm takes overall N(N1+N2)<N^2 steps
Hope this helps
