New sequences from the generalized Pell $p-$numbers and mersenne numbers and their application in cryptography

1.   Introduction

The Fibonacci sequence $\lbrace F_n \rbrace$ is defined as

with initial conditions $F_0 = 0$ and $F_1 = 1$. This sequence and its generalizations (e.g. $k$-Fibonacci sequences and $k$-Pell sequences), have been investigated extensively and there are applications in many diverse fields ^[1,2,3].

The Pell sequence $\lbrace P_n\rbrace$ is defined as

with initial conditions $P_0 = 0$ and $P_1 = 1$. This sequence and its generalizations have also been studied extensively ^[4,5,6,7]. The Pell $p-$numbers are defined as follows.

Definition 1.1 (^[8]). For an integer $p$, the Pell $p-$numbers, denoted by $\lbrace P(n, p)\rbrace$, are

where $P(0) = P(1) = P(2) = \dots = P(p) = 0$, $P(p) = 1$ and $P(p+1) = 0$.

Example 1.1. (i) The Pell $p-$numbers for $p = 2$ are given by

so the sequence is $\lbrace P(n, 2)\rbrace _{0}^\infty = \lbrace 0, 1, 0, 0, 1, 2, 4, 9, 20, \dots \rbrace$.

(ii) The Pell $p-$numbers for $p = 3$ are given by

so, the sequence is $\lbrace P(n, 3)\rbrace _{0}^\infty = \lbrace 0, 0, 1, 0, 0, 0, 1, 2, 4, 8, 17, 36, 76,160, \dots \rbrace$.

The generalized order $k$-Pell sequences were defined in ^[9] as the semi-direct product of finite cyclic groups. In ^[10], the quaternion-Pell sequence was introduced and extended to finite cyclic groups. The generalized order $k$-Pell sequences for special groups of nilpotency class 2 were given in ^[11]. Two new identities involving generalized Fibonacci and generalized Lucas numbers were introduced in ^[12]. In ^[13], a Horadam-type of generalization was provided which involves the generalized Fibonacci, generalized Lucas, Fibonacci, Lucas, Pell, Pell-Lucas, Fermat, Fermat-Lucas, Jacobsthal, Jacobsthal-Lucas, balancing, and co-balancing numbers. Expressions connecting two generalized classes of Fibonacci and Lucas polynomials were given in ^[14]. A class of polynomials known as convolved Pell polynomials was investigated in ^[15].

Another important sequence is the Mersenne numbers. The $n$th Mersenne number has the form $M_n = 2^n-1$ where $n$ is a nonnegative integer. A generalization of these numbers is as follows:

Definition 1.2 (^[16]). For $k \geq 3$ an integer, the generalized Mersenne numbers, denoted by $\lbrace M(k, n)\rbrace _{0}^\infty$, are

with initial conditions $M(k, 0) = 0$ and $M(k, 1) = 1$.

For $k = 3$, we have

which gives the sequence $\lbrace M(3, n)\rbrace _{0}^\infty = \lbrace 0, 1, 3, 7, \cdots\rbrace$. The Mersenne numbers and their generalizations and properties have been studied extensively ^{[17,18,19,20,21]}. The characteristic polynomials of the Pell $p-$numbers and generalized Mersenne numbers are $x^{p+1}-2x^p-1$ and $x^2-kx+k-1$, respectively.

The Hadamard-type product of polynomials $f$ and $g$ is defined as follows:

Definition 1.3 (^[22]). The Hadamard-type product of polynomials $f$ and $g$ is $f\ast g = \sum_{i = 0}^\infty(a_i\ast b_i)x^i$ where

and $f(x) = a_mx^m+\dots+a_1x+a_0$ and $g(x) = b_nx^n+b_{n-1}x^{n-1}+\dots+b_1x+b_0$.

