Taking speed as an issue it may be better to choose another language, but what is your library/module/implementation of choice for doing a 1D fast Fourier transform (FFT) in Python?
I would recommend using the FFTW library ("the fastest Fourier transform in the West"). The FFTW download page states that Python wrappers exist, but the link is broken. A Google search turned up Python FFTW, which provides Python bindings to FFTW3.