Convolutions over residue classes of quadratic integers

A Fourier-like transform is defined over a ring of quadratic integers modulo a prime number in the quadratic field , where is a square-free integer. If is 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 in . 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 in modulo a nonprime Fermat number.