The cyclotomic fast Fourier transform is a type of fast Fourier transform algorithm over finite fields. This algorithm first decomposes a DFT into several circular convolutions, and then derives the DFT results from the circular convolution results. When applied to a DFT over , this algorithm has a very low multiplicative complexity. In practice, since there usually exist efficient algorithms for circular convolutions with specific lengths, this algorithm is very efficient.
is called linearized because , which comes from the fact that for elements
Notice that is invertible modulo because must divide the order of the multiplicative group of the field . So, the elements can be partitioned into cyclotomic cosets modulo :
where . Therefore, the input to the Fourier transform can be rewritten as
In this way, the polynomial representation is decomposed into a sum of linear polynomials, and hence is given by
Expanding with the proper basis , we have where , and by the property of the linearized polynomial , we have
This equation can be rewritten in matrix form as , where is an matrix over GF(p) that contains the elements , is a block diagonal matrix, and is a permutation matrix regrouping the elements in according to the cyclotomic coset index.
Note that if the normal basis is used to expand the field elements of , the i-th block of is given by:
which is a circulant matrix. It is well known that a circulant matrix-vector product can be efficiently computed by convolutions. Hence we successfully reduce the discrete Fourier transform into short convolutions.
When applied to a characteristic-2 field GF(2m), the matrix is just a binary matrix. Only addition is used when calculating the matrix-vector product of and . It has been shown that the multiplicative complexity of the cyclotomic algorithm is given by , and the additive complexity is given by .
^ abWu, Xuebin; Wang, Ying; Yan, Zhiyuan (2012). "On Algorithms and Complexities of Cyclotomic Fast Fourier Transforms Over Arbitrary Finite Fields". IEEE Transactions on Signal Processing. 60 (3): 1149–1158. doi:10.1109/tsp.2011.2178844.