Fast algorithm for the Fourier transform over finite fields and its VLSI implementation

Summary form only given. An algorithm for computing the Fourier transform over any finite field GF(p^m) has been developed. It requires only O(n log n)²/4) additions and the same number of multiplications for an n-point transform, and allows in some fields a further reduction of the number of multiplications to O(n log n). Unlike most other fast algorithms that are generalizations of the FFT algorithms over the complex field, the proposed algorithm is unique in that it makes use of the special algebraic properties of the finite field and has the same implementation structure over any field. Due to its high regularity and low computational complexity when both multiplications and additions are considered, the algorithm is very attractive when VLSI realization is intended.