Radix-2² Algorithm for the Odd New Mersenne Number Transform (ONMNT)

Number theoretic transforms (NTTs) [1] have many applications [2] in signal processing and cryptography [1]. Two well-known NTTs are the Mersenne number transform (MNT) [3,4] and the Fermat number transform (FNT) [5,6], which are based on Mersenne numbers and Fermat numbers, respectively. MNT has been given particular attention as it has simple arithmetic and favorable reduction operations compared to FNT. However, MNT has limitations in terms of its transform length, which is short and has limited factorability, making it unfeasible to use the fast algorithm.

To address the limitations of MNT, Bousssakta and Holt introduced the new Mersenne number transform (NMNT) [7]. Later, two new variants named the odd new Mersenne number transform (ONMNT) and the odd square new Mersenne number transform (O²NMNT) were proposed; these are known as generalized new Mersenne number transforms (GNMNTs) [8]. These two transforms have shown promising results in signal processing, image processing, and cryptography [9]. Parameterized implementation, strong diffusion performance, and simple arithmetic operations are critical advantages of NMNT-based cryptographic ciphers over conventional ciphers.

One of the advantages of the NMNT family of transforms is their suitability for fast algorithms, as their transform length is always a power of 2. A detailed discussion on different fast algorithms such as radix-2, radix-4, and split-radix for NMNT and GNMNT can be found in [9,10]. Hue et al. [11] presented a realization of NMNT using the 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^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]. 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²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 ONMNMT and IONMNT.

The original contributions of this paper are as follows:

Regarding the rest of the paper, Section 2 describes the most common fast algorithms. Section 3 and Section 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.

ONMNT is the first of the two new NMNT-based transforms introduced by Boussakta et al. [8]. An odd member of the transform parameter is chosen to form the kernel matrix.

The ONMNT of an integer sequence $x\left(n\right)$, where $n=0,1,2,3,\cdots ,N-1$ with transform length $N=2^m$ for $m=1,2,3,\cdots ,p-1$, is defined as follows: where $k=0,1,2,\cdots ,N-1$, ${\langle .\rangle }_{M_p}$ represents modulo $M_p$ where $M_p=2^p-1$ is a Mersenne prime for $p=2,3,5,7,13,17,19,\cdots$ and $\beta \left(\frac{n(2k+1)}{2}\right)$ is the transform kernel. For the ONMNT, the transform kernel can be expressed by the following matrix:

The IONMNT is defined as follows: where $n=0,1,2,3,\cdots ,N-1$, $X_0\left(k\right)$ is the input sequence and $\beta \left(k\frac{2n+1}{2}\right)$ is the kernel parameter for IONMNT. When comparing (1) and (3), the IONMNT differs from the ONMNT in two ways: it has a scaling factor $N^{-1}$ and the transform matrix is transposed (i.e., $M_{o_i}=M_{o_f}^T$) to let the kernel matrix be orthogonal. Therefore, the following is the kernel matrix of the inverse ONMNT:

The maximum transform length for ONMNT is $N_{\max }=2^{p-1}$.

An ONMNT radix-$2^2$ algorithm can be developed by decomposing (1) into $2^2=4$ equal partial sums of transform length $\frac{N}{4}$, where $n=0,1,2,\cdots \frac{N}{4}-1$, and by replacing n with $4n+l$, where $l=0,1,2,\cdots \frac{N}{4}-1$. Therefore, (1) can be written as follows: where $x(4n+l)$ is the input sequence of each segment, $\beta \left((4n+l)\frac{2k+1}{2}\right)$ is the kernel parameter of ONMNT and ${\langle .\rangle }_{M_p}$ means that the calculation is modulo a Mersenne prime. From the above equation, it can be seen that the output $X^o\left(k\right)$ of the ONMNT is the summation of four equal segments $X^o\left(k+\lambda \frac{N}{4}\right)$ with $\frac{N}{4}$ consecutive elements indexed by $\lambda$ and where $0\le \lambda \le 3$. A general equation for each partial sum or segment is

In the next step of the derivation, the twiddle factor, $\beta (.)$ from (3), is simplified as follows:

Equation (7) can be expanded using the $\beta$ properties of $\beta (m+n)={\beta }_1\left(m\right)\beta \left(n\right)+{\beta }_2\left(m\right)\beta (-n)$ from [31] as follows: where, using the periodic property of $\beta \left(n\right)$, i.e., $\beta (aN+m)=\beta \left(m\right)$ [30], (8) can be written as follows:

