Cyclotomic fast Fourier transform

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 formula_1, 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.
Background.
The discrete Fourier transform over finite fields finds widespread application in the decoding of error-correcting codes such as BCH codes and Reed–Solomon codes. Generalized from the complex field, a discrete Fourier transform of a sequence formula_2 over a finite field GF("p""m") is defined as
where formula_4 is the "N"-th primitive root of 1 in GF("p""m"). If we define the polynomial representation of formula_2 as
it is easy to see that formula_7 is simply formula_8. That is, the discrete Fourier transform of a sequence converts it to a polynomial evaluation problem. 
Written in matrix format, 
Direct evaluation of DFT has an formula_10 complexity. Fast Fourier transforms are just efficient algorithms evaluating the above matrix-vector product.
Algorithm.
First, we define a linearized polynomial over GF(pm) as 
formula_12 is called linearized because formula_13, which comes from the fact that for elements formula_14formula_15
Notice that formula_16 is invertible modulo formula_17 because formula_17 must divide the order formula_19 of the multiplicative group of the field formula_20. So, the elements formula_21 can be partitioned into formula_22 cyclotomic cosets modulo formula_17: 
where formula_28. 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 formula_7 is given by 
Expanding formula_32 with the proper basis formula_33, we have formula_34 where formula_35, and by the property of the linearized polynomial formula_36, we have
This equation can be rewritten in matrix form as formula_38, where formula_39 is an formula_40 matrix over GF("p") that contains the elements formula_41, formula_42 is a block diagonal matrix, and formula_43 is a permutation matrix regrouping the elements in formula_44 according to the cyclotomic coset index. 
Note that if the normal basis formula_45 is used to expand the field elements of formula_46, the i-th block of formula_42 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.
Complexity.
When applied to a characteristic-2 field GF(2"m"), the matrix formula_39 is just a binary matrix. Only addition is used when calculating the matrix-vector product of formula_50 and formula_51. It has been shown that the multiplicative complexity of the cyclotomic algorithm is given by formula_52, and the additive complexity is given by formula_53.