From: jkreznar@ininx.com (John E. Kreznar)
Date: Wed, 16 Mar 94 03:31:07 PST
To: ritter@cactus.org
Subject: Block Mixing Transforms
In-Reply-To: <9403130516.AA27259@cactus.org>
Message-ID: <9403161038.AA02512@ininx>
MIME-Version: 1.0
Content-Type: text/plain


-----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-----