Description and Implementation of Number Theoretic Transforms.

摘要

This thesis summarizes the theory of number theoretic transforms (NTT's), and presents original examples to illustrate the theory. Concepts have been studied and compared in order to present them in a cohesive and unified manner. Software and hardware implementation of Fermat number transforms are discussed and compared with the Fourier Transform showing a substantial improvement in efficiency and accuracy. The main drawback of Fermat Number Transforms is a rigid relationship between the allowed sequence length and word length. Methods and other NTT's, for overcoming this problem are discussed. The theory has also been extended to two dimensions. (Author)