Cyclotomic fast Fourier transform

Cyclotomic Fast Fourier Transform (CFFT) is a specialized algorithm for efficiently computing the Fourier transform of sequences, particularly those with lengths that are power of a prime, like \( p^n \) where \( p \) is a prime number. CFFT leverages the properties of cyclotomic fields and roots of unity to achieve fast computation similar to traditional Fast Fourier Transform (FFT) algorithms but with optimizations that apply to the specific structure of cyclotomic polynomials.