Substituting ${\beta }_1(.)$ and ${\beta }_2(.)$ with the relations ${\beta }_1(m+n)={\beta }_1\left(m\right){\beta }_1\left(n\right)-{\beta }_2\left(m\right){\beta }_2\left(n\right)$ and ${\beta }_2(m+n)={\beta }_1\left(m\right){\beta }_2\left(n\right)+{\beta }_2\left(m\right){\beta }_1\left(n\right)$ from (9) into (7) yields the following:

Substituting the values from (10) into (3), ignoring the modulo operator ${\langle \rangle }_{M_p}$ and rearranging yields

The following two sequences, where $l=0,1,2$ and 3, can be defined:

Substituting $X_l^o\left(k\right)$ and $X_l^o\left(\frac{N}{4}-k-1\right)$ from (12) and (13) into (11), and rearranging and applying re-indexing l of ${\beta }_1\left(\frac{2k+1}{2}l\right)$ and ${\beta }_2\left(\frac{2k+1}{2}l\right)$ from (11) according to the bit reverse order, yields the following:

Equation (14) is the general decomposition equation. The four main points for radix $2^2$ are $X^o\left(k\right)$, $X^o\left(k+\frac{N}{4}\right)$, $X^o\left(k+\frac{N}{2}\right)$ and $X^o\left(k+\frac{3N}{4}\right)$, which are derived by setting $\lambda =0,1,2,3$ in (14) and using the following beta relationships:

Then, the following mapping relations are applied:

There are also four retrograde points. The butterfly diagram consists of all eight points. For ONMNT, the four retrograde points, $X^o\left(\frac{N}{4}-k-1\right)$, $X^o\left(\frac{N}{2}-k-1\right)$, $X^o\left(\frac{3N}{4}-k-1\right)$ and $X^o\left(N-k-1\right)$, can be derived by replacing k with $-k$, where $-k=\frac{N}{4}-k-1$, in (28)–(31) and using the following beta relations:

The proof of the beta relations (32)–(37) is given in Appendix A.

Figure 1 shows the butterfly diagram for radix-$2^2$ ONMNT using the four main points and the four retrograde points. The signal flow graph (SFG) for different transform lengths can be drawn using the ONMNT butterfly diagram presented in Figure 1. For example, SFG for $N=16$ using the ONMNT butterfly diagram is shown in Figure 2.

The derivation of the radix-$2^2$ algorithm starts by replacing $\left(\frac{2k+1}{2}\right)$ with $\left(\frac{2k+1}{2}+\lambda \frac{N}{4}\right)$ and n with $4n+l$ in $\left(2\right)$, where $\lambda =0,1,2,3$ and $l=0,1,2,3$, ignoring $\left(N^{-1}\right)$ in (3):

The twiddle factor from (38) can be written as follows:

Using the relationship $\beta (m+n)={\beta }_1\left(m\right).\beta \left(n\right)+{\beta }_2\left(m\right).\beta (-n)$ and the periodic properties of $\beta (.)$, (39) can be written as follows:

Using the relationships (41) and (42) yields and

Substituting (43) and (44) into (40) gives the updated values of $\beta (.)$:

Rearranging and simplifying (45) results in the following:

Substituting the value from (46) into (38) and ignoring ${\langle \rangle }_{M_p}$ for the derivation,

Reorganizing the equation and factoring out the shared summation term ${\sum }_{\lambda =0}^3$ from (47) yields the following result:

Let us define the two following terms:

Substituting the relations (49) and (50) into (48) leads to

Upon reorganizing the terms and isolating the common summation term ${\sum }_{k=0}^{\frac{N}{4}-1}(.)$ and $\beta \left(4n\frac{2k+1}{2}\right)$ from Equation (51), the result is as follows:

Equation (52) can be rewritten as follows: where

Expanding $\lambda$, substituting ${\beta }_2\left(a\frac{N}{2}\right)=0$ and rearranging (54) leads to the following:

By substituting $l=0,1,2$ and 3 in (55) using the $\beta$ relationships from (15)–(20) and applying the bit-unscrambling technique, the temporary main points are found as follows:

By substituting k with $-k$, where $-k=\frac{N}{4}-k-1$, in Equations (56)–(59), and employing the beta relations from (17)–(19), the outcome entails the determination of four temporary retrograde points: