-----BEGIN PGP SIGNED MESSAGE-----
A mixing transform is not unlike a "butterfly" section in a fast Fourier transform (FFT) [3]. But the usual FFT operates on complex values which are normally represented in floating-point. When implemented in fixed-point (as needed for mixing data blocks), the normal FFT butterfly expands the range of the input values, thus requiring a larger amount of storage (a larger block size) for the result. Fast Hadamard / Walsh transforms [2] behave similarly.
For cryptography, we need transforms which are "size preserving" so that we can perform fixed-size block operations (such as DES) either on the input data or on the transformed results. It was
This made me think of Ramesh C. Agarwal's work with Fermat Number Transforms in the 1970s. Are you familiar? I have copies of several of his papers. According to the abstract of ``Fast Convolution Using Fermat Number Transforms with Applications to Digitial Filtering'', IEEE Trans on Accoustics, Speech, and Signal Processing, Vol ASSP-22, No 2, 1974 April, ``...transform is proposed that is defined on a finite ring of integers with arithmetic carried out modulo Fermat numbers... the Fermat number transform implementation of convolution is exact, i.e., there is no roundoff error... Results... are... compared with the fast Fourier transform (FFT) showing a substantial improvement in efficiency and accuracy.'' John E. Kreznar | Relations among people to be by jkreznar@ininx.com | mutual consent, or not at all. -----BEGIN PGP SIGNATURE----- Version: 2.3a iQCVAgUBLYbha8Dhz44ugybJAQGafgP+Luj3zWlNJKOqaXmO8ZZbOcfGIfTI4yYy NKb2Xwz8nvPTJjZq4zSA60RC1zXOoc9e0hjz1VT2xmqfwAlRqcN0PMzsHeUjxGMH EXOlY9anHiUFWkLEYRMfe2KBP1y3FSt68gLVgx0pLBb5AIt2rOY9yyTQM/2G3CjU h+c15MziZg0= =k9i4 -----END PGP SIGNATURE-----