Diffie-Hellman key exchange is one of the earliest and most widely used public-key cryptographic primitives ^[24,25,26]. It allows two parties who have never met to exchange a secret key over an open channel. In ^[27], the Diffie-Hellman key exchange protocol was studied using matrices over noncommutative rings. A universal algebraic generalization of the Diffie-Hellman scheme was proposed in ^[28].

Motivated by the above results and the practical importance of Diffie-Hellman key exchange, we first generalize the Pell numbers and study their combinatorial representations. Then the characteristic polynomials of the Pell $p-$numbers and generalized Mersenne numbers are used to obtain new sequences. As an application, these sequences are employed to obtain a new Diffie-Hellman key exchange. This is the first algorithm that uses sequences and matrices to obtain a key.

The remainder of this paper is organized as follows: Section 2 presents the Pell $(p, t)-$numbers and their combinatorial representation and matrices are given. In Section 3, the Hadamard-type product of Pell $p-$number polynomials and generalized Mersenne numbers are considered. Section 4 provides a Diffie-Hellman key exchange using the Pell $(p, t)-$numbers and the Hadamard-type Pell-Mersenne $p-$numbers. Finally, some concluding remarks are given in Section 5.

2.   The Pell $(p, t)-$numbers

In this section, we define the Pell $(p, t)-$numbers and obtain new sequences. Then their structure is investigated. The Pell $(p, t)-$numbers, $p$ an integer, are defined as follows.

Definition 2.1. For integers $p$ and $t$, the Pell $(p, t)-$numbers, denoted by $\lbrace P_n(p, t)\rbrace$, are

where $P_0(p, t) = P_1(p, t) = \dots = P_{p+t-1}(p, t) = 0$, $P_{p+t}(p, t) = 1$.

Example 2.1. (i) The Pell $(p, t)-$numbers for $p = 2$ and $t = 1$ are given by

so the sequence is $\lbrace P_n(2, 1)\rbrace _{0}^\infty = \lbrace 0, 0, 0, 1, 2, 4, 9, 21, 48,109,248,565, \dots \rbrace$.

(ii) The Pell $(p, t)-$numbers for $p = 3$ and $t = 1$ are given by

so the sequence is $\lbrace P_n(3, 1)\rbrace _{0}^\infty = \lbrace 0, 0, 0, 1, 2, 4, 8, 17, 37, 80,172, \dots \rbrace$.

Lemma 2.1. Let $u(x)$ be the generating function of the Pell $(p, t)-$numbers. Then

Proof. We have

□

Theorem 2.1. The Pell $(p, t)-$numbers $\lbrace P_n(p, t)\rbrace$ have the following exponential representation

Proof. Using (2.2), we have

Since

the result follows. □

Let $t = 1$. Then the recurrence relation (2.1) gives

Lemma 2.2. For $p = 2$, $t = 1$, and $n\geq 4$, we have

where

Proof. By induction on $n$. For $p = 2$, $t = 1$, and $n = 4$, we have

Now, assume that the statement holds for $n = s$. Then for $n = s+1$

which completes the proof. □

Let $M_p(1) = [m_{i, j}]_{(p+2)\times(p+2)}$ be the companion matrix for the Pell $(p, 1)-$numbers. It can be readily established by mathematical induction on $n$ that for $p\geq 3$ and $n\geq p+2$

Theorem 2.2. For $u \in \mathbb{N}$, $p\geq 2$ and $n\geq p+2$, we have

(i) $(M_p(1))^n(M_p(1))^u = (M_p(1))^{n+u}$.

(ii) $(M_p(1))^n(M_p(1))^u = (M_p(1))^u(M_p(1))^n$.

Proof. By induction on $u$. For $u = 1$ we have

Now suppose it is true for $u = s$. Then for $u = s+1$

which completes the proof of (ⅰ). For (ⅱ), using (ⅰ) we have

□ For $n < 0$, the Pell $(p, t)-$numbers are defined as

For $n < 0$, the companion matrix of the Pell $(p, 1)-$numbers are defined as follows. For $n = -1$ we have

and by induction on $n$, we obtain

