Unified algorithms for generalized new Mersenne number transforms

Lujain S. Abdulla, Abdulmuttalib A-Wahab Hussein, Mounir Taha Hamood


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 (O2NMNT) 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 O2NMNT. 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.


decimation-in-frequency; fast transform algorithms; new mersenne number transforms; number theoretic transforms;

Full Text:


DOI: http://doi.org/10.12928/telkomnika.v21i6.25253


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

TELKOMNIKA Telecommunication, Computing, Electronics and Control
ISSN: 1693-6930, e-ISSN: 2302-9293
Universitas Ahmad Dahlan, 4th Campus
Jl. Ringroad Selatan, Kragilan, Tamanan, Banguntapan, Bantul, Yogyakarta, Indonesia 55191
Phone: +62 (274) 563515, 511830, 379418, 371120
Fax: +62 274 564604