Block Mixing Transforms

John E. Kreznar jkreznar at
Wed Mar 16 03:31:07 PST 1994


> 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 at	| mutual consent, or not at all.

Version: 2.3a


More information about the cypherpunks-legacy mailing list