Research on Software Optimization for Discrete Fourier Test

Random sequences are critical to cryptographic technologies and applications. Randomness testing typically employs probabilistic statistical techniques for evaluating the randomness properties of such sequences. Both the National Institute of Standards and Technology (NIST, Gaithersburg, MD, U.S.) and the State Cryptography Administration (SCA, China) have issued guidelines for randomness testing, each of which includes the Discrete Fourier Transform (DFT) test as one of the mandatory assessments. This paper focuses on the efficient implementation of the DFT test and proposes a fast implementation approach that leverages FFTW (Fastest Fourier Transform in the West). Comprehensive experimental tests and performance evaluations were performed both before and after optimization of the algorithm. The results show that the optimized algorithm increases the speed of the DFT test for a single sample by a factor of 3.37.