Efficient Implementation of DFT over GF(qm)
Huapeng Wu · 2006
In this paper an algorithm to compute N-point DFT over a finite field qm without multiplication is proposed, where q is a prime power and N is a positive integer not divisible by the characteristic of Fqm. The proposed method uses redundant representation for field elements and it is shown that no multiplication operations in Fqare required for computing N-point DFT. Both bit-serial and bit-parallel architectures to realize the algorithm are also presented that use only finite field adders and registers. One constrain of this method is that m must divide the multiplicative order of q mod N.