# Radix-2\({}^{2}\) Algorithm for the Odd New Mersenne Number Transform (ONMNT)
###### Abstract  
This paper introduces a new derivation of the radix-2\({}^{2}\) fast algorithm for the forward odd new Mersenne number transform (ONMNT) and the inverse odd new Mersenne number transform (IONMNT). This involves introducing new equations and functions in finite fields, bringing particular challenges unlike those in other fields. The radix-2\({}^{2}\) algorithm combines the benefits of the reduced number of operations of the radix-4 algorithm and the simple butterfly structure of the radix-2 algorithm, making it suitable for various applications such as lightweight ciphers, authenticated encryption, hash functions, signal processing, and convolution calculations. The multidimensional linear index mapping technique is the conventional method used to derive the radix-2\({}^{2}\) algorithm. However, this method does not provide clear insights into the underlying structure and flexibility of the radix-2\({}^{2}\) approach. This paper addresses this limitation and proposes a derivation based on bit-unscrambling techniques, which reverse the ordering of the output sequence, resulting in efficient calculations with fewer operations. Butterfly and signal flow diagrams are also presented to illustrate the structure of the fast algorithm for both ONMNT and IONMNT. The proposed method should pave the way for efficient and flexible implementation of ONMNT and IONMNT in applications such as lightweight ciphers and signal processing. The algorithm has been implemented in C and is validated with an example. radix-2\({}^{2}\); ONMNT; IONMNT; fast algorithm +
Footnote †: journal:  
1
Footnote 1: School of Engineering, Newcastle University, Newcastle NE1 7 RU, UK  
2
Footnote 2: Department of Electrical Engineering, University of Tikrit, Tikrit P.O. Walsh-Hadamard Transform (WHT) to speed up the calculation. The split-radix algorithm has the lowest arithmetic complexity. It avoids the limitation of the radix-4 algorithm, which can only be applied for a transform length \(N\) with an odd power of 4. However, the structure of the split-radix algorithm is highly complex, and its implementation in a simple hardware system is challenging. A new class of fast algorithms called radix-2[12] algorithms has been proposed, incorporating a twiddle factor decomposition technique in an efficient divide and conquer method, which leads to a regular signal flow graph structure. The structure of the radix is a crucial factor in determining the architecture of the fast Fourier transform (FFT) [13] processor. A simple and regular radix structure allows for an efficient implementation of the architecture [14]. The radix-2\({}^{2}\) algorithm retains both the low multiplicative complexity of the radix-4 algorithm and the simple structure of the radix-2 algorithm. Thus, it solves both these limitations. This algorithm can be used directly for even values of \(n\), where \(N=2^{n}\), and for odd values of \(n\) simply by utilizing a mixed-radix algorithm at the beginning or end of the radix-2\({}^{2}\) algorithm. The radix-2\({}^{2}\) algorithm can, therefore, be implemented for any value of \(N\) that is a power of 2. Moreover, significant memory savings have been achieved using this algorithm [15]. Therefore, multiple efficient implementations of the radix-2\({}^{2}\) FFT algorithm have been proposed for application-specific integrated circuits (ASIC) [16] and field-programmable gate arrays (FPGA) [16; 17; 18], primarily in the field of wireless communication. Lightweight cryptography [19] is another area of research that can benefit from the efficient implementation of radix-2\({}^{2}\) algorithms in resource-constrained devices, such as in radio frequency identification (RFID), sensors, wireless Internet of Things (IoT) devices [20], smart home automation, telemedicine, smart money [21], healthcare, and military applications. Efficient hardware implementations [22] are important in lightweight cryptography. In recent years, number theoretic transform-based cryptographic systems have been proposed, especially for the IoT [23; 24; 25].