Assertion: fft algorithm | /r/CapableOf | depend upon the factorization of n
Facets:
Source sentences:
text: The best-known FFT algorithms depend upon the factorization of N, but there are FFTs with O(N log N) complexity for all N, even for prime N. Many FFT algorithms only depend on the fact that e − 2 π i / N {\displaystyle e^{-2\pi i/N}} is an N-th primitive root of unity, and thus can be applied to analogous transforms over any finite field, such as number-theoretic transforms.