Research On FFT Algorithm Based On Finite Field And Its Application In Full Homomorphic Encryption Algorithm

Fast Fourier Transform(FFT)can realize real-time signal processing by combining with high-speed hardware,and is widely used in intelligent fields,such as image processing,biomedical,big data and cloud computing security.However,with the rapid development of Artificial Intelligence(AI),the underlying hardware is facing the bottleneck of insufficient computing capacity,and higher requirements are put forward for the underlying core algorithm.As a particularly important part in digital signal processing field,FFT algorithm although has greatly improved the calculating performance,the operation performance of the traditional FFT algorithm cannot meet the real-time requirements of high-speed hardware in the face of big points of FFT transforming huge computation in engineering and mobile terminal hardware resource constraints.So the optimization speed and reduced resource depletion is necessary.This paper focuses on FFT algorithm optimization,hardware implementation and application in full homomorphic encryption.The main work and innovation are as follows:Firstly,in view of FFT algorithm cannot meet the requirement of high rate and low resource utilization in the real number field and the complex domain,this paper introduces and improves FFT algorithm based on finite field.At first,in order to satisfy the underlying algorithm to accelerate the initial demand,constructing minimum polynomials by using circulation characteristic of the finite field to settle additive operation times of FFT algorithm,then the algorithm for the corresponding hardware is implemented and optimized,this paper design 15 points FFT hardware implementation framework based on GF(24),and finish verification on the FPGA,the results show that the number of logical units of FFT algorithm reduce by 145,and the maximum clock frequency of it increase from 299.94 MHz to 359.84 MHz by comparing with the Discrete Fourier Transform(DFT)in finite domain.Secondly,in view of the current traditional large integer multiplication having problems of long computing time and large resource depletion,this paper puts forward an improved Schonhage-Strassen algorithm based on FFT over the finite field,using the convolution theorem and a combination of a finite field to improve the large integer multiplication calculation rate in algorithms,then use a lightweight operation examples to show the calculation process,and complete the implementation of the corresponding design FPGA hardware,and finally verify the algorithm validity by using the simulation waveform.Finally,Fully Homomorphic Encryption as an important encryption algorithm has important research significance in cloud computing security,in view of large integer multiplication is a problem difficult to solve in the current fully homomorphic encryption scheme,this paper puts forward Schonhage-Strassen algorithm based on FFT over the finite field which is applied to the fully homomorphic encryption algorithm.At the same time,16 points FFT which is the most important computing unit is improved,and the improved performance of 16 points FFT algorithm optimize the fully homomorphic encryption scheme.Subsequently,the most important 16-point FFT in the algorithm is optimized on the FPGA,and the analysis of simulation and performance is carried out on the software tool.After optimization,the utilization of logical units was reduced by 56% and the maximum clock frequency was increased by about 219%,which verified the correctness and superiority of the optimization algorithm.