Convolutions over residue classes of quadratic integers
I.S. Reed, Treiu-Kien Truong · IEEE Transactions on Information Theory · 1976
A Fourier-like transform is defined over a ring of quadratic integers modulo a prime numberqin the quadratic fieldR(\sqrt{m}), wheremis a square-free integer. Ifqis a Fermat prime, one can utilize the fast Fourier transform (FFT) algorithm over the resulting finite fields to yield fast convolutions of quadratic integer sequences inR(\sqrt{m}). The theory is also extended to a direct sum of such finite fields. From these results, it is shown that Fourier-like transforms can also be defined over the quadratic integers inR( \sqrt{m})modulo a nonprime Fermat number.