Theorem 2.3. For $u \in \mathbb{N}$, $p\geq 2$, and $n\geq p+2$, we have

(i) $(M_p(1))_{-n}(M_p(1))_{-u} = (M_p(1))_{-(n+u)}$.

(ii) $(M_p(1))_{-n}(M_p(1))_{-u} = (M_p(1))_{-u}(M_p(1))_{-n}$.

Proof. The proof is similar to that of Theorem 2.2 and so is omitted. □

3.   The Hadamard-type Pell-Mersenne $p-$numbers

In this section, new sequences are obtained using the Hadamard-type product of the Pell $p-$numbers and Mersenne numbers. Then, some results on their structure are obtained. First, we give the new Hadamard-type Pell-Mersenne $p-$sequences.

Definition 3.1. For integers $k\geq 3$ and $p\geq 3$, the Hadamard-type Pell-Mersenne $p-$sequences, denoted by $\lbrace MP_{n}(k, p)\rbrace _{0}^\infty$, are

with initial conditions $MP_{0}(k, p) = MP_{1}(k, p) = \dots = MP_{p-1}(k, p) = 0$ and $MP_{p}(k, p) = 1$.

For example, the Hadamard-type Pell-Mersenne $p-$sequence for $p = 3$ and $k = 3$ is given by

so $\lbrace MP_{n}(3, 3)\rbrace _{0}^\infty = \lbrace 0, 0, 0, 1, 2, 3, 7, 19, 44, 96, \cdots \rbrace$, and for $p = 4$ and $k = 3$ is given by

so $\lbrace MP_{n}(4, 3)\rbrace _{0}^\infty = \lbrace 0, 0, 0, 0, 1, 2, 3, 8, 24, 58,133, \dots \rbrace$.

From the recurrence relation (3.1), we have

The Hadamard-type Pell-Mersenne $p-$numbers have the following companion matrix

and is called the Hadamard-type Pell-Mersenne $p-$matrix.

Theorem 3.1. For $p = 3, k = 3$, and $n\geq 4$, we have

where

Proof. By induction on $n$. For $n = 4$ we have

so the statement is true. Now, assume that the statement holds for $n = t$. Then, for $n = t + 1$ we have

which completes the proof. □

Corollary 3.1. For $p = 3, k\geq4$, and $n\geq 4$, we have

where

Using induction on $p\geq 4$ and $n\geq p+1$ gives

Lemma 3.1. Let $y(x)$ be the Hadamard-type Pell-Mersenne $p-$numbers. Then

Proof. We have

□

Theorem 3.2. The Hadamard-type Pell-Mersenne $p-$numbers sequences $\lbrace MP_n(k, p)\rbrace$ have the following exponential representation

Proof. Using (3.2), we have

Since

the result follows. □

4.   Diffie-Hellman Key Exchange Using the Pell $(p, 1)-$numbers and the Hadamard-type Pell-Mersenne $p-$numbers

In this section, we present a new Diffie-Hellman key exchange using the Pell $(p, t)-$numbers and Hadamard-type Pell-Mersenne $p-$numbers matrices. Then, a security analysis is given. Two algorithms are given below.

Algorithm 1. Alice and Bob want to establish a secret key. They select a Pell $(p, t)-$numbers matrix and $q$ a prime number over an insecure channel. Alice chooses a random number $a\geq 4$ and sends $M_p(1)^a \ (\mathrm{mod}\ q)$ to Bob. Bob chooses a random number $b\geq 4$ and sends $M_p(1)^b \ (\mathrm{mod}\ q)$ to Alice. Alice and Bob both compute $M_p(1)^{ab} \ (\mathrm{mod}\ q)$ and use this as their private key. The algorithm steps are given below and illustrated in Figure 1.

Step 1. The prime number $q$ and generator $M_p(1)$ are public (assume all users have agreed on the general linear group over a finite field $F_q$ and $M_p(1)$ as the Pell $(p, 1)-$matrix).

