Closed-Form Orthogonal Number Theoretic Transform Eigenvectors and the Fast Fractional NTT

摘要

In this paper, we propose a new method to find the closed-form solution of Number Theoretic Transform (NTT) eigenvectors. We construct the complete generalized Legendre sequence over the finite field (CGLSF) and use it to solve the NTT eigenvector problem. We derive the CGLSF-like NTT eigenvectors successfully, including the case where the operation field is defined over the Fermat and Mersenne numbers. The derived NTT eigenvector set is orthogonal and has a closed form. It is suitable for constructing sub-NTT building blocks for NTT implementation. In addition, with different eigenvalue assignment rule, we can construct the fractional number theoretic transform (FNTT), including the fractional Fermat number transform (FFNT), the fractional complex Mersenne number transform (FCMNT), and the fractional new Mersenne number transform (FNMNT). They are the generalizations of the original transforms and all have the complexities of $O(Nlog_{2}N)$.