# Radix-2\({}^{2}\) Algorithm for the Odd New Mersenne Number Transform (ONMNT)
## 5 Arithmetic Complexity of Radix-\(2^{2}\) Algorithm  
There are two general formulas for computing complexity: the closed formula used for single-butterfly implementation and the recursive formula used for multiple-butterfly implementation. In this paper, we used single-butterfly implementation for simplicity in calculation. The arithmetic complexity is a summation of the number of initial additions and multiplications in a single butterfly, along with the number of stages and points. A comparison of arithmetic complexity for ONMNT using direct calculations for the radix-\(2\) and radix-\(2^{2}\) algorithms is presented below. In the direct calculation of the transform, the numbers of addition and multiplication operations are \(N(N-1)\) and \(N^{2}\), respectively, where \(N\) is the transform length. The number of stages in the radix-\(2\) fast algorithm is \(\log_{2}(N)\). Each butterfly processes \(N/4\) points and requires 6 additions and 4 multiplications using the single-butterfly implementation. Therefore, the number of additions \(A(N)\) and multiplications \(M(N)\) for radix 2 can be calculated using the following equations:  
\[A(N) = \frac{N}{4}6\log_{2}(N)=\frac{3N}{2}\log_{2}(N) \tag{67}\] \[M(N) = \frac{N}{4}4\log_{2}(N)=N\log_{2}(N) \tag{68}\]  
In the radix-\(2^{2}\) algorithm, the number of stages \(S\) is \(\log_{4}(N)\) or \(\frac{1}{2}\log_{2}(N)\), where \(N\) is the number of points in each butterfly. The numbers of multiplication and addition operations required in each stage are 12 and 22, respectively. As the radix-\(2^{2}\) butterfly has eight points--four main points and four retrograde points--the number of points to calculate at each stage is \(\frac{N}{8}\). Therefore, the arithmetic complexity can be calculated in terms of the number of additions \(A(N)\) and the number of multiplications \(M(N)\) using the following equations:  
\[A(N) = \frac{N}{8}\times 22\times\frac{1}{2}\log_{2}N=\frac{11N}{8}\log_{ 2}(N) \tag{69}\] \[M(N) = \frac{N}{8}\times 12\times\frac{1}{2}\log_{2}N=\frac{3N}{4}\log_{ 2}(N) \tag{70}\]  
Figure 5 shows the total calculations for direct calculations, radix-\(2\), and radix-\(2^{2}\), in a graph where the x-axis shows the transform length in the logarithm scale and the y-axis shows the total number of calculations, including addition and multiplication. As can be seen from the figure, both the radix-\(2\) and radix-\(2^{2}\) algorithms require significantly fewer calculations than the direct method. Moreover, the total number of calculations increases exponentially as the transform length increases.  
Table 1 presents the number of additions, multiplications, and total calculation required for ONMNT using a direct calculation as well as the radix-\(2\) and radix-\(2^{2}\) algorithms for transform length \(N=8,16,32,64,128\) and \(256\). Comparing (67) and (68) with (69) and (70) for direct calculations, the numbers of saved operations in the radix-\(2^{2}\) algorithm relative to radix 2 can be written as follows:  
\[\Delta A(N) = \frac{N}{8}\log_{2}(N) \tag{71}\] \[\Delta M(N) = \frac{N}{4}\log_{2}(N) \tag{72}\]The radix-2\({}^{2}\) algorithm offers an 8.55% reduction in the number of additions and a 25% reduction in the number of multiplications compared to radix 2. It is important to note that the multiplication operation is more CPU-intensive than the addition operation, so a 25% saving in the number of multiplications in the radix-2\({}^{2}\) algorithm is notable and makes it more suitable for a lightweight cipher application. Overall, this algorithm achieves a 15% reduction in total calculations. The number of calculations for radix-4 and split radix is not included in the comparison because the transform length of radix-4 [32] fast algorithm is only limited to the power of 4, and it has more complex implementations than radix-2\({}^{2}\). Radix-2\({}^{2}\) has the same non-trivial multiplicative complexity of radix-4, but it retains the butterfly structure of radix-2 [33]. The saving percentage will be higher as the transform length increases.