Fractional Fourier, Hartley, Cosine and Sine Number-Theoretic Transforms Based on Matrix Functions

Abstract

In this paper, we introduce fractional number-theoretic transforms (FrNTT) based on matrix functions. In contrast to previously proposed FrNTT, our approach does not require the construction of any number-theoretic transform (NTT) eigenvectors set. This allows us to obtain an FrNTT matrix by means of a closed-form expression corresponding to a linear combination of integer powers of the respective NTT matrix. Fractional Fourier, Hartley, cosine and sine number-theoretic transforms are developed. We show that fast algorithms applicable to ordinary NTT can also be used to compute the proposed FrNTT. Furthermore, we investigate the relationship between fractional Fourier and Hartley number-theoretic transforms, and demonstrate the applicability of the proposed FrNTT to a recently introduced image encryption scheme.

1 Introduction

The inaugural investigations related to fractional transforms date back to the first half of the twentieth century [11, 39]. In such studies, the computation of a Fourier transform is viewed as the application of a linear operator, the Fourier operator, to a function (or signal) whose spectrum one desires to obtain; the fractional Fourier transform (FrFT) corresponds to a generalization, where noninteger powers of the Fourier operator can be considered. This enables a diversity of possibilities, which remained hidden until the 1980s, when the FrFT was rediscovered. In quantum mechanics, optics and signal processing, the FrFT has reappeared as a useful mathematical tool, with applications based on new theoretic results and interesting interpretations [2, 27–29].

In the time–frequency plane, the computation of the FrFT of a signal in the time domain (horizontal axis to the right) can be viewed as a counterclockwise rotation by an angle $\alpha =a\pi /2, a\in \mathbb {R}$. If a is noninteger, the signal is taken to an intermediate domain, which represents, in the physical point of view, something like a hybrid domain between time and frequency [2]. In optics, the FrFT is related to systems whose output corresponds to the Fourier transform of the input signal [27, 29]. These systems produce sequences of images of an object. In certain distances, the object itself as well as its Fourier transform is observed; in arbitrary distances, the FrFT of the object is obtained.

The fractional Fourier transform inspired the definition of fractional Hartley, cosine and sine transforms, among others [3, 30]. Furthermore, discrete fractional transforms have also been introduced [8, 31, 34]. In particular, there are several approaches for constructing a discrete fractional Fourier transform (DFrFT) [8, 32, 37]. Besides allowing the employment of fast algorithms in its computation, a DFrFT should numerically approximate the corresponding continuous-time transform and preserve some of its properties.

More recently, fractional number-theoretic transforms (NTT) were proposed. In [33], for example, closed-form orthogonal NTT eigenvector sets are constructed from complete generalized Legendre sequences. Such sets are then used to spectrally expand the NTT matrix and to compute its fractional powers. The method introduced in [21] is also based on the spectral expansion of the NTT matrix. However, in this case, orthogonal NTT eigenvectors are obtained from an extension to the finite field scenario of a matrix which commutes with the NTT matrix; the eigenvectors derived through this approach can be viewed as finite field Hermite–Gaussian vectors.

In this paper, we generalize the ideas introduced in [25] and describe several types of new fractional number-theoretic transforms based on matrix functions [14]. This approach involves concepts which are also valid for matrices whose elements lie in a finite field, such as the Lagrange interpolation polynomial for a given function and the minimal polynomial of a matrix. Given a transform matrix $\mathbf{{M}}$, our goal is computing $f(\mathbf{{M}})=\mathbf{{M}}^a$, where the fractional parameter $a=a_1/a_2$ is a ratio of two integers. Compared with previous works concerning fractional NTT [21, 33], our proposal has two main advantages. First, it does not require the construction of NTT eigenvector sets, which usually constitutes a laborious task from the point of view of computational complexity. Furthermore, since the fractional transform matrices resulting from the proposed procedure correspond to a linear combination of integer powers of the respective ordinary transform matrices, standard fast algorithms can be straightly employed.

Although the best-known NTT can be viewed as a finite field analogous of the discrete Fourier transform (DFT),¹ other types of NTT have been introduced in recent years. Cosine and Hartley NTT, for example, have interesting properties and can be used in applications related to information hiding, image encryption, communications, etc. [10, 12, 18, 24] In the present work, we also consider such transforms and show how the matrix functions approach can be applied to fractionalize them. In order to avoid ambiguities and contribute to the readability of our text, we adopt the following nomenclature:

$$\begin{aligned} \hbox {FNT}\quad&\hbox {Fourier number-theoretic transform}\\ \hbox {HNT}\quad&\hbox {Hartley number-theoretic transform}\\ \hbox {CNT}\quad&\hbox {Cosine number-theoretic transform}\\ \hbox {SNT}\quad&\hbox {Sine number-theoretic transform}\\ \hbox {FrFNT}\quad&\hbox {Fractional Fourier number-theoretic transform}\\ \hbox {FrHNT}\quad&\hbox {Fractional Hartley number-theoretic transform}\\ \hbox {FrCNT}\quad&\hbox {Fractional cosine number-theoretic transform}\\ \hbox {FrSNT}\quad&\hbox {Fractional sine number-theoretic transform}\\ \mathrm {GF}(p)\quad&\hbox {Finite field with} p \ \hbox {elements} \end{aligned}$$

This paper is organized as follows. In Sect. 2, we review the main concepts related to trigonometry over finite fields and number-theoretic transforms. In Sect. 3, we develop the NTT fractionalization approach based on matrix functions and use it to define the FrFNT, the FrHNT, the FrCNT, and the FrSNT. The relationship between the FrFNT and the FrHNT is presented in Sect. 4. In Sect. 5, we give some illustrative examples regarding fractional NTT. The image encryption scheme proposed in [19] is revisited in Sect. 6; we show that, using fractional NTT based on matrix functions, its implementation becomes simpler, while its robustness against the main cryptographic attacks remains unaltered. The paper closes with some concluding remarks on Sect. 7.

2 Preliminaries

2.1 Cosine and Sine over Finite Fields

In this section, we present a definition for cosine and sine functions over finite fields. Such finite field trigonometric functions were originally introduced in [7], as a requirement for defining a Hartley number-theoretic transform, and are computed with respect to elements in the set of Gaussian integers over finite fields, $\mathrm {GI}(p)$. This set is isomorphic to the extension field $\mathrm {GF}(p^2)$ and provides an analogy with classical complex numbers.

Definition 1

The set of Gaussian integers over $\mathrm {GF}(p)$ is the set $\mathrm {GI}(p) := \{ c + jd, c, d \in \mathrm {GF}(p)\}$, where $j^2$ is a quadratic nonresidue over $\mathrm {GF}(p)$.

The elements $\zeta =c+jd$ of the “complex” structure $\mathrm {GI}(p)$ have a “real” part $c=\mathfrak {R}\{\zeta \}$ and an “imaginary” part $c=\mathfrak {I}\{\zeta \}$. If $p\equiv 3\,(\mathrm {mod}\,\,4)$, one may use $j=\sqrt{-1}\equiv \sqrt{p-1}\,(\mathrm {mod}\,\,p)$, for example. However, if $p\equiv 1\,(\mathrm {mod}\,\,4), -1\equiv p-1\,(\mathrm {mod}\,\,p)$ is a quadratic residue and another j has to be selected [6].

Definition 2

Let $\zeta \in \mathrm {GI}(p)$ be an element with multiplicative order denoted by $\mathrm {ord}(\zeta ) = N$. The finite field cosine and the finite field sine of the arc related to $\zeta ^x$ are computed modulo p, respectively, by

$$\begin{aligned} \cos _{\zeta }(x):= & {} \frac{\zeta ^{x} + \zeta ^{-x}}{2 } \end{aligned}$$

(1)

and

$$\begin{aligned} \sin _{\zeta }(x):= & {} \frac{\zeta ^{x} -\zeta ^{-x}}{2j }, \end{aligned}$$

(2)

for $x = 0, 1, \ldots , N-1$.

2.2 Number-Theoretic Transforms

In what follows, we define Fourier, Hartley, cosine and sine number-theoretic transforms [5, 7, 20]. Compared with usual NTT definitions, where vectors whose elements lie in $\mathrm {GF}(p)$ are considered, we consider a more general case, where vectors whose elements lie in $\mathrm {GI}(p)$ can be transformed.

Definition 3

Let $\zeta \in \mathrm {GI}(p)$ be an element of multiplicative order $\mathrm {ord}(\zeta ) = N$. The Fourier number-theoretic transform (FNT) of an N-length vector $\mathbf{{x}} = \left( x[i]\right) , x[i] \in \mathrm {GI}(p)$, is an N-length vector $\mathbf{{X}}_F = \left( X_F[k]\right) , X_F[k] \in \mathrm {GI}(p)$, given by

$$\begin{aligned} X_F[k] := \sqrt{N^{-1}}\sum _{i=0}^{N-1}{x[i]\zeta ^{-ki}}. \end{aligned}$$

(3)

The inverse transform is given by

$$\begin{aligned} x[i] = \sqrt{N^{-1}}\sum _{k=0}^{N-1}{X_F[k]\zeta ^{ki}}. \end{aligned}$$

Definition 4

Let $\zeta \in \mathrm {GI}(p)$ be an element of multiplicative order $\mathrm {ord}(\zeta ) = N$. The Hartley number-theoretic transform (HNT) of an N-length vector $\mathbf{{x}} = \left( x[i]\right) , x[i] \in \mathrm {GI}(p)$, is an N-length vector $\mathbf{{X}}_H = \left( X_H[k]\right) , X_H[k] \in \mathrm {GI}(p)$, given by

$$\begin{aligned} X_H[k] := \sqrt{N^{-1}}\sum _{i=0}^{N-1}{x[i]\mathrm {cas}_{\zeta }(ki)}, \end{aligned}$$

(4)

where $\mathrm {cas}_{\zeta }(\cdot ) := \cos _{\zeta }(\cdot ) + \sin _{\zeta }(\cdot )$. The inverse transform is also obtained from the expression above, i.e., the Hartley transform is an involution.

The family of trigonometric number-theoretic transforms includes eight types of cosine transforms (CNT) and eight types of sine transforms (SNT) [20]. The construction of a trigonometric NTT is based on symmetric extensions of a sequence whose elements are in a finite field and requires the weighting function

