Cooley-Tukey FFT: You don't have to zeropad to a power of 2? Someone wrote "The algorithm that Cooley and Tukey presented in their classic paper (Math. Comp. 19 (1965), 297-301. http://dx.doi.org/10.1090/S0025-5718-1965-0178586-1) can be applied to any composite length.  The performance advantages are greatest for highly composite lengths, of which powers-of-2 are one example, and lengths of powers-of-2 result in other advantages on binary computers, so it has become a common misconception that the algorithm is only applicable to signals whose length is a power of 2."

Does that mean that when you DO use the Cooley-Tukey FFT You don't have to zeropad to a power of 2?
Take for example an image of 1920x1080. So, if you want to use the Cooley-Tukey FFT, you don't need to zeropad that to 2048*2048?
Yes.  If you can factor length N, Cooley-Tukey will give you an DFT computation that uses less multiplies than an unfactored DFT.  A power of 2 factorization requires less lines of text or shorter equations to explain.  But any small prime factors allows a straight forward extension to the power-of-2 explanation or proof of the algorithm.

Many newer FFT libraries (iOS Accelerate for one example) allow efficient composite FFT lengths with factors of 2,3,5 and maybe more, thus requiring less padding to get to the next useful composite length.