Step 2. Alice chooses a random number $a\geq 4$ and sends $M_p(1)^a \ (\mathrm{mod}\ q)$ to Bob.

Step 3. Bob chooses a random number $b\geq 4$ and sends $M_p(1)^b \ (\mathrm{mod}\ q)$ to Alice.

Step 4. Alice and Bob both compute $M_p(1)^{ab} \ (\mathrm{mod}\ q)$ and use this as the private key for future communications.

Example 4.1. Let $(M_2(1), 13)$ be the public key. Alice chooses $a = 4$ and using Lemma 2.2 computes $M_2(1)^4 \ (\mathrm{mod}\ {13})$

and sends this to Bob. Bob chooses $b = 7$ and obtains $M_2(1)^7 \ (\mathrm{mod}\ {13})$

and sends this to Alice. From Theorem 2.2, we have $M_2(1)^{4}M_2(1)^{7} = M_2(1)^{7}M_2(1)^{4}$, so Alice and Bob both compute

This is used as the private key for future communications.

Algorithm 2. This algorithm is the same as Algorithm 1 but in Step 1 $N_p(k)$ is used.

Example 4.2. Let $(N_3(3), 11)$ be the public key. Alice chooses $a = 5$ and using Lemma 2.2 computes $N_3(3)^5 \ (\mathrm{mod}\ {11})$

and sends this to Bob. Bob chooses $b = 6$ and obtains $N_3(3)^6 \ (\mathrm{mod}\ {11})$

and sends this to Alice. From Theorem 2.2, we have $N_3(3)^{5}N_3(3)^{6} = N_3(3)^{6}N_3(3)^{5}$, so Alice and Bob both compute

This is used as the private key for future communications.

One way for an adversary to obtain the key is to generate all possible matrices. Since $q$ can be a very large prime number, it is intractable to check all $q^{m^2}$ matrices where $m$ is the matrix size. Because the matrices used to make the key are invertible, it is possible to check only the order of the general linear group $GL_m(F_q)$ which also can be made intractable by choosing $q$ a very large prime number and $m$ large.

$GL_m(F_q)$, $q$ a prime number, consists of all invertible matrices of order $m\times m$ over $F_q$ ^[29]. This group has order

Consider $M_p(1)$. Since $M_p(1)$ is a $(p+2)\times (p+2)$ matrix, we must check

matrices. For example, for $M_{48}(1)$ over $F_{37}$, we have

and for the key $N_p(k)$

Table 1 gives $N_p(k)$, $q$, and $\mid GL_p(F_q) \mid$ for $2 \leq p \leq 4$ and $2\leq q\leq 11$. This shows that as $p$ and $q$ increase, the number of matrices grows significantly. Thus, it can be made intractable to break the protocol. From (4.1) and (4.2), it is clear that the key size increases with $p$, i.e. $\mid GL_{p}(F_q) \mid\rightarrow \infty$. Therefore, if the key space is large it is not practical to break the system via a brute-force attack ^[30].

5.   Conclusions

In this paper, two new sequences were defined using the Pell and Mersenne sequences. Their structures were examined and some results obtained using them. Then, they were used to develop a new Diffie-Hellman key exchange protocol that provides high security. The matrices $M_P(1)$ and $N_P(k)$ are constructed using these sequences so calculations are fast when $a$ and $b$ are very large, but it is intractable for an adversary to determine the key. This is the first algorithm that uses sequences and matrices to obtain a key. The sequences presented are suitable for constructing private keys. Note that other sequences such as Fibonacci and Pell sequences can be used with the proposed approach to construct keys. In general, any matrix sequence that has the commutative property for multiplication is suitable for use with this algorithm. As future work, the new sequences presented in this paper can be used in other private or public key encryption algorithms.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

Researchers would like to thank the Deanship of Scientific Research, Qassim University, for funding the publication of this paper.

Conflicts of Interest

The authors declare that there are no conflicts of interest regarding the publication of this paper.