$$\begin{aligned} \beta [r] = \left\{ \, \begin{array}{ll} \sqrt{2^{-1}} \,\,(\mathrm {mod} \,\, p), &{}\quad r=0 \,\,\mathrm {or}\,\, N,\\ &{}\quad r=1,2, \ldots , N-1. \end{array} \right. \end{aligned}$$

Definition 5

Let $\zeta \in \mathrm {GI}(p)$ be an element of multiplicative order $\mathrm {ord}(\zeta ) = 2N$. The cosine number-theoretic transforms of types 1 and 4 (respectively, denoted by CNT-1 and CNT-4) of $(N+1)$- and N-length vectors $\mathbf{{x}}$ are, respectively, given by

$$\begin{aligned} X_{C_{1}}[k] := \sqrt{\frac{2}{N}}\,\sum _{i=0}^{N}\beta [i]\,\beta [k]\,x[i]\,\cos _{\zeta }(ki), \end{aligned}$$

(5)

$k=0,1,\ldots ,N$, and

$$\begin{aligned} X_{C_{4}}[k] := \sqrt{\frac{2}{N}}\,\sum _{i=0}^{N-1}\,x[i]\,\cos _{\zeta } \left( \left( k+\frac{1}{2}\right) \left( i+\frac{1}{2}\right) \right) , \end{aligned}$$

(6)

$k=0,1,\ldots ,N-1$.

Definition 6

Let $\zeta \in \mathrm {GI}(p)$ be an element of multiplicative order $\mathrm {ord}(\zeta ) = 2N$. The sine number-theoretic transforms of types 1 and 4 (respectively, denoted by SNT-1 and SNT-4) of $(N-1)$- and N-length vectors $\mathbf{{x}}$ are, respectively, given by

$$\begin{aligned} X_{S_{1}}[k] := \sqrt{\frac{2}{N}}\,\sum _{i=1}^{N-1}x[i]\,\sin _{\zeta }(ki), \end{aligned}$$

(7)

$k=1,2,\ldots ,N-1$, and

$$\begin{aligned} X_{S_{4}}[k] := \sqrt{\frac{2}{N}}\,\sum _{i=0}^{N-1}x[i]\,\sin _{\zeta } \left( \left( k+\frac{1}{2}\right) \left( i+\frac{1}{2}\right) \right) , \end{aligned}$$

(8)

$k=0,1,\ldots ,N-1$.

We remark that, although an element $\zeta \in \mathrm {GI}(p)$ of multiplicative order $\mathrm {ord}(\zeta )=2N$ is used to define each CNT and SNT, transforms of different lengths are obtained ($N, N+1$, and $N-1$). This is due to differences among the symmetric extension criteria employed in the construction of each transform type. A complete explanation regarding this aspect can be found in [20, 26]. CNT and SNT of types 1 and 4 are also involutions.

2.3 Eigenstructure of Number-Theoretic Transforms

The computation of each transform defined in Sect. 2.2 can be expressed by the matrix equation $\mathbf{{X}}= \mathbf{{Mx}}$, where $\mathbf{{x}}$ is the vector to be transformed, $\mathbf{{X}}$ is the transform vector, and $\mathbf{{M}}$ is a transform matrix. In particular, the FNT of a vector $\mathbf{{x}}$ can be expressed by $\mathbf{{X}}_F = \mathbf{{Fx}}$, where the element in the kth row and the ith column of $\mathbf{{F}}$ is $[\mathbf{{F}}]_{k,i} = \sqrt{N^{-1}}{\zeta ^{-ki}}$. The inverse of $\mathbf{{F}}$ is $\mathbf{{F}}^{-1} = \mathbf{{PF}}$, where $\mathbf{{P}}$ is an $N \times N$ Schur matrix [4] given by

$$\begin{aligned} \mathbf{{P}} = \left[ \begin{array}{ll} 1 &{}\quad \mathbf{{0}}\\ \mathbf{{0}} &{} \quad \mathbf{{J}} \end{array} \right] , \end{aligned}$$

(9)

and $\mathbf{{J}}$ is an $(N-1)\times (N-1)$ matrix with ones in the antidiagonal.

The matrix $\mathbf{{F}}$ has period equal to 4, i.e., $l= 4$ is the least positive integer such that $\mathbf{{F}}^l = \mathbf{{I}}$, where $\mathbf{{I}}$ is the identity matrix. On the other hand, the matrices related to the HNT, the CNT-1, the CNT-4, the SNT-1, and the SNT-4, respectively, denoted by $\mathbf{{H}}, \mathbf{{C}}_1, \mathbf{{C}}_4, \mathbf{{S}}_1$, and $\mathbf{{S}}_4$, are unitary and also symmetric. This means that such matrices have period equal to 2 [7, 24]. These facts can be used to determine the eigenvalues of each transform matrix as well as their multiplicities. Such results are summarized in the following proposition [4, 24, 31].

Proposition 1

The eigenvalues of an NTT matrix are distributed as follows:

• The matrix $\mathbf{{F}}$ has, at most, four distinct eigenvalues, namely $\left\{ 1,-1,\sqrt{-1},\right. \left. -\sqrt{-1} \right\}$, whose multiplicities are shown in Table 1;

• The matrix $\mathbf{{H}}$ has, at most, two distinct eigenvalues, namely $\{1,-1\}$, whose multiplicities are shown in Table 1;

• The matrices $\mathbf{{C}}_1, \mathbf{{C}}_4, \mathbf{{S}}_1$, and $\mathbf{{S}}_4$ have, at most, two distinct eigenvalues, namely $\{1,-1\}$, whose multiplicities are shown in Table 2.

Table 1 Multiplicities of the eigenvalues of $N\times N$ matrices of the FNT and the HNT

Table 2 Multiplicities of the eigenvalues of $N{'} \times N{'}$ matrices ($N'$ can be equal to $N, N-1$ or $N+1$) of the CNT and the SNT of types 1 and 4

3 Finite Field Fractional Transforms Based on Matrix Functions

The approach presented in this section is based on matrix functions [14], whose theory can be described using concepts which are valid also in the finite field scenario. Such concepts include, for example, the Lagrange interpolating polynomial for a given function and the minimal polynomial of a matrix [17]. Our goal is to compute the function $\mathbf{{A}}^a$, where $\mathbf{{A}}$ is an NTT matrix and a is a rational number called fractional parameter. We start by considering the minimal polynomial of $\mathbf{{A}}$, which is defined as the unique monic polynomial $\psi$ of lowest degree such that $\psi (\mathbf A ) = 0$. The minimal polynomial divides any other polynomial r for which ${r}(\mathbf{{A}}) = 0$. According to the following theorem, ${r}(\mathbf{{A}})$ is completely determined by the values of r on the spectrum of $\mathbf{{A}}$.

Theorem 1

Let r and s be polynomials and $\mathbf{{A}}$ be an $N \times N$ matrix over a finite field. Then $r(\mathbf{{A}}) = s(\mathbf{{A}})$ if and only if r and s take the same values on the spectrum of $\mathbf{{A}}$.

The proof of Theorem 1 is analogous to that presented for Theorem 1.3 on p. 5 of [14]. This result can be generalized to an arbitrary function f considering the following definitions.

Definition 7

Let $\lambda _1, \lambda _2, \ldots , \lambda _v$ be the distinct eigenvalues of $\mathbf{{A}}$, and let $n_i$ be the dimension of the largest Jordan block in which $\lambda _i$ appears. We say that f(t) is defined on the spectrum of $\mathbf{{A}}$ if the kth derivatives

$$\begin{aligned} f^{(k)}(\lambda _i), \quad k = 0, 1, \ldots , n_i-1, \quad i = 1, \ldots , v, \end{aligned}$$

(10)

called the values of f(t) on the spectrum of $\mathbf{{A}}$, exist.

Definition 8

Let f be a polynomial defined on the spectrum of an $N \times N$ matrix $\mathbf{{A}}$ over a finite field, and let $\psi$ be the minimal polynomial of $\mathbf{{A}}$. Then $f (\mathbf{{A}}) = r(\mathbf{{A}})$, where r is the polynomial of degree less than $\deg (\psi )$ that satisfies the interpolation condition

$$\begin{aligned} r^{(k\,)}(\lambda _i) = f^{(k\,)}(\lambda _i), \end{aligned}$$

(11)

$k= 0,1, \ldots , n_i -1,\, i = 1,2,\ldots , v$. If $n_i = 1, i = 1, \ldots , v$, the polynomial r corresponds to the Lagrange interpolating polynomial [17]

$$\begin{aligned} r(t) = \sum _{i=1}^{v}{f(\lambda _i)l_i(t)}, \end{aligned}$$

(12)

where

$$\begin{aligned} l_i(t) = \prod _{{\begin{array}{c}j=1,j\ne i\end{array}}}^{v}{\frac{t- \lambda _j}{\lambda _i -\lambda _j }}. \end{aligned}$$

(13)

In order to use Definition 8 to compute the a th power of a transform matrix, we set $r(t) = t^a$, where $a = a_1/a_2, a_2 \ne 0$, is a ratio of two integers; the variable t is replaced by the corresponding NTT matrix. In what follows, we give details related to the development of this approach to each NTT defined in Sect. 2.

3.1 Fractional Fourier Number-Theoretic Transform

The fractional Fourier number-theoretic transform (FrFNT) of an N-length vector $\mathbf{{x}}$ is computed as $\mathbf{{X}}_{a,F} = \mathbf{{F}}^{a}{} \mathbf{{x}}$. According to Proposition 1, the FNT matrix has four distinct eigenvalues $\lambda \in \{1,-1,\sqrt{-1},-\sqrt{-1} \}$ and, therefore, $v = 4$. Thus, the functions $l_i(t), i = 0,1,2,3$, defined in Eq. (13), are

$$\begin{aligned} l_1(t)= & {} \frac{t^3+ t^2 + t + 1}{4},\\ l_2(t)= & {} \frac{-t^3+ t^2 - t + 1}{4},\\ l_3(t)= & {} \frac{\sqrt{-1}\,t^3 - t^2 - \sqrt{-1}\,t + 1}{4}\\ \end{aligned}$$

and

$$\begin{aligned} l_4(t) = \frac{-\sqrt{-1}\,t^3 - t^2 + \sqrt{-1}\,t + 1}{4}. \end{aligned}$$

From Eq. (12), one has

$$\begin{aligned} r(t) = l_1(t) + (-1)^{\,a}l_2(t) + (\sqrt{-1})^{\,a}l_3(t) + (-\sqrt{-1})^{a}l_4(t). \end{aligned}$$

Grouping the coefficients of each power of t and setting $\alpha _i(a) = \alpha _i(a_1,a_2)$ as the coefficient of the ith power of t, one has

$$\begin{aligned} r(t) = \sum ^{3}_{i=0}{\alpha _i(a_1,a_2)}t^i, \end{aligned}$$

where

$$\begin{aligned} \alpha _0(a_1,a_2)&= \frac{1+(\sqrt{-1})^a + (-1)^a + (-\sqrt{-1})^a}{4}\nonumber \\&=\frac{1}{4} \left[ (\root 2a_2\, \of {-1})^{a_1}\left( 1+(\root 2a_a\, \of {-1})^{a_1} \right) + (\root 2a_2\, \of {-1})^{-a_1}\left( 1+(\root 2a_a\, \of {-1})^{a_1} \right) \right] \nonumber \\&=\frac{\,1+(\root 2a_2\, \of {-1\,})^{a_1}}{2}\cos _{\root \,2a_2\, \of {-1\,}}(a_1), \end{aligned}$$

(14)

$$\begin{aligned} \alpha _1(a_1,a_2)&= \frac{\,1-\sqrt{-1}(\root 2a_2\, \of {-1\,})^{a_1}}{2}\sin _{\root \,2a_2\, \of {-1\,}}(a_1), \end{aligned}$$

(15)

$$\begin{aligned} \alpha _2(a_1,a_2)&= \frac{-1+(\root 2a_2\, \of {-1\,})^{a_1}}{2}\cos _{\root \,2a_2\, \of {-1\,}}(a_1), \end{aligned}$$

(16)

$$\begin{aligned} \alpha _3(a_1,a_2)&= \frac{-1-\sqrt{-1}(\root 2a_2\, \of {-1\,})^{a_1}}{2}\sin _{\root \,2a_2\, \of {-1\,}}(a_1). \end{aligned}$$

(17)

Finally, the FrFNT matrix with fractional parameter $a = a_1/a_2$ is computed as

$$\begin{aligned} \mathbf F ^a = \mathbf F ^{\frac{a_1}{a_2}} = r(\mathbf F ) = \sum ^{3}_{i=0}{\alpha _i(a_1,a_2)}{} \mathbf F ^i. \end{aligned}$$

(18)

3.2 Fractional Hartley, Cosine and Sine Number-Theoretic Transforms

In order to define fractional Hartley (FrHNT), cosine of type 1 (FrCNT-1) and type 4 (FrCNT-4), sine of type 1 (FrSNT-1) and type 4 (FrSNT-4) number-theoretic transforms, we compute $\mathbf{{H}}^a, \mathbf{{C}}_1^a, \mathbf{{C}}_4^a, \mathbf{{S}}_1^a$ and $\mathbf{{S}}_4^a$, respectively. According to Proposition 1, these matrices have two distinct eigenvalues $\lambda \in \{1,-1\}$. In these cases, the functions $l_i(t), i=0,1$, defined in Eq. (13), are

$$\begin{aligned} l_1(t) = \frac{1+t}{2} \end{aligned}$$

and

$$\begin{aligned} l_2(t) = \frac{1-t}{2}. \end{aligned}$$

From Eq. (12), one has

$$\begin{aligned} r(t) = \left( \frac{1+t}{2}\right) + (-1)^{a} \left( \frac{1-t}{2}\right) . \end{aligned}$$

(19)

Grouping the coefficients of the powers of t and setting $\alpha _i(a)=\alpha _i(a_1,a_2)$ as the coefficient of the ith power of t, one has

$$\begin{aligned} r(t) = \alpha _0(a_1,a_2) + \alpha _1(a_1,a_2)t, \end{aligned}$$

(20)

where

$$\begin{aligned} \alpha _0(a_1,a_2)=\frac{1+(-1)^a}{2} \end{aligned}$$

and

$$\begin{aligned} \alpha _1(a_1,a_2)=\frac{1-(-1)^a}{2}. \end{aligned}$$

Finally, the fractional number-theoretic transform matrix $\mathbf{{B}}^a$ with fractional parameter $a = (a_1/a_2)$ is computed as

$$\begin{aligned} \mathbf{{B}}^{a} = \alpha _0(a_1,a_2)\mathbf{{I}} +\alpha _1(a_1,a_2)\mathbf{{B}}, \end{aligned}$$

(21)

where $\mathbf{{B}}$ can be replaced by $\mathbf{{H}}, \mathbf{{C}}_1, \mathbf{{C}}_4, \mathbf{{S}}_1$ or $\mathbf{{S}}_4$, according to the fractional transform one desires to compute.

We reinforce the fact that the computation of fractional powers of an NTT matrix by means of matrix functions does not require the construction of eigenvector sets. This makes our approach simpler than that employed in [21, 22, 33], where fractional Fourier, cosine and sine number-theoretic transforms are defined via finite field extensions of the methods given in [8, 32, 34]. In particular, the approach described in [21] involves a systematic procedure for deriving finite field Hermite–Gaussian vectors, whose components may unpredictably lie in higher-order extension fields. On the other hand, using the technique proposed in the present paper, if $\root 2a_2\, \of {-1} \in \mathrm {GI}(p)$, we assure that the components of $\mathbf{{F}}^a=\mathbf{{F}}^{\frac{a_1}{a_2}}$ lie in $\mathrm {GI}(p)$; correspondingly, for other transforms, it is sufficient that $\root a_2\, \of {-1} \in \mathrm {GI}(p)$.

3.3 Fast Algorithms

Another important property of fractional NTT defined using matrix functions is that they can be computed by means of standard fast algorithms. This is due to the fact that, according to the referred approach, the ath power of a transform matrix $\mathbf{{B}}$ is a linear combination of integer powers of $\mathbf{{B}}$. To be more specific, let us consider an N-point Fourier number-theoretic transform, for which the matrix-vector product $\mathbf{{F x}}$ can be computed by means of a fast algorithm with $M_{F}(N)$ multiplications and $A_{F}(N)$ additions. According to Eq. (18), the FrFNT with fractional parameter $a=a_1/a_2$ of an N-point vector $\mathbf{{x}}$ can be computed as

$$\begin{aligned} \mathbf{{X}}_{a,F}&=\left[ \alpha _0(a_1,a_2)\mathbf{{I}}+ \alpha _1(a_1,a_2)\mathbf{{F}}+\alpha _2(a_1,a_2) \mathbf{{F}}^2+\alpha _3(a_1,a_2)\mathbf{{F}}^3\right] \mathbf{{x}}\\&=\left[ \alpha _0(a_1,a_2)\mathbf{{I}}+\alpha _1(a_1,a_2) \mathbf{{F}}+\alpha _2(a_1,a_2)\mathbf{{P}}+ \alpha _3(a_1,a_2)\mathbf{{PF}}\right] \mathbf{{x}}\\&=\left[ \alpha _0(a_1,a_2)\mathbf{{I}}+\alpha _2(a_1,a_2) \mathbf{{P}}\right] \mathbf{{x}}+\left[ \alpha _1(a_1,a_2) \mathbf{{I}}+\alpha _3(a_1,a_2)\mathbf{{P}}\right] \mathbf{{F}}{} \mathbf{{x}}. \end{aligned}$$

By observing the last equation, we see that the FrFNT requires $M'_{F}(N) = M_{F}(N) + 2[2N-2+N\,(\mathrm {mod}\,\,2)]$ multiplications and $A'_{F}(N) = A_{F}(N) + 3N$ additions. Similarly, let us consider an N-point HNT, CNT, or SNT, for which the matrix-vector product $\mathbf{{B}}{} \mathbf{{x}}$ can be computed by means of a fast algorithm with $M_{B}(N)$ multiplications and $A_{B}(N)$ additions. According to Eq. (21), the FrHNT, the FrCNT, or the FrSNT with fractional parameter $a=a_1/a_2$ of an N-point vector $\mathbf{{x}}$ can be computed as

$$\begin{aligned} \mathbf{{X}}_{a,B}&= \left[ \alpha _0(a_1,a_2)\mathbf{{I}} +\alpha _1(a_1,a_2)\mathbf{{B}} \right] \mathbf{{x}}= \alpha _0(a_1,a_2)\mathbf{{x}} +\alpha _1(a_1,a_2)\mathbf{{B}}{} \mathbf{{x}}. \end{aligned}$$

Therefore, the computation of $\mathbf{{X}}_{a,B}$ involves $M'_{\mathbf{{B}}}(N) = M_{B}(N) + 2N$ multiplications and $A'_{B}(N) = A_{B}(N) + N$ additions.

In general, fast algorithms applicable to real-valued discrete transforms can also be used to compute number-theoretic transforms. In this sense, FNT, HNT and, consequently, FrFNT and FrHNT, can be computed by means of Cooley–Tukey, Good–Thomas prime factor, and Rader prime algorithms, for instance [5, 35]. Similarly, since the CNT and the SNT matrices have symmetries analogous to those of the corresponding real-valued transforms, standard decimation-in-time and decimation-in-frequency fast algorithms can be employed in their computation and also in the computation of the respective fractional number-theoretic transforms [9, 15].

In short, an N-point fractional NTT based on matrix functions can be computed with $\mathcal {O}(N\log N)$ additions and multiplications in the corresponding field; on the other hand, the computation of the N-point fractional NTT defined in [21, 22], for example, requires $\mathcal {O}(N^2)$ multiplications and additions. Moreover, if the transform is defined over fields whose characteristic is a Fermat or a Mersenne prime, other strategies can be employed to further decrease the computational complexity. Such strategies include the employment of residue number system and the implementation of multiplications by means of bit-shifts [5].

4 Relationship Between the FrFNT and the FrHNT

In this section, we show that the FrFNT matrix can be obtained from the FrHNT matrix and vice versa. The relationship between such two matrices is a generalization of the relationship between the FNT and the HNT matrices. For the sake of simplicity, in what follows, we assume that $p\equiv 3\,(\mathrm {mod}\,\,4)$ and $j=\sqrt{-1}$. From Definitions 3 and 4, one clearly observes that matrices $\mathbf{{F}}$ and $\mathbf{{H}}$ are related according to

$$\begin{aligned} \mathbf{{F}} = \frac{1}{2}(\mathbf{{I}}+\mathbf{{P}})\mathbf{{H}} + \frac{j}{2}(\mathbf{{I}}-\mathbf{{P}})\mathbf{{H}} \end{aligned}$$

(22)

or

$$\begin{aligned} \mathbf{{H}} = \left[ \frac{1}{2}(1-j)\mathbf{{I}} + \frac{1}{2}(1+j)\mathbf{{P}}\right] \mathbf{{F}}. \end{aligned}$$

(23)

Defining the matrix $\mathbf{{S}}$ as

$$\begin{aligned} \mathbf{{S}}:=\frac{1}{2}(1-j)\mathbf{{I}}+\frac{1}{2}(1+j)\mathbf{{P}}, \end{aligned}$$

we may write $\mathbf{{H}}=\mathbf{{S}}{} \mathbf{{F}}$ and $\mathbf{{F}}=\mathbf{{S}}^{-1}{} \mathbf{{H}}$. If N is odd, the $N\times N$ matrix $\mathbf{{S}}$ is

if N is even, the $N \times N$ matrix $\mathbf{{S}}$ has the form

Our goal is to find $\mathbf{{S}}^a$, which can be done by using matrix functions. We begin by characterizing $\mathbf{{S}}$ with respect to its eigenstructure. The proofs of the following results are given in the “Appendix.”

Lemma 1

The matrix $\mathbf{{S}}$ has, at most, four distinct eigenvalues.

Lemma 2

The $N\times N$ matrix

(24)

has determinant $\left( b^2 - c^2 \right) ^{\frac{N}{2}}$.

Lemma 3

If N is odd, the minimal polynomial of $\mathbf{{S}}$ is

$$\begin{aligned} P_\mathbf{S }(\lambda ) = (\lambda -1)\left[ (2\lambda -1+j)^2 - (1+j)^2\right] ^{\frac{N-1}{2}}. \end{aligned}$$

If N is even, the minimal polynomial of $\mathbf{{S}}$ is

$$\begin{aligned} P_\mathbf{S }(\lambda ) = (\lambda -1)^2\left[ (2\lambda -1+j)^2 - (1+j)^2\right] ^{\frac{N-2}{2}}. \end{aligned}$$

Theorem 2

The eigenvalues of the matrix $\mathbf{{S}}$ are $\{1,-j\}$. Their multiplicities are shown in Table 3.

Table 3 Multiplicities of the eigenvalues of the $N\times N$ matrix $\mathbf{{S}}$

Since the matrix $\mathbf{{S}}$ has two distinct eigenvalues, and according to Definition 8, its $l_i(t)$ functions are

$$\begin{aligned} l_1(t) = \frac{t+j}{1+j}=\frac{1-j}{2}\left( j+t\right) \end{aligned}$$

and

$$\begin{aligned} l_2(t) = \frac{t-1}{-j-1}=\frac{1-j}{2}\left( 1-t\right) , \end{aligned}$$

the Lagrange interpolating polynomial is

$$\begin{aligned} r(t) = (1)^a \frac{1-j}{2}\left( j+t\right) + (-j)^a \frac{1-j}{2}\left( 1-t\right) . \end{aligned}$$

From the definition of the matrix $\mathbf{{S}}$, the term $\frac{1-j}{2}\left( j\mathbf{{I}}+\mathbf{{S}}\right)$ is equivalent to $\frac{\mathbf{{I}}+\mathbf{{P}}}{2}$ and the term $\frac{1-j}{2}\left( \mathbf{{I}}-\mathbf{{S}}\right)$ is equivalent to $\frac{\mathbf{{I}}-\mathbf{{P}}}{2}$. Therefore, replacing t by the matrix $\mathbf{{S}}$, one obtains

$$\begin{aligned} \mathbf{{S}}^a = r(\mathbf{{S}}) = \frac{1}{2}(\mathbf{{I}}+\mathbf{{P}}) + \frac{(-j)^a}{2}(\mathbf{{I}}-\mathbf{{P}}) \end{aligned}$$

and the relationship between the FrHNT and the FrFNT, which is given by

$$\begin{aligned} \mathbf{{H}}^{a}= \left[ \frac{1}{2}(\mathbf{{I}}+\mathbf{{P}}) + \frac{(-j)^a}{2}(\mathbf{{I}}-\mathbf{{P}})\right] \mathbf{{F}}^{a}. \end{aligned}$$

(25)

5 Examples

In this section, we develop numerical examples to illustrate the construction of fractional number-theoretic transforms based on matrix functions.

5.1 FrFNT

Let us consider the element $\zeta =4\in \mathrm {GI}(257)$, where $\mathrm {ord}(4)=8$. We choose the fractional parameter $a=a_1/a_2= 3/8$ and use Definition 8 to construct an $8 \times 8$ FrFNT matrix. Initially, we obtain the $8 \times 8$ FNT matrix

$$\begin{aligned} \mathbf{{F}} = \left[ \begin{array}{cccccccc} 242 &{} 242&{} 242&{} 242&{} 242&{} 242&{} 242&{} 242\\ 242 &{} 197&{} 17&{} 68&{} 15&{} 60&{} 240&{} 189\\ 242 &{} 17&{} 15&{} 240&{} 242&{} 17&{} 15&{} 240\\ 242 &{} 68&{} 240&{} 197&{} 15&{} 189&{} 17&{} 60\\ 242 &{} 15&{} 242&{} 15&{} 242&{} 15&{} 242&{} 15\\ 242 &{} 60&{} 17&{} 189&{} 15&{} 197&{} 240&{} 68\\ 242 &{} 240&{} 15&{} 17&{} 242&{} 240&{} 15&{} 17\\ 242 &{} 189&{} 240&{} 60&{} 15&{} 68&{} 17&{} 197\\ \end{array} \right] \end{aligned}$$

using Definition 3. In order to obtain $\alpha _i(a_1,a_2), i=0,1,2,3$, we compute

$$\begin{aligned} \root 16 \of {(-1)^{3}}&\equiv \root 16 \of {(256)^{3}} \equiv 60^3 \equiv 120\, (\mathrm {mod}\, 257),\\ \cos _{\root 16 \of {-1}}(3)&= \cos _{60}(3) = 196,\\ \sin _{\root 16 \of {-1}}(3)&= \sin _{60}(3)= 188. \end{aligned}$$

Using these results, one obtains $\alpha _0(3,8) = 36, \alpha _1(3,8)= 28, \alpha _2(3,8)= 97, \alpha _3(3,8) = 97$ and, therefore,

$$\begin{aligned} \mathbf{{F}}^{\frac{3}{8}}&= 36\mathbf{{F}}^{0} + 28\mathbf{{F}}^{1} + 97\mathbf{{F}}^{2} + 97\mathbf{{F}}^{3}=\left[ \begin{array}{cccccccc} 57&{} 181&{} 181&{} 181&{} 181&{} 181&{} 181&{} 181\\ 181&{} 241&{} 112&{} 14&{} 76&{} 52&{} 145&{} 83\\ 181&{} 112&{} 112&{} 145&{} 181&{} 112&{} 173&{} 145\\ 181&{} 14&{} 145&{} 241&{} 76&{} 83&{} 112&{} 52\\ 181&{} 76&{} 181&{} 76&{} 57&{} 76&{} 181&{} 76\\ 181&{} 52&{} 112&{} 83&{} 76&{} 241&{} 145&{} 14\\ 181&{} 145&{} 173&{} 112&{} 181&{} 145&{} 112&{} 112\\ 181&{} 83&{} 145&{} 52&{} 76&{} 14&{} 112&{} 241 \end{array} \right] . \end{aligned}$$

5.2 FrHNT

In this example, we consider the same parameters of Example 5.1 and construct the $8 \times 8$ FrHNT matrix using Eq. (20). From Definition 4, the $8 \times 8$ HNT matrix shown in Eq. (26) is constructed. In order to obtain $\alpha _i(a_1,a_2), i=0,1$, we compute $\root 8 \of {-1} \equiv 2 \,(\mathrm {mod}\, 257), \alpha _0(3,8) = 133$ and $\alpha _1(3,8)= 125$. The matrix $\mathbf{{H}}^{3/8} = 133\mathbf{{H}}^{0} + 125\mathbf{{H}}^{1}$, shown in Eq. (27), is obtained.

$$\begin{aligned} \mathbf{{H}} = \left[ \begin{array}{cccccccc} 1&{} 1&{} 1&{} 1&{} 1&{} 1&{} 1&{} 1\\ 1&{} 227+223j&{} 241j&{} 30+223j&{} 255&{} 228&{} 130&{} 103\\ 1&{} 241j&{} 255&{} 16j&{} 103&{} 1&{} 29&{} 178\\ 1&{} 30+223j&{} 16j&{} 227+223j&{} 67&{} 255&{} 130&{} 103\\ 1&{} 255&{} 1&{} 255&{} 1&{} 1&{} 1&{} 1\\ 1&{} 30+223j&{} 241j&{} 227+34j&{} 67&{} 255&{} 130&{} 103\\ 1&{} 16j&{} 255&{} 241j&{} 103&{} 1&{} 29&{} 178\\ 1&{} 227+223j&{} 16j&{} 30+34j&{} 67&{} 255&{} 130&{} 103\\ \end{array} \right] \end{aligned}$$

(26)

$$\begin{aligned} \small \mathbf{{H}}^{\frac{3}{8}} = \left[ \begin{array}{cccccccc} 1&{} 125&{} 125&{} 125&{} 125&{} 125&{} 125&{} 125\\ 125&{} 238+118j&{} 56j&{} 152+119j&{} 132&{} 152+138j&{} 201j&{} 105+138j\\ 125&{} 56j&{} 8&{} 201j&{} 125&{} 56j&{} 132&{} 201j\\ 125&{} 152+119j&{} 201j&{} 238+119j&{} 132&{} 105+138j&{} 56j&{} 152+138j\\ 125&{} 132&{} 125&{} 132&{} 1&{} 132&{} 125&{} 132\\ 125&{} 152+138j&{} 56j&{} 105+138j&{} 132&{} 238+119j&{} 201j&{} 152+119j\\ 125&{} 201j&{} 132&{} 56j&{} 125&{} 201j&{} 8&{} 56j\\ 125&{} 105+138j&{} 201j&{} 152+138j&{} 132&{} 152+119j&{} 56j&{} 238+119j\\ \end{array} \right] \end{aligned}$$

(27)

5.3 FrCNT

In order to obtain the $8 \times 8$ FrCNT of type 4 matrix over $\mathrm {GI}(257)$, an element $\zeta$ whose multiplicative order is $\mathrm {ord}(\zeta )=2N=16$ has to be chosen. We then select the element $\zeta =2\in \mathrm {GI}(257)$, which has the mentioned order, and use again the fractional parameter $a=a_1/a_2= 3/8$. From Eq. (6), the $8 \times 8$ CNT-4 matrix

$$\begin{aligned} \mathbf{{C}}_4= \left[ \begin{array}{cccccccc} 29&{} 11&{} 190&{} 127&{} 189&{} 178&{} 154&{} 61\\ 11&{} 189&{} 61&{} 79&{} 67&{} 228&{} 130&{} 103\\ 190&{} 61&{} 130&{} 246&{} 103&{} 189&{} 29&{} 178\\ 127&{} 79&{} 246&{} 61&{} 29&{} 154&{} 67&{} 68\\ 189&{} 67&{} 103&{} 29&{} 196&{} 246&{} 178&{} 127\\ 178&{} 228&{} 189&{} 154&{} 246&{} 127&{} 61&{} 67\\ 154&{} 130&{} 29&{} 67&{} 178&{} 61&{} 68&{} 11\\ 61&{} 103&{} 178&{} 68&{} 127&{} 67&{} 11&{} 228\\ \end{array} \right] \end{aligned}$$

is constructed. We use Eq. (20) with $\alpha _0(3,8) = 133$ and $\alpha _1(3,8)= 125$ (the same values employed in the construction of the FrHNT matrix in Example 5.2). Thus, one has

$$\begin{aligned} \mathbf{{C}}_4^{\frac{3}{8}}&= 133\mathbf{{C}}_4^{0} + 125\mathbf{{C}}_4^{1}= \left[ \begin{array}{cccccccc} 160&{}90&{} 106&{} 198&{} 238&{} 148&{} 232&{} 172\\ 90&{} 114&{} 172&{} 109&{} 151&{} 230&{}59&{}25\\ 106&{} 172&{} 192&{} 167&{}25&{} 238&{}27&{} 148\\ 198&{} 109&{} 167&{}48&{}27&{} 232&{} 151&{}19\\ 238&{} 151&{}25&{}27&{} 218&{} 167&{} 148&{} 198\\ 148&{} 230&{} 238&{} 232&{} 167&{}74&{} 172&{} 151\\ 232&{}59&{}27&{} 151&{} 148&{} 172&{} 152&{}90\\ 172&{}25&{} 148&{}19&{} 198&{} 151&{}90&{} 106\\ \end{array} \right] . \end{aligned}$$

The FrCNT of type 1 and FrSNT of types 1 and 4 are constructed in a similar manner.

6 An Image Encryption Scheme Based on Fractional NTT

In this section, we revisit the image encryption scheme proposed in [19]. More specifically, we verify that, after changing the FrFNT based on the approach given in [21] by the FrFNT constructed using the matrix functions approach, the robustness of the referred scheme against the main cryptographic attacks is not affected. Moreover, we show that the FrFNT we use to encrypt a grayscale image encoded with 8 bpp does not require a pixel juxtaposition strategy performed in [19]. In addition to the computational advantages described in Sect. 3.3, this makes the current proposal more efficient and straight.

6.1 Encryption Scheme

The encryption procedure consists in taking $N\times N$ image blocks from left to right and from top to bottom, in the manner shown in Fig. 1. A two-dimensional version of an FrFNT is applied to the current image block and the resulting block replaces the corresponding original block before the next block is processed. In order to provide diffusion to the scheme, a number of columns and rows is shared among adjacent blocks. To be more specific, in Fig. 1, the first $o_v$ columns of block $\mathbf{{b}}_1$ (before its encryption) correspond to the last $o_v$ columns of the encrypted version of $\mathbf{{b}}_0$; $\mathbf{{b}}_1$ is then encrypted, and the first $o_v$ columns of block $\mathbf{{b}}_2$ (before its encryption) correspond to the last $o_v$ columns of the encrypted version of $\mathbf{{b}}_1$; $\mathbf{{b}}_2$ is then encrypted and so on. A similar overlapping strategy is also performed in the rows. An image block may have to be assembled from two sub-blocks; this is the case of $\mathbf{{b}}_3=[\mathbf{{b}}_3^{(1)} | \mathbf{{b}}_3^{(2)}]$ in Fig. 1.

Fig. 1

Block selection and overlapping in the image encryption scheme. The image has dimensions $R \times C$, and blocks with dimensions $N \times N$ are selected. Darker gray regions correspond to regions where adjacent blocks overlap

The fractional parameter used in the computation of the FrFNT of each image block is obtained from a secret-key. Actually, an integer $a_2$ is chosen and kept fixed. The secret-key is the K-length vector of integers

$$\begin{aligned} \mathbf{{k}}=\{a_{1,0},a_{1,1},a_{1,2},\ldots ,a_{1,K-2},a_{1,K-1}\} \end{aligned}$$

and the ith image block is transformed by the matrix

$$\begin{aligned} \mathbf{{F}}^{\frac{a_{1,i\,(\mathrm {mod}\,\,K)}}{a_2}}. \end{aligned}$$

In the computation of the fractional power of $\mathbf{{F}}$, the index i of the component of $\mathbf{{k}}$ is taken modulo K because the number of blocks to be processed is usually greater than the key length. In other words, the key components are used in a cyclic manner. The encryption is finished after the whole image is covered by two rounds of the block-by-block transformation procedure we have explained. The decryption consists in applying, in the reverse order, the same steps performed in the encryption.

Specific parameters for an image encryption scheme following the described approach can be chosen in accordance with the type of images to be processed. Throughout this paper, we consider grayscale images encoded with 8 bpp. Since the pixels values range from 0 to 255, an FrFNT defined over $\mathrm {GI}(257)$ can be used to encrypt such images. We then consider the FNT used to construct the FrFNT in Example 5.1 and use it to construct FrFNT with different fractional parameters. In this case, image blocks with dimension $8\times 8$ are processed.

We remark that, using the method proposed in [21], an $8\times 8$ FrFNT matrix over $\mathrm {GI}(257)$ would have its entries lying in higher extension fields. Since this would require a more sophisticated arithmetic, in [19], the authors defined a $4\times 4$ FrFNT matrix over $\mathrm {GI}(65537)$ and applied it to blocks where each entry is a Gaussian integer whose “real” and “imaginary” parts are 16-bit numbers obtained from the juxtaposition of two 8-bit numbers (pixels of an $8\times 8$ image block). Using the matrix functions approach, as shown in Example 5.1, $8\times 8$ FrFNT matrices whose elements lie in $\mathrm {GF}(257)$ can be obtained and any pixel manipulation is unnecessary.

6.2 Computer Experiments and Security Aspects

In order to carry out computer simulations of the proposed scheme, we consider the FrNTT over $\mathrm {GI}(257)$ mentioned at the end of Sect. 6.1, and set $a_2=64$ and $o_v=2$ (number of columns and rows overlapping). The secret-key

$$\begin{aligned} \mathbf{{k}}=[&53, 58, 9, 59, 41, 7, 18, 36, 62, 62, 11, 63, 62, 32, 52, 10, 27, 59, 51, 62, 42,\\&3, 55,60, 44, 49, 48, 26, 42, 11, 46, 3, 18, 3, 7, 53, 45, 21, 61, 3] \end{aligned}$$

was randomly generated and the $512\times 512$ image lena.bmp shown in Fig. 2a was encrypted.

In the encryption procedure, an additional strategy is employed, with the purpose of avoiding the appearance of encrypted image blocks with pixels whose value is 256; the representation of such pixels would require a 9-bit encoding. The strategy consists in applying to the ith image block the FrNTT with fractional parameter $\frac{a_{1,i\,(\mathrm {mod}\,\,40)}}{64}$ in a recursive manner. More precisely, the FrNTT is applied to the image block and, if the result contains a pixel of value 256, the FrNTT is applied again. The recursive FrNTT application stops when a transformed image block whose maximum pixel value is less than 256 is obtained, which allows maintaining an 8 bpp encoding.

In Fig. 2b, we observe that the visual aspect of the encrypted image is completely noisy. In contrast to the histogram of the original image (Fig. 2c), the histogram of the encrypted image appears to be uniform (Fig. 2d). Additionally, the correlation coefficients obtained from pairs of horizontally adjacent pixels in the original and the encrypted images are, respectively, 0.9853 and 0.0001 [40]; the entropy of the encrypted image is 7.9992. This suggests that statistical and entropy attacks against the proposed scheme would not be effective.

Fig. 2

Image encryption by means of FrNTT. a Original image lena.bmp; c encrypted version of lena.bmp; b histogram of original image and d histogram of encrypted image

The secret-key used in our scheme is a vector with 40 integer numbers in the range 1–64. Since each such integer is encoded as a 6-bit string, the key length is 240 bits. This satisfies the general requirement for resisting brute-force attack [38]. Naturally, since the working premises of the scheme do not depend on the key length, the key space size can be easily increased according to the desired security level.

The resistance of the method to differential attack can be measured by the number of pixels change rate (NPCR) and the unified average changing intensity (UACI), whose ideal values are, respectively, $100\%$ and $33.\overline{3}\%$ [1]. In order to obtain such metrics, we change the least significant bit of a randomly chosen pixel in the original image lena.bmp. The modified image is then encrypted and compared with the encrypted version of the original image. After performing this experiment 100 times, the average NPCR and UACI were, respectively, 99.6083 and $33.4765\%$. The same procedure was performed for lena.bmp with other resolutions. The results were, respectively, 99.6155 and $33.4300\,\%$ for an $128\times 128$ image, 99.6307 and $33.4425\,\%$ for a $256\times 256$ image, and 99.6065 and $33.4565\,\%$ for an $1024\times 1024$ image. This indicates that the scheme is also robust against differential attack.

We can also perform a preliminary analysis regarding the computational complexity of the proposed encryption scheme. Since the method basically involves transform computations, we characterize its complexity by means of the total number of arithmetic operations needed to apply such transforms. Considering the overlapping of two columns and two rows in the processing of each $8\times 8$ image block, we estimate the number of FrNTT necessary to cover the whole $R\times C$ image twice as

$$\begin{aligned} T_{N=8,\mathrm {GF}(257)} = 2\times \frac{R}{6}\times \frac{C}{6}. \end{aligned}$$

Using the definition proposed in this paper, the computation of an N-point FrNTT requires $\mathcal {O}(N\log N)$ arithmetic operations (see Sect. 3.3). Therefore, assuming that an $N\times N$ two-dimensional FrNTT corresponds to an N-point FrNTT calculated 2N times, we estimate the total complexity of our method by

$$\begin{aligned} 16\times 8\log 8\times T_{N=8,\mathrm {GF}(257)} = \frac{512}{24}\times R\times C. \end{aligned}$$

(28)

The complexity of our method can be compared with that of the method proposed in [19], which employs 4-point FrNTT over $\mathrm {GI}(65537)$, defined according to [21].² In this case, the number of FrNTT necessary to cover the whole $R\times C$ image twice is estimated as

$$\begin{aligned} T_{N=4,\mathrm {GI}(65537)}=2\times \frac{R}{8}\times \frac{C}{7}. \end{aligned}$$

The computation of an N-point FrNTT defined according to [21] requires $\mathcal {O}(N^2)$ arithmetic operations. Since these operations have to be carried out over $\mathrm {GI}(65537)$, it is reasonable to consider that their cost is at least 16 times the cost of an operation carried out over $\mathrm {GF}(257)$. Thus, we estimate the total complexity of the method given in [19] by

$$\begin{aligned} 8\times 4^2\times 4^2\times T_{N=4,\mathrm {GI}(65537)}=\frac{512}{7}\times R\times C. \end{aligned}$$

(29)

Comparing Eqs. (28) and (29), one concludes that the computational complexity of the proposed scheme is about 3.4 times less than that of the method given in [19].

Finally, it is important to remark that the image encryption scheme analyzed in this section is very flexible. Instead of using the FrNTT, other fractional NTT could be employed. The parameters of the scheme can also be adjusted. This includes the dimension of the transform matrix, which must coincide with the dimension of the image blocks one desires to process, the field in which the transform is defined, the number of columns and rows shared by adjacent image blocks, the key length, the number of encryption rounds, etc. Such a flexibility allows designing schemes with distinct robustness levels and whose implementations require different computational efforts.

7 Concluding Remarks

A new approach for defining fractional number-theoretic transforms was presented in this paper. The method is based on matrix functions and, differently from previously proposed definitions, it does not require the construction of NTT eigenvectors. This allows us to express fractional powers of an NTT matrix as a linear combination of its integer powers. As we have demonstrated, this also enables the use of standard fast algorithms in the computation of FrNTT matrix-vector products. Our approach was developed for Fourier, Hartley, cosine and sine number-theoretic transforms, and some peculiarities of these transforms were discussed.

Besides addressing theoretic aspects, we revisited a recently proposed image encryption scheme based on the FrFNT. We have shown how the FrFNT constructed by means of matrix functions can be employed in such an application and emphasized the advantages that it provides. After carrying out computer experiments and performing a preliminary security analysis, we have concluded that the scheme remains resistant against the main cryptographic attacks.

Currently, we are investigating further theoretic and practical aspects concerning fractional number-theoretic transforms. The possibility of defining FrNTT based on closed-form Hermite–Gaussian eigenvectors over finite fields [16] and the characterization, in the number-theoretic scenario, of fractional convolution and other important properties [41] have been studied. Applications of FrNTT in the fields of error-correcting codes, cryptography, digital watermarking, and multiuser communication have also been investigated [10, 13, 23, 24, 36].

Appendix

1.1 Proof of Lemma 1

Since the integer powers of $\mathbf{{S}}$ are

$$\begin{aligned} \mathbf{{S}}^2= & {} \left[ \frac{1}{2}(1-j)\mathbf{{I}}+\frac{1}{2}(1+j)\mathbf{{P}}\right] ^2 = \mathbf{{P}},\\ \mathbf{{S}}^3= & {} \mathbf{{P}}{} \mathbf{{S}} \end{aligned}$$

and

$$\begin{aligned} \mathbf{{S}}^4 =\mathbf{{PS}}^2 = \mathbf{{I}}, \end{aligned}$$

the matrix $\mathbf{{S}}$ has period 4 and, therefore, the lemma holds.

1.2 Proof of Lemma 2

Permuting the second and the last rows of $\mathbf{{B}}$, the updated first and second rows have zero entries at the same positions. Applying analogous permutations to other rows of $\mathbf{{B}}$, after an even number of permutations, one obtains the matrix

$$\begin{aligned} \mathbf{{B}}_p = \left[ \begin{array}{cccccccc} b&{} 0&{}\ldots &{} 0&{} 0&{}\ldots &{} 0&{}c\\ c&{} 0&{}\ldots &{} 0&{} 0&{}\ldots &{} 0&{}b\\ 0&{} b&{}\ldots &{} 0&{} 0&{}\ldots &{} c&{}0\\ 0&{} c&{}\ldots &{} 0&{} 0&{}\ldots &{} b&{}0\\ \vdots &{}\vdots &{}\vdots &{}\vdots &{}\vdots &{}\vdots &{}\vdots &{}0\\ 0&{} 0&{}\ldots &{} b&{} c&{}\ldots &{} 0&{}0\\ 0&{} 0&{}\ldots &{} c&{} b&{}\ldots &{} 0&{}0\\ \end{array} \right] , \end{aligned}$$

(30)

such that $|\mathbf{{B}}_p| = |\mathbf{{B}}|$. This determinant can be expressed as $|\mathbf{{B}}| = \left( b^2 -c^2 \right) |\mathbf{{B}}_{s}|$, where $\mathbf{{B}}_{s}$ is the matrix obtained excluding the first two rows and the first and the last columns of $\mathbf{{B}}_p$. We can also write $|\mathbf B | = \left( b^2 -c^2 \right) ^2|\mathbf B _{s-1}|$, where $\mathbf{{B}}_{s-1}$ is a matrix obtained excluding the first two rows and the first and the last columns of $\mathbf{{B}}_{s}$. In general, we observe that $|\mathbf{{B}}|=\left( b^2-c^2\right) ^{s_0}|\mathbf{{B}}_{s-s_0+1}|, s_0=1,\ldots ,\frac{N}{2}$, where $\mathbf{{B}}_{s-s_0+1}$ is a matrix obtained excluding the first two rows and the first and the last columns of $\mathbf{{B}}_{s-s_0+2}$. This leads us to $|\mathbf{{B}}| = \left( b^2 -c^2 \right) ^{\frac{N}{2}}$.

1.3 Proof of Lemma 3

The minimal polynomial of $\mathbf{{S}}$ is given by $\left| \lambda \mathbf I _{N} - \mathbf{{S}}\right|$. Defining $b'= \lambda -1, b = \lambda - \frac{1-j}{2}$ and $c = \frac{1+j}{2}$, after permuting the rows in a way similar to that used in the proof of Lemma 2, the matrix $\lambda \mathbf I _{N} - \mathbf{{S}}$ has a structure similar to that of $\mathbf{{B}}_p$. If N is odd, the minimal polynomial of $\mathbf{{S}}$ is given by

$$\begin{aligned} P_{\mathbf{{S}}}(\lambda ) = \left| \begin{array}{ccccccc} b' &{}0 &{} \ldots &{} 0&{}0&{} \ldots &{} 0\\ 0 &{}b &{} \ldots &{} 0&{}0&{} \ldots &{} c\\ 0 &{}c &{} \ldots &{} 0&{}0&{} \ldots &{} b\\ \vdots &{}\vdots &{} \vdots &{} \vdots &{}\vdots &{} \vdots &{} \vdots \\ 0 &{}0 &{} \ldots &{} b&{}c&{} \ldots &{} 0\\ 0 &{}0 &{} \ldots &{} c&{}b&{} \ldots &{} 0\\ \end{array} \right| . \end{aligned}$$

(31)

Therefore,

$$\begin{aligned} P_{\mathbf{{S}}}(\lambda )&= b'\left( b^2 - c^2\right) ^{\frac{N-1}{2}}= (\lambda -1)\left[ (2\lambda -1+j)^2 - (1+j)^2\right] ^{\frac{N-1}{2}}. \end{aligned}$$

If N is even, the minimal polynomial of $\mathbf{{S}}$ is given by

$$\begin{aligned} P_{\mathbf{{S}}}(\lambda ) = \left| \begin{array}{cccccccc} b' &{} 0&{}\ldots &{} 0&{} 0&{} 0&{}\ldots &{} 0\\ 0 &{} 0&{}\ldots &{} 0&{} b'&{} 0&{}\ldots &{} 0\\ 0 &{} b&{}\ldots &{} 0&{} 0&{} 0&{}\ldots &{} c\\ 0 &{} c&{}\ldots &{} 0&{} 0&{} 0&{}\ldots &{} b\\ \vdots &{}\vdots &{}\vdots &{}\vdots &{}\vdots &{}\vdots &{}\vdots &{} 0\\ 0 &{} 0&{}\ldots &{} b&{} 0&{} c&{}\ldots &{} 0\\ 0 &{} 0&{}\ldots &{} c&{} 0&{} b&{}\ldots &{} 0\\ \end{array} \right| . \end{aligned}$$

(32)

Therefore,

$$\begin{aligned} P_{\mathbf{{S}}}(\lambda )&= (b')^2\left( b^2 - c^2\right) ^{\frac{N-2}{2}}= (\lambda -1)^2\left[ (2\lambda -1+j)^2 - (1+j)^2\right] ^{\frac{N-2}{2}}. \end{aligned}$$

1.4 Proof of Theorem 2

If N is odd, the eigenvalues of $\mathbf{{S}}$ are the roots of the polynomial

$$\begin{aligned} P_{\mathbf{{S}}}(\lambda ) =(\lambda -1)\left[ (2\lambda -1+j)^2 - (1+j)^2\right] ^{\frac{N-1}{2}}. \end{aligned}$$

From $(2\lambda -1+j)^2 - (1+j)^2 = 0$, the roots are $\{1,-j\}$, both with multiplicity $\frac{N-1}{2}$. The root $\lambda = 1$ also occurs due to the term $(\lambda -1)$. If N is even, the eigenvalues are the roots of the polynomial

$$\begin{aligned} P_{\mathbf{{S}}}(\lambda ) =(\lambda -1)^2\left[ (2\lambda -1+j)^2 - (1+j)^2\right] ^{\frac{N-2}{2}}. \end{aligned}$$

From $(2\lambda -1+j)^2 - (1+j)^2 = 0$, the roots are $\{1,-j\}$, both with multiplicity $\frac{N-2}{2}$. The root $\lambda = 1$ occurs twice more, due to the term $(\lambda -1)^2$.