Research on FFT-Based Large Integers Multiplication

The most common use for fast Fourier transform is in high speed signal processing, encryption algorithms and other fields, which use the properties of primitive complex nth root of unity in complex number field. In order to implement the FFT-based large integers multiplication arithmetic whose time complexity is O(nlogn), this paper discusses how to select the primitive nth root of unity for FFT-based large integers multiplication under modulo-p arithmetic, where p is a prime or a composite number, further more, some related proofs which the primitive nth root of unit satisfies the condition of discrete Fourier transform (DFT) and its inverse are given too.