Fourier Transform, Optical Computing, Technology, Next Generation Tech.
using the raw definition of the Fourier transform. However, this is only efficient if N​ is the product of many small factors. If N​ has large prime factors, such algorithms become much less efficient — typically, their complexity (without other optimizations) is at least Ω(p²)​ where p​ is the