Transforms, Finite Fields, and Fast Multiplication

Introduction The theme of a transform arises frequently. It entails transforming a problem into a setting where the new problem can be solved more easily and then applying the inverse transform to bring the solution back to the desired form. This is the general idea behind the fast Fourier transform (FFT) in a finite field for doing fast multiplication of large integers with absolute precision. Possible applications are to primality testing and cryptography where perfect accuracy is crucial. Long ago in the seventeenth century, one highly effective use of a transform to make multiplication more tractable had been discovered, and was indispensable up to the computer age. In 1614 John Napier invented logarithms which transformed the multiplication problem into simple addition of exponents. Shortly after, Edward Gunter and William Oughtred built the powerful mechanical realization: the slide rule ([4, p. 247]).