Fast, prime factor, discrete Fourier transform algorithms over GF(2m) for 8 ⩽ m ⩽ 10

In this paper it is shown that Winograd’s algorithm for computing convolutions and a fast, prime factor, discrete Fourier transform (DFT) algorithm can be modified to compute Fourier-like transforms of long sequences of 2m − 1 points over GF(2m), for 8 ⩽ m ⩽ 10. These new transform techniques can be used to decode Reed–Solomon (RS) codes of block length 2m − 1. The complexity of this new transform algorithm is reduced substantially from more conventional methods. A computer simulation verifies these new results.