# Radix-2\({}^{2}\) Algorithm for the Odd New Mersenne Number Transform (ONMNT)
###### Abstract
One of the advantages of number theoretic transforms such as ONMNT is the ability to use fast algorithms. As the radix-2\({}^{2}\) fast algorithm offers a simple butterfly structure while maintaining the multiplicative complexity of the radix-4 algorithm, the derivation of the radix-2\({}^{2}\) fast algorithm for ONMNT will improve the efficiency for ONMNT-based lightweight ciphers. In the literature, there are two main approaches to implementing the radix-2\({}^{2}\) algorithm. The first approach is based on multidimensional index mapping [26], while the second is the twiddle factor unscrambling technique [27]. In conventional multidimensional index mapping, the transform length \(N\) is mapped onto a multidimensional array, following a similar approach to the Cooley-Tukey algorithm. In the twiddle factor unscrambling technique [28], the segment is divided into \(N/4\) equal segments, and each smaller butterfly is rearranged to be in base 2 or bit-reversed order rather than in base 4 or in word-reversed order, which is typical for the general radix-4 algorithm. This technique is comparatively efficient, and in this paper, we use the twiddle factor unscrambling technique to derive a radix-2\({}^{2}\) algorithm for ONMNT. The benefit of using the bit-unscrambling technique is that a higher-order radix, such as 4, 8, 16 or 2\({}^{i}\), can use the same bit-unscrambling counter, which speeds up the calculation [29] without needing extra calculations and data processing. This fast algorithm can be used in a lightweight cipher, in which reducing the number of operations leads to a compact implementation and efficient convolution calculations in signal processing applications. In [30], the authors presented promising results on using the bit-unscrambling technique for radix 2\({}^{2}\). It showed the dual advantages of a simpler structure and a reduced number of calculations. However, the paper was limited to NMNT. ONMNT is a more recent GNMNT, and it offers strong diffusion performance [9]. Unlike NMNT and O\({}^{2}\)NMNT, the kernel matrix for ONMNT is transposed in the inverse transform. Moreover, the derivation of the ONMNT fast algorithm requires considering retrograde points. Fast algorithms for ONMNT using radix 2\({}^{2}\) have not been explored yet. Therefore, the aim of this paper is to develop the radix-2\({}^{2}\) fast algorithm for the calculation of the ONMNT and IONMNT. The original contributions of this paper are as follows:1. A novel mathematical derivation of a radix-\(2^{2}\) algorithm for ONMNT and the inverse ONMNT (IONMNT) using the radix-\(2^{2}\) bit-unscrambling technique. 2. A detailed derivation of the transform kernel relationships incorporating retrograde points. 3. Butterfly diagrams and signal flow graphs of the Radix-\(2^{2}\) algorithm for ONMNT and IONMNT. Regarding the rest of the paper, Section 2 describes the most common fast algorithms. Sections 3 and 4 provide a detailed derivation of the radix-\(2^{2}\) algorithm for the forward and inverse ONMNT with a butterfly diagram and a signal flow diagram, respectively. Section 5 discusses the arithmetic complexity of the proposed fast algorithm and compares it with direct calculation and radix-\(2^{2}\). Section 6 presents an example to demonstrate the accuracy of the proposed fast algorithm. Section 7 concludes the paper and provides suggestions for future work.