Cyclotomic fast Fourier transform

ID: 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.

New to topics? Read the docs here!