×

zbMATH — the first resource for mathematics

A method for fast computation of the Fourier transform over a finite field. (English. Russian original) Zbl 1074.65157
Probl. Inf. Transm. 39, No. 3, 231-238 (2003); translation from Prob. Peredachi Inf. 39, No. 3, 3-10 (2003).
Summary: We consider the problem of fast computation of the Fourier transform over a finite field by decomposing an arbitrary polynomial into a sum of linearized polynomials. Examples of algorithms for the Fourier transform with complexity less than that of the best known analogs are given.

MSC:
65T50 Numerical methods for discrete and fast Fourier transforms
PDF BibTeX XML Cite
Full Text: DOI