Fast, prime factor, discrete Fourier transform algorithms over \(\text{GF}(2^m)\) for \(8 \leqslant m \leqslant 10\) (Q2575622)

This paper proposes a recursive algorithm to compute DFT (Discrete Fourier Transform) transforms over \(\text{GF}(2^m)\) for longer transform lengths \(2^m-1\), where \(8\leq m\leq 10\) when the transform length is a prime integer. The algorithm has been obtained in combination of the modified Winograd algorithm for computing cyclic convolutions with the extended fast prime-factor DFT algorithm developed earlier by the authors. The complexity of 255-, 511-, and 1023-point transforms over \(\text{GF}(2^m)\) is compared to existing efficient algorithms. It is also shown that the proposed algorithm requires fewer operations than those of the conventional methods.