The cyclotomic fast Fourier transform is a type of fast Fourier transform algorithm over finite fields.
[1] This algorithm first decomposes a DFT into several circular convolutions, and then derives the DFT results from the circular convolution results.
, 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.
[2] 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
over a finite field GF(pm) is defined as where
is the N-th primitive root of 1 in GF(pm).
If we define the polynomial representation of
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
Fast Fourier transforms are just efficient algorithms evaluating the above matrix-vector product.
First, we define a linearized polynomial over GF(pm) as
, which comes from the fact that for elements
of the multiplicative group of the field
cyclotomic cosets modulo
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
, and by the property of the linearized polynomial
, we have This equation can be rewritten in matrix form as
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
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
Only addition is used when calculating the matrix-vector product of
It has been shown that the multiplicative complexity of the cyclotomic algorithm is given by