Unified algorithms for generalized new Mersenne number transforms

Abstract

The generalized new Mersenne number transforms (GNMNTs) have proved to be significant number theoretic transforms (NTTs) used to calculate convolutions and correlations accurately. In this paper, by applying the principles of the decimation-in-frequency (DIF) approach with appropriate relations in finite field modulo Mersenne primes, two new fast algorithms for computing odd NMNT (ONMNT) and odd-squared NMNT (O²NMNT) are introduced. Moreover, by formulating a unified index mapping scheme for data sequence, a close relationship between the structures of the developed algorithms has been established. As a result, it has been shown that only a single universal butterfly structure is adequate to execute both algorithms. Consequently, a unified implementation platform can be used to compute the ONMNT as well as the O²NMNT. The validity of the development has been checked via an example for fast calculations of different types of convolutions, using both the GNMNTs and the proposed algorithms.