which FPGA chip to use for FFT?

Hello,

I have made a program which calculate FFT of two images (1024X1024) and
then convolve them. I wish to know which FPGA chips would be best for this
task, I want the result of the algorithm in real time (more than 30hz). It
takes around 10 seconds on my machine(AMD 1.8 Ghz Dual Core) for just one
convolution of both the images. I am thinking to use xilinx XC3S500E (500k
gates). I have no experience in FPGA, if anyone can help me i would really
appreciate. 

Thanks