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 depend only on the fact that formula_4 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. Since the inverse DFT is the same as the DFT, but with the opposite sign in the exponent and a 1/"N" factor, any FFT algorithm can easily be adapted for it.