?
The polynomial based method for the discrete Fourier transform computation over the finite field
A novel method of construction of the discrete Fourier transform (DFT) over the finite field has been proposed. The method is based on a polynomial representation of the DFT computation. We choose to minimize the sum of the number of operations (multiplications and additions) over a finite field as the optimization criterion. The presented method consists in transforming the original polynomial, replacing the result with the remainder from dividing it by the modulus, and the multipoint evaluation of the resulted polynomials in several elements of a finite field. Thus, all stages of the DFT calculation can be reduced to calculating several cyclic convolutions, to which the techniques of the multipoint evaluation can also be applied. The matrix notation of both known algorithms and new ones allows one to easily estimate their computational complexities. The novel description of the DFT calculation algorithms in polynomial terms allows us to improve the known methods of the DFT calculation. The introduced methods have a regular structure, which simplifies their hardware implementation. According to the criterion of minimizing the sum of the number of multiplications and additions, for a large amount of DFT lengths, the method seems to have the least complexity among all known algorithms.
