Fast Convolution by Number Theoretic Transforms.
Abstract
The concepts involved in the efficient computation of discrete convolution by number theoretic techniques were reviewed using key portions of the applicable technical literature. First, discrete convolution and its computation by direct and fast Fourier transform (FFT) techniques are reviewed. The discrete Fourier transform (DFT), defined in a finite field or ring, and applicable number theory concepts, are used to describe the number theoretic transform (NTT) and its circular convolution properties. The considerations in the selection of a modulus that results in efficient modular arithmetic on a binary computing device are discussed. The limitations in transform length are presented, along with means for overcoming this restriction. The complex number theoretic transform (CNT) defined in both a finite field and ring is described. Finally, the computational efficiency of NTT vs FFT convolution is discussed.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 12, 1975
- Accession Number
- ADA015276
Entities
People
- Lawrence M. Leibowitz
Organizations
- United States Naval Research Laboratory