Proposal and Evaluation for Efficient splitfft and mergefft in FALCON

In recent years, there has been much research on post-quantum cryptography (PQC) in anticipation of the compromise of existing algorithms due to the development of quantum computers, and NIST has published standardization of PQC. In this research, we focus on one of the standardized algorithms, FALCON, a digital signature algorithm based on the NTRU problem, to improve its performance. We propose improvements to splitfft and mergefft to increase efficiency by using a quadtree structure instead of the binary tree structure used in ffSampling and other algorithms. As a result, the computation time for splitfft and mergefft was reduced.