Degree project

Tribonacci Cat Map

A discrete chaotic mapping with Tribonacci matrix

Author : Linnea Fransson

Supervisor : Per-Anders Svensson
Examiner : Karl-Olof Lindahl
Date: 2021-05-26
Course code: 5MA41E
Subject: Mathematics
Level : Master

Department Of Mathematics
 Acknowledgements

First of all, I would like to thank my friend and co-founder of Växjö MathsJam, Maria
Ulan, whose encouragement made me take the first step of the long journey that became
this thesis. Then, I would like to pass on my thanks to my supervisor, Per-Anders Svens-
son, for his guidance and immense patience during the whole process. Without his help,
there would have not been a thesis today. I would also like to send my appreciation to
my examiner, Karl-Olof Lindahl, for his wise words that helped improve my work even
further. In fact, I would like to express my deepest gratitude to all teachers from the
Department of Mathematics for believing in me and never giving up on me. Lastly, I
would like to thank my mother for standing by me through all times, and the rest of my
family and friends for their support.

i
 Abstract

Based on the generating matrix to the Tribonacci sequence, the Tribonacci cat map is
a discrete chaotic dynamical system, similar to Arnold’s discrete cat map, but on three
dimensional space. In this thesis, this new mapping is introduced and the properties of
its matrix are presented. The main results of the investigation prove how the size of the
domain of the map affects its period and explore the orbit lengths of non-trivial points.
Different upper bounds to the map are studied and proved, and a conjecture based on
numerical calculations is proposed. The Tribonacci cat map is used for applications such
as 3D image encryption and colour encryption. In the latter case, the results provided by
the mapping are compared to those from a generalised form of the map.

Keywords: Arnold’s cat map, Tribonacci matrix, chaotic map, discrete dynamical sys-
tem, linear recurrence sequence, Trisano period, 3D image encryption, colour encryption.

ii
Contents
1 Introduction 1
1.1 Purpose of the thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Thesis overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Preliminaries 4
2.1 Arnold’s cat map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Properties of the matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Periods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.4 Orbit lengths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.5 Generalised cat map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.6 Higher dimensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3 Mathematical background 12
3.1 Abstract Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2 Number Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

4 Results 17
4.1 Tribonacci cat map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.2 Properties of the matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.3 Periods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.3.1 Periods of composite N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.3.2 Periods of prime N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.3.3 Upper bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.4 Orbit lengths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.4.1 Orbit lengths of prime N . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.4.2 Orbit lengths of composite N . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.5 Generalised Tribonacci cat map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

5 Applications 40
5.1 3D image encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.2 Colour encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

6 Discussion 44
6.1 Tribonacci cat map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
6.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6.3 Future investigations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

References 47

A Mathematica code 49

B Prime number sets 51

iii
1 Introduction
When studying ergodic theory in the 1960s, the Russian mathematician, Vladimir Arnold,
introduced the world to a new chaotic dynamical system [8]. By using the picture of a cat,
Arnold showed how his newfound mapping rearranged the pixels into chaotic patterns before
recreating the original image. This mapping has ever since been known as Arnold’s cat map.

Figure 1: The image becomes unrecognisable for a number of iterations before returning to its
original state.

From the very beginning, Arnold’s cat map managed to catch the attention of mathematicians
and cryptographers around the world due to its simple and yet powerful properties. Until today,
there are articles being published regarding its mathematical structure and its computational
usage (for a selected list on the subject, see References). Since it was first introduced, Arnold’s
cat map has been modified to more generalised forms (see section 2.5) and adapted to higher
dimensions (see section 2.6).
The key to this mapping’s chaotic attributes lies on its connection to the Fibonacci sequence
(see section 2.2). This fact itself raises the question of whether the Tribonacci sequence could
create an equally powerful map in three dimensions. Such map, the Tribonacci cat map,
would be expected to have a mathematical structure worth being studied. Likewise, it could
become an effective alternative to the three dimensional adaptation of Arnold’s cat map in
applications such as encryption and watermarking.

1.1 Purpose of the thesis

The main purpose of this thesis is to study the properties of the discrete three dimensional
cat map based on the Tribonacci matrix, i.e. the Tribonacci cat map. In other words, we will
examine the outcomes of a 3D image once it has been exposed to the mapping. In order to
achieve this purpose, the investigations and analysis will focus on the questions:

1. How does the size of a 3D image affect the number of iterations of the whole image?

1
 2. To what extent does the image size have an impact on the iterations of single pixels?

Besides answering these questions, this thesis will also look at possible applications of the
Tribonacci cat map, presenting examples of 3D image encryption and colour encryption.

1.2 Methods
Much of the work presented here is based on empirical investigations and numerical calculations
performed by the software Wolfram MathematicaTM . The codes used for the purposes of
this thesis can be found in the appendix (see A Mathematica code), guaranteeing the replica-
bility of the results. Alongside with the empirical investigations, this thesis also presents work
based on theoretical results.
The first result consists in proving the strong relation between the period 1 of the Tribonacci
cat map and the period of the Tribonacci sequence in Theorem 4.2 by using matrix and
divisibility properties. Due to such relation, it has been deemed sufficient to prove the periods
of the Tribonacci sequence and simply adapt them to the Tribonacci cat map. These periods
have then been grouped based on the factorisation of the size of the 3D image. Theorems 4.5
and 4.8 use results from Wadill’s paper [23] in their proofs. The main result of this thesis,
Theorem 4.9, proves the properties of the periods of 3D images with prime sizes. The proof
relies on results from Number Theory, such as the Legendre symbol and its properties, and
concepts from Abstract Algebra, such as kernel, norm map, extension fields and multiplicative
groups. The proof is also built on two propositions from previous works, namely Propositions
4.10 and 4.11. The former is about the relation between the discriminant of a polynomial and
the number of its factors modulo a prime. It was originally introduced by Stickelberger and
can be found in Carlitz’s article [5]. The latter is taken from Adams & Shanks in [1] and
presents the relation between the period of a third order linear recurrence and the roots of its
minimal polynomial.
When studying the upper bounds of the Tribonacci cat map, Corollaries 4.13 and 4.14 are
based on an adaptation of Theorem 4.9 and use straightforward modular calculations to prove
the upper bounds of two sets of primes. In order to make a conjecture on a possible upper bound
for all periods of the mapping, the first 10,000 periods are calculated. Thereafter, numerical
calculations of ratios and least common multiples of periods are taken into consideration in
order to produce Conjecture 4.15. Even the study of orbit lengths 2 relies on both inductive and
deductive analysis. Concepts like divisibility from Number Theory and multiplicative order
from Abstract Algebra play a major role in the presentation of the orbit lengths for different
sizes of the 3D image. Theorem 4.16 and Corollary 4.17 use modular system of equations to
prove the number of disjoint orbits with length 1 in even and odd sized images respectively.
For the image encryptions, two pictures were used. The first one was taken from the author’s
private album and depicts the author’s family cat. It was used in its original quadratic format
for the colour encryption and, for the 3D image encryption, copies of the picture were placed on
top of each other in order to give it depth. The number of copies was the same as the side of the
picture. The second image was already cubic to begin with and it was taken from the software
1 A period is the minimum number of iterations that takes the whole image back to its original state. A

proper definition can be found on page 5.

2 An orbit length is the mininum number of iterations that takes a single pixel back to its original position.

A proper definition can be found on page 5.

2
Wolfram MathematicaTM ’s own collection of example images. The picture can be found
in the TestImage3D collection under the name “MRKnee”. In the 3D image encryption, the
two images were compared to each other after being encrypted using the Tribonacci cat map.
Meanwhile, in the colour encryption, the results from the original Tribonacci cat map were
compared to those achieved by a generalised form of the mapping presented in section 4.5. The
analysis of all encryptions performed for this thesis is entirely based on empirical observations.

1.3 Limitations
The calculations performed for this thesis were dependent on the computer where the software
Wolfram MathematicaTM was installed. This explains the number of calculated periods
being limited to 10,000, as the process of retrieving the periods becomes more demanding and
time consuming for greater numbers. Conjecture 4.15 is built upon the values achieved in
the interval and might be refuted with further period calculations. Likewise, the encryptions
realised in this investigation had to obey the limitations of the hardware and could not be
carried out with images over a certain size or with large periods.

1.4 Thesis overview

Sections 2 and 3 contain the necessary theoretical background for the results presented in
sections 4 and 5. In section 2, we present the original two dimensional chaotic map, Arnold’s cat
map, and introduce its discrete version used in image encryption. We look into the properties
of the map and its matrix, and focus on the results regarding its periods and orbits. We also
mention two forms of generalised cat maps and conclude the section with examples of discrete
cat maps in higher dimensions. Section 3 is dedicated to the results in Abstract Algebra and
Number Theory that are used in the proofs in section 4.
The Tribonacci cat map, along with its general properties, is proposed in section 4. We
study its matrix and its connection to the Tribonacci sequence. The main results of the thesis,
already mentioned in subsection 1.2, are contained in this section. We prove the properties
of the periods for different domain sizes based on the content in section 3 and examine the
upper bounds of the mapping. We also investigate the orbit lengths and analyse them using
empirical results and theoretical concepts from section 3. At the end of the section, we suggest
a generalised Tribonacci cat map.
In section 5, we use the proposed Tribonacci cat map for 3D image encryption and relate the
choices of image sizes to the results on periods and orbit lengths in section 4. The outcomes are
compared to those obtained using the discrete version of Arnold’s cat map. We also perform
colour encryption and compare the results attained by the original Tribonacci cat map and a
generalised form of the map. There is a short discussion on the advantages of the generalised
map over the original for colour encryption.
Lastly, in section 6, we summarise the results from sections 4 and 5, and discuss them
even further. At the end of the section, we propose future investigations on the subject. The
codes used for data gathering and image encryption are listed in appendix A. The sets of prime
numbers mentioned in the analysis of upper bounds and orbit lengths in section 4 can be found
in appendix B.

3
2 Preliminaries
In this section, we focus on the original Arnold’s cat map. We start by introducing the
properties of the map in subsection 2.1, and defining a couple of concepts, like period and
orbit, that are vital for the understanding of the main results in section 4. In subsection 2.2,
we study the matrix used in the map, also known as the cat matrix, and present its connection
to the generating matrix of the Fibonacci sequence. In subsection 2.3, we analyse the periods
of the Fibonacci sequence and transfer them to the discrete version of Arnold’s cat map. The
connection between the periods is proved in Theorem 2.4. At the end of the subsection, we
state the upper bounds of the map. The orbits, more precisely the orbit lengths, are displayed
with the help of colourful matrices in subsection 2.4. A couple of examples of generalised cat
maps are demonstrated in subsection 2.5, while a couple of examples of discrete cat maps in
higher dimensions are suggested in subsection 2.6.

2.1 Arnold’s cat map

Let (x, y) be the coordinates of a point in the unit square, such that 0 ≤ x, y < 1. Arnold’s cat
map (ACM) takes (x, y) to the new point (x′ , y ′ ), where

⎛x ′ ⎞ ⎛1 1⎞ ⎛x⎞
≡ (mod 1).
⎝ y ′ ⎠ ⎝1 2⎠ ⎝y ⎠

ACM is a dynamical system that works in discrete time and generates a chaotic mapping
inside a two-dimensional torus, a toral automorphism. This means that, after a finite number
of iterations, all points in the domain return to their original positions at the same time.
Mathematicians and computer scientists have shown a particular interest in the discrete
version of ACM, the so-called Arnold’s discrete cat map (DCM) (e.g. [2, 6, 8, 15]). Instead of
working within the unit square, the domain of the mapping is expanded to an N × N plane, i.e.
a plane of size N 2 , and the coordinates of the points in the domain are scaled to the integer
coordinates 0 ≤ x, y ≤ N − 1. For every discrete time t, t ≥ 1, the new mapping becomes

⎛xt ⎞ ⎛1 1⎞ ⎛xt−1 ⎞
≡ (mod N ).
⎝ yt ⎠ ⎝1 2⎠ ⎝ yt−1 ⎠

Example 2.1. Consider the 4 × 4-matrix and the (x, y)-coordinates of its elements modulo 4:

⎛A B C D⎞ ⎛(0, 3) (1, 3) (2, 3) (3, 3)⎞

⎜ ⎟ ⎜ ⎟
⎜E F G H⎟ ⎜(0, 2) (1, 2) (2, 2) (3, 2)⎟
⎜ ⎟ ≡ ⎜ ⎟ (mod 4)
⎜ ⎟ ⎜ ⎟
⎜I J K L⎟ ⎜(0, 1) (1, 1) (2, 1) (3, 1)⎟
⎜ ⎟ ⎜ ⎟
⎝M N O P⎠ ⎝(0, 0) (1, 0) (2, 0) (3, 0)⎠

4
This is what happens to the matrix when DCM is applied to it:

⎛A B C D⎞ ⎛ B H J P ⎞ ⎛H A N K⎞ ⎛ A B C D⎞
⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟
⎜E F G H⎟ ⎜ A⎟ ⎜ B⎟ ⎜ H⎟
⎜ ⎟ ↦ ⎜G I O ⎟ ↦ ⎜O L E ⎟ ↦ ⎜E F G ⎟.
⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟
⎜I J K L⎟ ⎜ F⎟ ⎜ I⎟ ⎜ L⎟
⎜ ⎟ ⎜L N D ⎟ ⎜F C P ⎟ ⎜I J K ⎟
⎝M N O P ⎠ ⎝M C E K ⎠ ⎝M J G D ⎠ ⎝M N O P⎠

Here is what happens to the coordinates of four arbitrary elements in the matrix:

D ∶ (3, 3) ↦ (2, 1) ↦ (3, 0) ↦ (3, 3);

K ∶ (2, 1) ↦ (3, 0) ↦ (3, 3) ↦ (2, 1);
P ∶ (3, 0) ↦ (3, 3) ↦ (2, 1) ↦ (3, 0);
J ∶ (1, 1) ↦ (2, 3) ↦ (1, 0) ↦ (1, 1).

It takes three iterations of the DCM to return the matrix to its original state. The coordinates
of the elements D, K and P are mapped to each other, while the coordinates of the element J
are mapped to other elements in the matrix. After a closer look, one can see that J is mapped
to the coordinates of the elements C and N . The 4 × 4 plane in the example has period 3 and
the coordinates of the elements D, K and P belong to one orbit, while the coordinates of the
elements J, C and N belong to another orbit.

Definition 2.1. The period of the DCM is the smallest positive integer t such that

⎛x t ⎞ ⎛x 0 ⎞
≡ (mod N ),
⎝ yt ⎠ ⎝ y0 ⎠

for all points (x, y) in the domain. In other words, it is the minimum number of iterations
that maps the whole plane back to its original state. In this thesis, the period of a DCM on a
plane of size N 2 will be denoted by ρ(N ).

Definition 2.2. The orbit of a point is the set of all coordinates that the point is mapped to
under the iterations of the DCM, until being mapped back to itself. The orbit length is the
number of distinct coordinates in the set. In Example 2.1, all points except for M have orbit
length 3. As it only maps to itself, M is called a fixed point and has orbit length 1. The origin
is always a fixed point so it is known as trivial point.

Due to its chaotic nature, DCM has been studied and used in image encryption and wa-
termarking over the recent years (e.g. [4, 7, 14]). On the next page, there is an example to
illustrate the behaviour of DCM on a picture of size 400 × 400 pixels after t iterations.

5
 (a) Original image (b) t = 1 (c) t = 2 (d) t = 10

(e) t = 60 (f) t = 150 (g) t = 185 (h) t = 237

(i) t = 286 (j) t = 298 (k) t = 299 (l) t = 300

Figure 2: The original image is successfully retrieved after 300 iterations.

Since it takes 300 iterations to recover the original image for the first time, the period in this
case is ρ(400) = 300. After one iteration, the picture is relatively chaotic yet not unrecognisable.
On the second iteration, however, the cat is no longer visible even though the original colours
are still distinguishable. For most of the iterations, the result is similar to the one at t = 10.
When t = 150, and for a few other values of t, there are ghosts of the original picture covering
the plane. This phenomenon, along with the occurrence of miniatures of the mapped image,
is investigated and discussed in Behrends’ article [3].

2.2 Properties of the matrix

The chaotic properties of Arnold’s cat map derive from its matrix3

⎛1 1⎞
A= .
⎝1 2⎠

Its determinant is equal to 1, which results in the mapping being area preserving. This means
that, apart from shuffling the points inside the unit square in the ACM (or inside the N × N -
image in the DCM), there is neither any loss nor changes made to the points in the domain.
The entries of A are in fact Fibonacci numbers. Recall that the Fibonacci sequence (Fn )∞
n=0
is defined by F0 = 0, F1 = 1, and Fn = Fn−1 + Fn−2 for n ≥ 2. The numbers in the sequence can
3 In some literature, such as in [3], the matrix is given by ( 21 11 ) instead.

6
be generated by the matrix

⎛0 1⎞ ⎛Fn−1 Fn ⎞
F= , where Fn = .
⎝1 1⎠ ⎝ Fn Fn+1 ⎠

When F is multiplied by itself, the result becomes the cat matrix. Thus the powers of A are
also powers of the generating Fibonacci matrix.

⎛F1 F2 ⎞ ⎛ 1 1⎞
F2 = = =A and
⎝F2 F3 ⎠ ⎝ 1 2⎠
n
⎛1 1⎞ ⎛F2n−1 F2n ⎞
A =n
= .
⎝1 2⎠ ⎝ F2n F2n+1 ⎠

The minimal polynomial of A is PA (x) = x2 − 3x + 1, with discriminant 5 and roots

√ √
3+ 5 3− 5
x1 = and x2 = .
2 2

The connection to the Fibonacci sequence, together with the discriminant of the minimal
polynomial, has a major impact on the periods of DCM.

2.3 Periods
Since the matrix in the DCM is derived from the Fibonacci generating matrix, its period
modulo N is strongly related to the period of the recurrence relation modulo N .

Definition 2.3. In the Fibonacci sequence, the smallest positive integer k such that Fk ≡ F0
(mod N ) and Fk+1 ≡ F1 (mod N ) is called the Pisano period. It will be denoted by π(N ).

In other words, a Fibonacci sequence with Pisano period π(N ) = k looks like this:

F0 F1 F2 F3 ⋯ Fk−2 Fk−1 Fk Fk+1 Fk+2 Fk+3

0 1 1 2 ⋯ N −1 1 0 1 1 2

Theorem 2.4. For every integer N ≥ 3, the period of DCM modulo N is given by

π(N )
ρ(N ) = .
2

Proof. Let π(N ) = k. It means that

⎛Fk−1 Fk ⎞ ⎛1 0⎞
Fk = ≡ (mod N ).
⎝ Fk Fk+1 ⎠ ⎝0 1⎠

Since A = F2 , then Ak/2 = Fk and the theorem follows.

Remark. The theorem works because π(N ) is always even for N > 2. Further details about
the Pisano period can be found in Wall’s article [24].

7
Example 2.2. The Pisano period for N = 74 is 228 while its cat map period is 114. Likewise,
π(37) = 76 while ρ(37) = 38.

In order to better understand the periods of the cat map for different values of N , it is
inevitable to firstly introduce the properties of the Pisano period. Wall presents an extensive
study with proofs in [24]. Here are some of the known properties that are relevant for this
thesis:

(i) If N is a prime such that p ≡ ±1 (mod 5), then π(p) ∣ p − 1.

(ii) If N is a prime such that p ≡ ±2 (mod 5), then π(p) ∣ 2(p + 1).

(iii) If N is a prime power such that N = pk and if π(p2 ) ≠ π(p), then π(pk ) = pk−1 π(p), k ≥ 2.

(iv) If N is composite and has the prime factorisation N = pα

1 p2 ⋯pn , then π(N ) =
1 α2 αn

i )), where lcm is the least common multiple.

lcm(π(pαi

Remark. Properties (i) and (ii) provide information for calculating kπ(N ), i.e. a multiple of
the period, where k is a positive integer.

Example 2.3. Let N = 27. Since 27 = 33 and 3 ≡ −2 (mod 5), properties (ii) and (iii) can
be used. The former yields π(3) ∣ 8 and, in this case, π(3) = 8. The latter property gives
π(27) = 9 ⋅ π(3) = 9 ⋅ 8 = 72.

Example 2.4. Let N = 33 = 3 ⋅ 11. From the previous example it is known that π(3) = 8.
Property (i) states that π(11) ∣ 10, which is the case as π(11) = 10. Finally, according to
property (iv), the period becomes π(33) = lcm(8, 10) = 40.

It is noteworthy that even though property (iv) is based on the hypothesis π(p2 ) ≠ π(p),
there are still no known primes that fulfill π(p2 ) = π(p). These primes are called Wall-Sun-Sun
primes 4 and the search for them is still ongoing [16]. By 2014, a project held by PrimeGrid
could verify that no such prime exists up to 28 ⋅ 1015 [17]. Nonetheless, it has not been proven
that Wall-Sun-Sun primes do not exist.
Observe that properties (i) and (ii) depend on the discriminant of the Fibonacci matrix,
which is the same as the discriminant of the cat matrix. According to these properties, the
period of the cat map for N = p, p a prime, is conditioned to whether 5 is a quadratic residue5
of p, as in property (i), or not, as in (ii).
The periods of the cat map and their properties can be easily derived from the Pisano
periods. The results from Theorem 2.4 are clear in (i) and (ii):

(i)* If N is a prime such that p ≡ ±1 (mod 5), then ρ(p) ∣ p−1

2
.

(ii)* If N is a prime such that p ≡ ±2 (mod 5), then ρ(p) ∣ p + 1.

(iii)* If N is a prime power such that N = pk , p > 2, and if ρ(p2 ) ≠ ρ(p), then ρ(pk ) = pk−1 ρ(p),
k ≥ 2.

(iv)* If N is composite and has the prime factorisation N = pα

1 p2 ⋯pn , then ρ(N ) =
1 α2 αn

i )).
lcm(ρ(pαi

4 In Peng’s article [16], these primes are called Fibonacci-Wieferich primes.

5A definition of quadratic residue can be found on page 14.

8
Remark. Unlike with the Pisano period, there is at least one known prime, i.e. p = 2, where
ρ(p2 ) = ρ(p).

Example 2.5. For the composite numbers N1 = 27 and N2 = 33, the cat map periods are
ρ(27) = 36 and ρ(33) = 20. For the prime numbers p = 41 ≡ 1 (mod 5) and p = 43 ≡ −2 (mod
5), the periods are ρ(41) = 20 and ρ(43) = 44.

Authors like Bao and Chen study the properties (i)*-(iv)* and deepen their investigations
by analysing the periods of a generalised DCM in [2] and [6] respectively. More on these under
subsection 2.5. Dyson and Falk take one step further and examine the lower and upper bounds
of the periods of DCM in [8]. In their article, they state and prove the following theorem
regarding the upper bounds:

Theorem 2.5. For a positive integer k,

ρ(N ) = 3N when N = 2 ⋅ 5k ,
ρ(N ) = 2N when N = 5k or N = 6 ⋅ 5k ,
12
ρ(N ) ≤ N for all other N.
7

2.4 Orbit lengths

For any value of N , the orbit lengths of the points in the domain are less or equal to ρ(N ).
Moreover, they are divisors of the period and the origin is the only fixed point with orbit
length equal to 1. Consequently, there are a number of disjoint orbits in the DCM, as seen in
Example 2.1 on page 4.
When N is a prime number p, where p ≠ 5, all orbit lengths of the non-trivial points are
equal to ρ(N ). In the case where N = 5, the lengths of the orbits are either equal to ρ(5) = 10
or equal to ρ(5)/5 = 2. Gaspari presents an extensive investigation on orbits and orbit lengths
for prime periods of DCM in [11].

Example 2.6. The orbit lengths of each point in the DCM when N = 5 and N = 7 are
presented as entries in the matrices6 below.

⎛ 8 8 8 8 8 8 8 ⎞
⎜ ⎟
⎛ 10 10 10 2 10 ⎞ ⎜ 8 8 8 8 8 8 8 ⎟
⎜ ⎟
⎜ ⎟ ⎜ ⎟
⎜ 10 ⎟ ⎜ 8 ⎟
⎜ 10 2 10 10 ⎟ ⎜ 8 8 8 8 8 8 ⎟
⎜ ⎟ ⎜ ⎟
⎜ 2 ⎟ ⎜ 8 ⎟
⎜ 10 10 10 10 ⎟ ⎜ 8 8 8 8 8 8 ⎟
⎜ ⎟ ⎜ ⎟
⎜ 10 ⎟ ⎜ 8 ⎟
⎜ 10 10 2 10 ⎟ ⎜ 8 8 8 8 8 8 ⎟
⎜ ⎟ ⎜ ⎟
⎝ 10 ⎠ ⎜ 8 ⎟
1 10 10 10 ⎜ 8 8 8 8 8 8 ⎟
⎜ ⎟
⎝ 1 8 8 8 8 8 8 ⎠

N =5 N =7

When N is a composite number, except for when N = 4, there will be at least three different
6 The idea of illustrating the orbit lengths in colourful matrices is taken from Svanström’s work on a gener-
alised Arnold’s cat map [21].

9
orbit lengths: 1 (the trivial point), ρ(N ) and at least one non-trivial divisor of ρ(N ). In the
special case for N = 4, all non-trivial points have orbit length equal to ρ(4) = 3.

Example 2.7. The matrices below illustrate the orbit lengths for each point in the DCM
when N = 6 and N = 8.

⎛ 6 6 6 6 6 6 6 6 ⎞
⎜ ⎟
⎛ 12 12 12 12 12 12 ⎞ ⎜ 3 6 3 6 3 6 3 6 ⎟
⎜ ⎟
⎜ ⎟ ⎜ ⎟
⎜ 4 12 4 12 4 12 ⎟ ⎜ 6 6 6 6 6 6 6 6 ⎟
⎜ ⎟ ⎜ ⎟
⎜ ⎟ ⎜ ⎟
⎜ 12 3 12 12 ⎟ ⎜ 6 ⎟
⎜ 3 12 ⎟ ⎜ 3 6 3 6 3 6 3 ⎟
⎜ ⎟ ⎜ ⎟
⎜ 4 12 4 12 ⎟ ⎜ 6 ⎟
⎜ 4 12 ⎟ ⎜ 6 6 6 6 6 6 6 ⎟
⎜ ⎟ ⎜ ⎟
⎜ 12 12 12 12 ⎟ ⎜ 6 ⎟
⎜ 12 12 ⎟ ⎜ 3 6 3 6 3 6 3 ⎟
⎜ ⎟ ⎜ ⎟
⎝ ⎜ ⎟
1 12 4 3 4 12 ⎠ ⎜ 6 6 6 6 6 6 6 6 ⎟
⎜ ⎟
⎝ 1 6 3 6 3 6 3 6 ⎠

N =6 N =8

2.5 Generalised cat map

As mentioned earlier in subsection 2.3, there are generalised forms of DCM. These are preferred
over the original mapping for encryption and image validation because of their diversity. The
entries in the generalised cat matrices are not uniquely determined as in the original, which
leads to different periods for the same modulo N .
On an N 2 plane, a general form of DCM is

⎛xt ⎞ ⎛1 p ⎞ ⎛xt−1 ⎞
≡ (mod N )
⎝ yt ⎠ ⎝q 1 + pq ⎠ ⎝ yt−1 ⎠

where p, q ∈ {0, 1, ⋯, N − 1}.

As Chen et al. state in their paper [6], as long as the determinant of the cat matrix is equal
to 1, the map is area preserving and periodic for any initial point. They study the properties
of the periods and their range for different values of p and q under the same modulo N . One
of their examples states that, for N = 17, there are 16 different cat maps with the maximum
period 34 and 48 mappings with period equal to 18.
Bao & Yang take a different step in [2] and study the generalised form of DCM when p = q:

⎛x t ⎞ ⎛ 1 a ⎞ ⎛xt−1 ⎞
≡ (mod N ).
⎝ yt ⎠ ⎝a 1 + a2 ⎠ ⎝ yt−1 ⎠

Like in Chen’s paper, Bao & Yang present and prove several theorems regarding the generalised
mapping’s periods. For example, for any value of a, if N = a2 , then the period of the cat map
is equal to a.

10
2.6 Higher dimensions
Over the years, extensions of DCM into higher dimensions have also been studied. In his
paper, Nance creates a three dimensional cat matrix by fixing each one of the coordinates in
the x, y, z-space and keeping the original 2 × 2 matrix on the remaining coordinates [15]. He
presents a similar example for the four-dimensional case, which is based on the 3 × 3 matrix,
and introduces a general formula for the creation of an n-dimensional cat matrix. A three
dimensional cat matrix created according to Nance’s instructions can be seen below:

⎛1 0 0⎞ ⎛1 0 1⎞ ⎛1 1 0⎞ ⎛1 1 1⎞
⎜ ⎟⎜ ⎟⎜ ⎟ ⎜ ⎟
⎜0 1 1⎟ ⎜ 0⎟ ⎜ 0⎟ =⎜ 2⎟ . (2.1)
⎜ ⎟ ⎜0 1 ⎟ ⎜1 2 ⎟ ⎜2 3 ⎟
⎝0 1 2⎠ ⎝1 0 2⎠ ⎝0 0 1⎠ ⎝3 4 4⎠

It is important, however, to highlight that the matrix in (2.1) is not unique due to the non-
commutative properties of matrix multiplication. There are as many as 6 possible cat matrices
n
in three dimensions and at most ∏ k! different alternatives in n dimensions. Nevertheless, all
k=3
versions in any dimension will have the determinant equal to 1, keeping the volume preserving
properties of the mapping.
Here is one of the 4! ⋅ 3! = 144 different versions of the four dimensional DCM based on the
3 × 3 matrix in (2.1):

⎛1 0 0 0⎞ ⎛1 0 1 1 ⎞ ⎛1 1 0 1⎞ ⎛1 1 1 0⎞ ⎛ 17 23 18 5 ⎞
⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟ ⎜ ⎟
⎜0 1 1 1⎟ ⎜ 0⎟ ⎜ 2⎟ ⎜ 0⎟ ⎜ 31 ⎟
⎜ ⎟ ⎜0 1 0 ⎟ ⎜2 3 0 ⎟ ⎜2 3 3 ⎟ = ⎜110 149 117 ⎟.
⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟ ⎜ ⎟
⎜0 2 3 2⎟ ⎜ 2⎟ ⎜ 0⎟ ⎜ 0⎟ ⎜ 72 ⎟
⎜ ⎟ ⎜2 0 3 ⎟ ⎜0 0 1 ⎟ ⎜3 4 4 ⎟ ⎜257 348 274 ⎟
⎝0 3 4 4 ⎝3
⎠ 0 4 4 ⎝3
⎠ 4 0 4 ⎝0
⎠ 0 0 1 ⎠ ⎝432 585 460 122⎠

Since the chaotic properties of the cat map are preserved in higher dimensions, these matrices
have also gained their place in image encryption. An example is Ganesan and Murali’s propo-
sition of using an 8 × 8 cat matrix in an encryption algorithm in [10]. The size of the matrix
is to match with the number of bits of each pixel in the image. In their article, they use a
different but similar approach to Nance’s when creating the eight dimensional matrix.
In most cases, the three dimensional extension of the cat map is enough. In [7], Choi et al.
create a generalised version of the 3 × 3 matrix and use it to encrypt colour medical images by
shuffling the positions of the colour pixels in the RGB-channels. Meanwhile, in [18], Raj et al.
use a three dimensional version of DCM to separately encrypt the vertices and the faces of 3D
models.

11
3 Mathematical background
The main results of the thesis, presented in section 4, rely on previous knowledge from both
Abstract Algebra and Number Theory. The purpose of this section is to introduce the reader
to the necessary concepts and theorems. The proofs are omitted here but can be found in
Hungerford’s Abstract Algebra [12] and Rosen’s Elementary Number Theory [19].

3.1 Abstract Algebra

The main result in section 4, namely Theorem 4.9 that proves the properties of the periods for
prime values of N , is based on the concept of finite fields and their properties.

Theorem 3.1. Let F be a finite field. Then, for a specific prime p and any element α ∈ F , it
is true that
α + α + ⋯ + α = pα = 0.
´¹¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¸ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¶
p times

Example 3.1. The set of rational numbers, Q, is an infinite field. Meanwhile, the set Z7 =
{0, 1, 2, 3, 4, 5, 6} is a finite field, and any element in Z7 multiplied by the prime number 7 is
equal to 0 modulo 7.

Definition 3.2. Let F and K be fields where F is finite and F ⊆ K. Suppose α ∈ K is algebraic
over F . Then the smallest subfield of K that contains α and all elements of F is called a finite
extension field and will be denoted F (α).

Definition 3.3. The order of a finite field F is the number of elements in it. The order of F
is denoted ∣F ∣.

Theorem 3.4. If F has p elements, where p is prime, then the finite extension field K = F (α)
has order equal to a power of p.

Example 3.2. The finite field Z7 , with size ∣Z7 ∣ = 7, does not contain the roots of the polyno-
√ √
mial P (x) = x2 − 3. The finite field Z7 ( 3) = {a + b 3 ∣ a, b ∈ Z7 }, on the other hand, contains
both the field Z7 and the roots of P (x). It is therefore an extension field of Z7 and has size
√
∣Z7 ( 3)∣ = 72 = 49.

Besides finite fields and their finite extensions, Theorem 4.9 also deals with multiplicative
groups and some properties related to them.

Definition 3.5. The multiplicative group F ∗ of the finite field F contains all non-zero elements
of F .

Theorem 3.6. If F is a finite field, then the multiplicative group F ∗ is cyclic, i.e.

F ∗ = {αk ∣ k ∈ Z},

for some α ∈ F ∗ .

12
Example 3.3. Take the subset Z∗7 = {1, 2, 3, 4, 5, 6} of the field Z7 . It is cyclic and generated
by 3:

31 ≡ 3 (mod 7), 32 ≡ 2 (mod 7), 33 ≡ 6 (mod 7),

34 ≡ 4 (mod 7), 35 ≡ 5 (mod 7), 36 ≡ 1 (mod 7).

Definition 3.7. Let α be an element of the subgroup F ∗ of the finite field F . The smallest
positive integer k such that αk = 1 is called the multiplicative order of α. In this thesis, it will
be denoted by ord(α).

The definition of the multiplicative order of an element is important both for the proof
of Theorem 4.9 and for the study of orbit lengths. Furthermore, the following theorems and
definitions are equally important.

Theorem 3.8. Let α be an element in F ∗ . Then ord(α) ∣ ∣F ∗ ∣.

Example 3.4. Looking back at Example 3.3, we see that ord(3) = 6 and ∣Z∗7 ∣ = 6. Clearly,
ord(3) ∣ ∣Z∗7 ∣. With simple calculations, we can also see that

ord(1) = 1, ord(2) = ord(4) = ord(5) = 3, ord(6) = 2.

And they are all divisors of ∣Z∗7 ∣ = 6.

For the sake of repetition, the remaining definitions and theorems in this subsection will be
working with a finite field F and its finite extension K = F (α).

Definition 3.9. Two algebraic elements α1 , α2 are said to be conjugates over F if there is a
polynomial P (x) that is irreducible over F such that P (α1 ) = P (α2 ) = 0.

Definition 3.10. The norm of an element α ∈ K is defined as the product of its conjugates.
Besides, for any elements α1 , α2 ∈ K, the norm map N ∶ K ∗ → F ∗ fulfils

N (α1 α2 ) = N (α1 )N (α2 ).

The map is a surjective homomorphism of the multiplicative groups of K and F respectively.

Furthermore, if the polynomial P (x) = xn + an−1 xn−1 + ⋯ + a0 is irreducible over F and has
roots αi in K, then7
N (αi ) = (−1)n a0 . (3.1)

Theorem 3.11. Let f ∶ G → H be a homomorphism of groups. Then the kernel of f , denoted

by ker f = {g ∈ G ∣ f (g) = 1H }, is a subgroup of G. When both G and H are finite, then

∣G∣
∣ker f ∣ = .
∣H∣

7 This result is actually taken from Vince’s article [22].

13
 √
Example 3.5. Let us once again take the finite field Z7 and the extension field Z7 ( 3). This
√ √
time, we will look at the element 2 + 3 in Z7 ( 3), which is one of the roots of the polynomial
p(x) = x2 − 4x + 1. We take the element and calculate its norm:
√ √ √ √
N (2 + 3) = (2 + 3)(2 − 3) = 22 − ( 3)2 = 1.
√
It is clear that the norm of 2 + 3 can be calculated as in (3.1):
√
N (2 + 3) = (−1)2 ⋅ 1 = 1.
√
Since 1 is the identity element of the multiplicative group Z∗7 , the element 2 + 3 belongs to
the kernel of N , i.e. ker N .

Example 3.6. The norm map N in Example 3.5 is a homomorphism between the multiplica-
√
tive subgroups Z7 ( 3)∗ and Z∗7 . Their orders are
√
∣Z7 ( 3)∗ ∣ = 49 − 1 = 48 and ∣Z∗7 ∣ = 7 − 1 = 6.

From Theorem 3.11, we have that the order of the kernel is

48
∣kerN ∣ = = 8.
6

3.2 Number Theory

From Number Theory, the concept of the Legendre symbol and its properties are also vital for
the proof of Theorem 4.9. Consequently, quadratic residues are equally important.

Definition 3.12. Let a and n be integers, where n > 0. If gcd(a, n) = 1 and the congruence
x2 ≡ a (mod n) has a solution, then a is a quadratic residue of n. If the congruence x2 ≡ a
(mod n) has no solution, then a is said to be a quadratic nonresidue of n.

Example 3.7. We compute the squares of the integers 1, 2, 3, 4, 5, 6 modulo 7. We have

12 ≡ 62 ≡ 1 (mod 7), 22 ≡ 52 ≡ 4 (mod 7), 32 ≡ 42 ≡ 2 (mod 7).

The integers 1, 2, and 4 are quadratic residues of 7, while the integers 3, 5 and 6 are quadratic
nonresidues of 7.

Already in section 2, the concept of quadratic residues was used in the classification of
periods of the DCM modulo a prime. In the proof of Theorem 4.9 about the periods of prime
values of N , this concept is equally inevitable, along with the following definition and its
subsequent theorems.

Definition 3.13. Let a be an integer and p be an odd prime. The Legendre symbol is defined
to be
⎧
⎪
⎪
⎪
⎪
1 if a is a quadratic residue of p;
a ⎪
⎪
( ) = ⎨−1 if a is a quadratic nonresidue of p;
p ⎪
⎪
⎪
⎪
⎪
⎪
⎩0 if a is divisible by p.

14
Example 3.8. From the previous example, we have the following values:

1 2 4 3 5 6
( )=( )=( )=1 and ( ) = ( ) = ( ) = −1.
7 7 7 7 7 7

Theorem 3.14. Let p be an odd prime and a and b be integers not divisible by p. Then
(i) if a ≡ b (mod p), then ( ap ) = ( pb ) ;

(ii) ( ap ) ( pb ) = ( ab
p
);
2
(iii) ( ap ) = 1.
Example 3.9. We will calculate ( 495
7
) using the theorem above. We start by factorising 495
into 5 ⋅ 11 ⋅ 172 and, by part (ii) in Theorem 3.14, we have

495 5 ⋅ 11 ⋅ 172 5 11 172

( )=( ) = ( )( )( ).
7 7 7 7 7

Since 11 ≡ 4 (mod 7), we can use part (i) of the theorem and get

11 4
( ) = ( ).
7 7

Using part (iii), we find that

172
( ) = 1.
7
Finally, putting all parts together along with the results from the previous example, we get

495
( ) = 1 ⋅ (−1) ⋅ 1 = −1.
7

Theorem 3.15 (Euler’s Criterion). Let a be an integer and p be an odd prime that does not
divide a. Then
a
( ) ≡ a(p−1)/2 (mod p).
p
Example 3.10. If we let a = −1 and p be any odd prime, then Euler’s Criterion gives us

⎧
⎪
−1 (p−1)/2
⎪1
⎪ if p ≡ 1 (mod 4);
( ) = (−1) =⎨
p ⎪
⎪
⎩−1
⎪ if p ≡ 3 (mod 4).

When p ≡ 1 (mod 4), i.e. p = 4k + 1 for some positive integer k, then

(−1)(p−1)/2 = (−1)2k = 1.

Likewise, when p ≡ 3 (mod 4), i.e. p = 4k + 3 for some positive integer k, then

(−1)(p−1)/2 = (−1)2k+1 = −1.

Theorem 3.16 (The Law of Quadratic Reciprocity). Let p and q be distinct odd primes. Then

p q
( ) ( ) = (−1) 2 ⋅ 2 .
p−1 q−1

q p

15
In Example 3.10, we saw that (p − 1)/2 is even when p ≡ 1 (mod 4), and it is odd when p ≡ 3
(mod 4). The same is true when q ≡ 1 (mod 4) and q ≡ 3 (mod 4) respectively. Hence,

⎧
⎪
p q ⎪
⎪1 if p ≡ 1 (mod 4) or q ≡ 1 (mod 4) or both;
( )( ) = ⎨
q p ⎪
⎪
⎩−1
⎪ if p ≡ q ≡ 3 (mod 4).

From the Law of Quadratic Reciprocity and the results above, we have that, for two distinct
odd primes p and q,

⎧
⎪
p ⎪( q )
⎪ if p ≡ 1 (mod 4) or q ≡ 1 (mod 4) or both;
( )=⎨ p
q ⎪
⎪
⎩− ( p ) if p ≡ q ≡ 3 (mod 4).
q
⎪

We have now the necessary tools to introduce the new discrete chaotic mapping, the Tribonacci
cat map, and to analyse its behaviour in form of periods and orbit lenghts.

16
4 Results
In this section, we introduce the chaotic three dimensional map, the Tribonacci cat map. We
start by presenting the map itself in subsection 4.1. In subsection 4.2, we study the matrix used
in the map, which can be known as the Tribonacci cat matrix, and demonstrate its connection
to the generating matrix of the Tribonacci sequence.
In the beginning of subsection 4.3, we prove the connection between the period of the
Tribonacci sequence and the period of the Tribonacci cat map in Theorem 4.2. Because of this
connection, the remaining of the subsection focus on proving the properties of the periods of
the Tribonacci sequence. Theorems 4.5 and 4.8 are adaptations of results taken from Wadill’s
article [23] and prove the properties of periods of composite N . The proof of Theorem 4.9,
which is the main result of the thesis, depends on the mathematical background from section
3 and on Propositions 4.10 and 4.11 to prove the properties of periods of prime N . The results
from Theorem 4.9 are then adapted to the Tribonacci cat map in Theorem 4.12. Still in
subsection 4.3, we divide the prime numbers into sets according to their periods and analyse
the upper bounds for different values of N . We propose Corollaries 4.13 and 4.14 for their
respective sets of prime numbers and Conjecture 4.15 for all values of N .
In subsection 4.4, we use the concept of multiplicative order from section 3, together with
empirical investigations, and study the orbit lengths of the different sets of prime values of N .
We also conduct an inductive analysis on the orbit lengths of composite N . The subsection
ends with Theorem 4.16 about the number of fixed points when N is even, and Corollary 4.17,
that proves the number of fixed points when N is odd.
Lastly, in subsection 4.5, we propose a generalised Tribonacci cat map and compares a
couple of its properties with those of the original Tribonacci cat map. An example of the
generalised map is used for colour encryption in section 5.

4.1 Tribonacci cat map

Let (x, y, z) be the coordinates of a point in an N × N × N space. For every discrete time t,
where t ≥ 1, the Tribonacci cat map is defined by the following mapping:

⎛xt ⎞ ⎛1 1 1⎞ ⎛xt−1 ⎞
⎜ ⎟ ⎜ ⎟⎜ ⎟
⎜ y t ⎟ ≡ ⎜1 2 2⎟ ⎜ ⎟ (mod N ).
⎜ ⎟ ⎜ ⎟ ⎜ yt−1 ⎟
⎝ zt ⎠ ⎝2 3 4⎠ ⎝ zt−1 ⎠

Like the original DCM in three dimensions, this mapping is chaotic. Any three dimensional
image will iterate into undistinguishable 3D images until it is eventually recovered after a
limited amount of iterations. The period of the Tribonacci cat map modulo N will be denoted
by ρ′ (N ).

17
4.2 Properties of the matrix
The chaotic properties of the Tribonacci cat mapping derive from its matrix

⎛1 1 1⎞
⎜ ⎟
B = ⎜1 2 2⎟ .
⎜ ⎟
⎝2 3 4⎠

As with the original cat matrix, the determinant of B is equal to 1, which means that it is
volume preserving. The points within the N 3 -image are shuffled inside its domain without any
loss or gain of information.
While the entries in the 2×2 cat matrix are Fibonacci numbers, the entries in B are numbers
of the generalised Fibonacci sequence, also known as the Tribonacci sequence (Tn )∞
n=0 . This
sequence is recursively defined by8 as T0 = T1 = 0, T2 = 1, and Tn = Tn−1 + Tn−2 + Tn−3 for n ≥ 3.
The numbers in the sequence can be generated by the matrix9

⎛0 1 0⎞ ⎛Tn−1 Tn−2 + Tn−1 Tn ⎞

⎜ ⎟ ⎜ ⎟
T = ⎜0 0 1⎟ where T = ⎜ Tn
n
Tn−1 + Tn Tn+1 ⎟ .
⎜ ⎟ ⎜ ⎟
⎝1 1 1⎠ ⎝Tn+1 Tn + Tn+1 Tn+2 ⎠

From matrix multiplication Tn Tk = Tn+k , the element Tn+k can be written as

Tn+k = Tn Tk−1 + (Tn−1 + Tn )Tk + Tn+1 Tk+1 . (4.1)

Likewise, after some simplification, the determinant of T is

Tn3 + Tn−1
2
Tn+2 + Tn+1
2
Tn−2 − 2Tn−1 Tn Tn+1 − Tn−2 Tn Tn+2 = 1. (4.2)

When the generating matrix T is raised to the power of three, the result becomes the Tribonacci
cat matrix B. Consequently, any power of B will also be a power of the Tribonacci matrix.

⎛T2 T1 + T2 T3 ⎞ ⎛1 1 1⎞
⎜ ⎟ ⎜ ⎟
T = ⎜T2
3
T2 + T3 T4 ⎟ =⎜ 2⎟ = B and
⎜ ⎟ ⎜1 2 ⎟
⎝T4 T3 + T4 t5 ⎠ ⎝2 3 4⎠
n
⎛1 1 1⎞ ⎛T3n−1 T3n−2 + T3n−1 T3n ⎞
⎜ ⎟ ⎜ ⎟
B = ⎜1
n
2 2⎟ = ⎜ T3n T3n−1 + T3n T3n+1 ⎟ .
⎜ ⎟ ⎜ ⎟
⎝2 3 4⎠ ⎝T3n+1 T3n + T3n+1 T3n+2 ⎠

The minimal polynomial of B is PB (x) = x3 − 7x2 + 5x − 1, where the discriminant is −44 and
8 For this thesis, the initial values in the recurrence relation are the same as in Klaška’s article [13] and in

The On-Line Encyclopedia of Integer Sequences® (http://oeis.org). Meanwhile, authors like Wadill [23] use
the initial values T0 = 0, T1 = T2 = 1, and authors like Spickerman [20] prefer T0 = T1 = 1, T2 = 2.
9 This generating matrix is taken from Fransson’s thesis on generalised Fibonacci series [9].

18
its roots are10

1
x1 = (7 + σ1 + σ2 )
3
1 √ √
x2 = (14 + i( 3 + i)σ1 − (1 + 3i)σ2 )
6
1 √ √
x3 = (14 + i( 3 + i)σ2 − (1 + 3i)σ1 )
6

where √ √
3 √ 3 √
σ1 = 199 − 3 33 and σ2 = 199 + 3 33.

The prime factors of the discriminant to the minimal polynomial will play an import role in
the study of the periods of the Tribonacci cat map. Likewise, the connection to the Tribonacci
sequence will be of help when calculating the periods of the mapping.

4.3 Periods
Since the Tribonacci cat map is derived from the third order recurrence relation, the Tribonacci
sequence, their periods modulo N are closely related. This relation is similar to the one found
between the period of the original cat map and the Pisano period. Before demonstrating their
relation in Theorem 4.2, the following definition is required.

Definition 4.1. In the Tribonacci sequence, the smallest positive integer k such that Tk ≡ T0
(mod N ), Tk+1 ≡ T1 (mod N ) and Tk+2 ≡ T2 (mod N ) is called the Trisano period. It is denoted
by π ′ (N ).

In other words, a Tribonacci sequence with Trisano period π ′ (N ) = k looks like this:

T0 T1 T2 T3 T4 ⋯ Tk−2 Tk−1 Tk Tk+1 Tk+2 Tk+3 Tk+3

0 0 1 1 2 ⋯ N −1 1 0 0 1 1 2

Theorem 4.2. For every integer N ≥ 2, the period of the Tribonacci cat map modulo N is

π ′ (N )
ρ′ (N ) = when 3 ∣ π ′ (N ),
3

otherwise it is ρ′ (N ) = π ′ (N ).

Proof. Suppose that π ′ (N ) = k for some integer k ≥ 2. Then

⎛Tk−1 Tk−2 + Tk−1 Tk ⎞ ⎛1 0 0⎞

⎜ ⎟ ⎜ ⎟
T = ⎜ Tk
k
Tk−1 + Tk Tk+1 ⎟ ≡⎜ 0⎟ (mod N ).
⎜ ⎟ ⎜0 1 ⎟
⎝Tk+1 Tk + Tk+1 Tk+2 ⎠ ⎝0 0 1⎠

Since B = T3 , it follows that Bk = T3k .

If 3 ∣ k, then Bk/3 = Tk and ρ′ (N ) = k3 . If 3 ∤ k, then ρ′ (N ) = k.

10 The
√
roots presented here are given in R. If given in a finite field, then i = −1.

19
Example 4.1. The Trisano period for N = 48 is 416, which is not divible by 3, so the period
of the Tribonacci cat map is the same. Meanwhile, π ′ (49) = 336 is divisible by 3 and therefore
ρ′ (49) = 112.

Figure 3: The graph shows the periods of the Tribonacci cat map for the first 10, 000 numbers.

The graphical illustration above has a clear pattern, where most periods seem to lie on invisible
parabolas with their symmetry lines somewhere near the y-axis. We will take a closer look at
them when discussing the upper bounds. But firstly, we will introduce the properties of the
period of the mapping for different values of N .

4.3.1 Periods of composite N

Due to Theorem 4.2, it is sufficient to present and prove the properties regarding the Trisano
period. The proofs can be efficiently adapted to the Tribonacci cat map. The results regarding
the Trisano period modulo a composite number are mainly taken from Wadill’s article [23].
They have been readjusted to fit the initial values and the generating matrix used in this thesis.
For the proof of Theorem 4.5, where N has a prime factorisation of two or more powers of
primes, we will first need the results from two lemmas.

Lemma 4.3 (Theorem 2 [23]). If Tk+1 ≡ Tk ≡ 0 (mod N ), then Tk−1

3
≡ Tk+2
3
≡ 1 (mod N ).

Proof. Using the equation of the determinant in (4.2), we have that

3
Tk−1 + Tk−2
2
Tk+1 + Tk2 Tk−3 − 2Tk−2 Tk−1 Tk − Tk−3 Tk−1 Tk+1 = 1.

From the hypothesis Tk+1 ≡ Tk ≡ 0 (mod N ), we have

2
Tk−2 Tk+1 ≡ Tk2 Tk−3 ≡ 2Tk−2 Tk−1 Tk ≡ Tk−3 Tk−1 Tk+1 ≡ 0 (mod N ),

20
which leads to
3
Tk−1 ≡1 (mod N ).

From the recurrence relation of the Tribonacci sequence, we have that

3
Tk−1 ≡ Tk+2
3
≡1 (mod N ).

Lemma 4.4 (Theorem 3 [23]). If k is the least positive integer such that Tk+1 ≡ Tk ≡ 0 (mod
N ), then, for any positive integer n

(a) Tnk+1 ≡ Tnk ≡ 0 (mod N );

(b) if Ts+1 ≡ Ts ≡ 0 (mod N ), then s = nk.

Proof. We will prove each case separately.

(a) Here, we will use proof by induction.

(i) For n = 1, the conclusion is immediate by the hypothesis Tk+1 ≡ Tk ≡ 0 (mod N ).
(ii) We assume that Tnk+1 ≡ Tnk ≡ 0 (mod N ) is true for a positive integer n. By (4.1) we
have that T(n+1)k+1 can be written as

T(n+1)k+1 = Tnk+(k+1) = Tnk Tk + (Tnk−1 + Tnk )Tk+1 + Tnk+1 Tk+2 .

From the hypothesis Tk+1 ≡ Tk ≡ 0 (mod N ), we have

Tnk Tk ≡ Tnk Tk+1 ≡ Tnk−1 Tk+1 ≡ 0 (mod N ).

From the assumption Tnk+1 ≡ Tnk ≡ 0 (mod N ), we also have Tnk+1 Tk+2 ≡ 0 (mod N ), which
implies that
Tnk+1 ≡ 0 (mod N ).

A similar argument can be used to show that Tnk ≡ 0 (mod N ).

(b) Let s be an integer such that Ts+1 ≡ Ts ≡ 0 (mod N ). Since k is the least positive integer
that fulfils Tk+1 ≡ Tk ≡ 0 (mod N ), we have that s ≥ k. If k does not divide s, then by the
division algorithm:
s = kt + r, 0<r<k for some integer t ≥ 0.

From (4.1), we have

Ts = Tkt+r = Tkt Tr−1 + (Tkt−1 + Tkt )Tr + Tkt+1 Tr+1 .

The results from (a) show that

Tkt Tr−1 ≡ Tkt Tr ≡ Tkt+1 Tr+1 ≡ 0 (mod N ).

3
From Lemma 4.3, together with the results in (a), we have that Tkt−1 ≡ 1 (mod N ). This
means that, in order to have Tkt−1 Tr ≡ 0 (mod N ), we must have Tr ≡ 0 (mod N ).
But r < k and k is the least positive integer such that Tk+1 ≡ Tk ≡ 0 (mod N ). This leads
to a contradiction. Hence, s = nk for any positive integer n.

21
This completes the proof of cases (a) and (b) and, consequently, the proof of the lemma.

1 p2 ⋯pm and ki
Theorem 4.5 (Theorem 4 [23]). If N has the prime factorisation N = pα1 α2 αm

denotes the Trisano period modulo piαi , then π ′ (N ) = lcm(ki ).

Proof. If π ′ (pα
i ) = ki then, from the recurrence relation of the Tribonacci sequence we have
i

⎧
⎪
⎪
⎪Tki +1 ≡ Tki ≡ 0 (mod pi )
αi
⎨
⎪
⎪
⎩Tki +2 ≡ Tk1 −1 ≡ 1 (mod pi ).
αi
⎪

From Lemma 4.4, it is also true that, for any positive integer n,

⎧
⎪
⎪
⎪Tnki +1 ≡ Tnki ≡ 0 (mod pi )
αi
⎨
⎪
⎪
⎩Tnki +2 ≡ Tnk1 −1 ≡ 1 (mod pi ).
αi
⎪

1 p2 ⋯pm , we can let s = lcm(ki ) and have

Since N = pα1 α2 αm

⎧
⎪
⎪
⎪Ts+1 ≡ Ts ≡ 0 (mod N )
⎨
⎪
⎪
⎩Ts+2 ≡ Ts−1 ≡ 1 (mod N ).
⎪

If π ′ (N ) = k it implies that

⎧
⎪
⎪
⎪Tk+1 ≡ Tk ≡ 0 (mod pi )
αi
⎨
⎪
⎪
⎩Tk+2 ≡ Tk−1 ≡ 1 (mod pi ).
αi
⎪

Once again, by Lemma 4.4, k = ni ki for all ki and an appropriate ni . By the definition of k, it
becomes clear that k = s = lcm(ki ) and π ′ (N ) = lcm(π ′ (pα
i )).
i

The next theorem concerns the Trisano period for a prime power. Like in the previous
theorem, the results are equivalent to those for the Pisano period. Even so, in order to prove
them, Lemmas 4.6 and 4.7 are necessary.
Lemma 4.6 (Theorem 6 [23]). If π ′ (N ) = k, then the following identities are true for N 2 and
any positive integer n:
(a) Tnk+2 ≡ Tk+2
n
(mod N 2 )

(b) Tnk−1 ≡ Tk−1

n
(mod N 2 )

(c) Tnk ≡ nTk−1

n−1
Tk (mod N 2 )

(d) Tnk+1 ≡ Tk+2

n
− nTk−1
n−1
Tk − Tk−1
n
(mod N 2 ).
Proof. We prove the lemma by considering each case separately.
(a) We will prove this case by induction.
(i) For n = 1, the conclusion is immediate.
(ii) Let us assume that Tnk+2 ≡ Tk+2
n
(mod N 2 ) is true for a positive integer n. By (4.1) we
can write T(n+1)k+2 as

T(n+1)k+2 = T(nk+1)+(k+1) = Tnk+1 Tk + (Tnk + Tnk+1 )Tk+1 + Tnk+2 Tk+2 .

22
Since π ′ (N ) = k, we can use the results from Lemma 4.4 where

Tk+1 ≡ Tnk+1 ≡ Tnk ≡ Tk ≡ 0 (mod N ).

These lead to
Tnk+1 Tk ≡ (Tnk + Tnk+1 )Tk+1 ≡ 0 (mod N 2 )

and to
T(n+1)k+2 ≡ Tnk+2 Tk+2 (mod N 2 ).

From the assumption, we have that Tnk+2 ≡ Tk+2

n
(mod N 2 ), giving us

T(n+1)k+2 ≡ Tk+2
n
Tk+2 ≡ Tk+2
n+1
(mod N 2 ).

(b) This case is also proved by induction.

(i) For n = 1, the conclusion is immediate.
(ii) Assume that Tnk−1 ≡ Tk−1
n
(mod N 2 ) is true for a positive integer n. By (4.1) we have
that T(n+1)k−1 is

T(n+1)k−1 = Tnk+(k−1) = Tnk Tk−2 + (Tnk−1 + Tnk )Tk−1 + Tnk+1 Tk

= Tnk (Tk−2 + Tk−1 ) + Tnk−1 Tk−1 + Tnk+1 Tk .

Since π ′ (N ) = k, we have that Tk−2 + Tk−1 ≡ 0 (mod N ) due to the recurrence relation of the
Tribonacci sequence. Along with the results from Lemma 4.4, we have

Tnk (Tk−2 + Tk−1 ) ≡ Tnk+1 Tk ≡ 0 (mod N 2 ),

leaving us
T(n+1)k−1 ≡ Tnk−1 Tk−1 (mod N 2 ).

From the assumption, we have Tnk−1 ≡ Tk−1

n
(mod N 2 ), which leads to

T(n+1)k−1 ≡ Tk−1
n
Tk−1 ≡ Tk−1
n+1
(mod N 2 ).

(c) Induction will be used here as well.

(i) For n = 1, the conclusion is immediate.
(ii) Assume Tnk ≡ nTk−1
n−1
Tk (mod N 2 ) is true for a positive integer n. We use (4.1) to write
T(n+1)k as
T(n+1)k = Tnk+k = Tnk Tk−1 + (Tnk−1 + Tnk )Tk + Tnk+1 Tk+1 .

Once again, we take advantage of the results from Lemma 4.4 and end up with

T(n+1)k ≡ Tnk Tk−1 + Tnk−1 Tk (mod N 2 ).

From the result in (b), we can rewrite the equation above as

T(n+1)k ≡ Tnk Tk−1 + Tk−1

n
Tk (mod N 2 ).

23
Finally, we use the assumption that Tnk ≡ nTk−1
n−1
Tk (mod N 2 ) in order to get the following:

T(n+1)k ≡ nTk−1
n−1
Tk Tk−1 + Tk−1
n
Tk ≡ (n + 1)Tk−1
n
Tk (mod N 2 ).

(d) From the defining recurrence relation of the Tribonacci sequence, we have that

Tnk+1 = Tnk+2 − Tnk − Tnk−1 .

By using the results from the previous cases, (a)-(c), we can rewrite the equation above into

Tnk+1 = Tk+2
n
− nTk−1
n−1
Tk − Tk−1
n
(mod N 2 ).

This proves case (d) and completes the proof of Lemma 4.6.

Lemma 4.7 (Theorem 7 [23]). If p is prime and π ′ (p) = k, then Tk+2

p p
≡ Tk−1 ≡ 1 (mod p2 ).

Proof. If Tk+2 ≡ 1 (mod p2 ), then the conclusion is immediate. Now, if Tk+2 ≢ 1 (mod p2 ) then
p
we can factorise Tk+2 − 1 as the following:

p p−1 p−2
Tk+2 − 1 = (Tk+2 − 1)(Tk+2 + Tk+2 + ⋯ + Tk+2 + 1).

Since π ′ (p) = k, it means that

Tk+2 ≡ 1 (mod p). (4.3)
s
Therefore, Tk+2 ≡ 1 (mod p) for any integer s. Hence, we have

p−1 p−2
Tk+2 + Tk+2 + ⋯ + Tk+2 + 1 ≡ 1 + 1 + ⋯ + 1 + 1 ≡ 0 (mod p). (4.4)
´¹¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¸ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¹ ¶
p summands

Using (4.3) and (4.4), we end up with

p p
Tk+2 −1≡0 ⇔ Tk+2 ≡1 (mod p2 ).

p
The equivalence Tk−1 ≡ 1 (mod p2 ) is proved in a similar manner.

Theorem 4.8 (Theorem 8 [23]). If p is prime and π ′ (p2 ) ≠ π ′ (p), then π ′ (pt ) = pt−1 π ′ (p), for
any positive integer t > 1.

Proof. We start the proof by showing that the theorem is true for t = 2. If we have that
π ′ (p) = k, then Tk ≡ I (mod p), where T is the generating matrix to the Tribonacci sequence
and I is the identity matrix. By Lemma 4.6 we have the following identities for n = p:
p
(a) Tpk+2 ≡ Tk+2 (mod p2 )
p
(b) Tpk−1 ≡ Tk−1 (mod p2 )
p−1
(c) Tpk ≡ pTk−1 Tk (mod p2 )
p p−1 p
(d) Tpk+1 ≡ Tk+2 − pTk−1 Tk − Tk−1 (mod p2 ).

24
From Lemma 4.7, together with identities (a) and (b), we have Tpk+2 ≡ Tpk−1 ≡ 1 (mod p2 ).
Since π ′ (p) = k, we have Tk ≡ 0 (mod p), which implies that

p−1
Tpk ≡ pTk−1 Tk ≡ 0 (mod p2 ) and by identity (d)
p−1
Tpk+1 ≡ −pTk−1 Tk ≡0 2
(mod p ).

Thus we end up with

⎧
⎪
⎪
⎪Tpk+1 ≡ Tpk ≡ 0 (mod p )
2
⎨
⎪
⎪
⎩Tpk+2 ≡ Tpk−1 ≡ 1 (mod p )
2
⎪

and we have that π ′ (p2 ) ∣ pk. Now, if π ′ (p2 ) = pk, there is no s, s < pk, that satisfies

⎧
⎪
⎪
⎪Ts+1 ≡ Ts ≡ 0 (mod p )
2
⎨
⎪
⎪
⎩Ts+2 ≡ Ts−1 ≡ 1 (mod p ).
2
⎪

Let us claim that such s exists. By Lemma 4.4, s = mk for some positive integer m as it is
implied that
⎧
⎪
⎪
⎪Ts+1 ≡ Ts ≡ 0 (mod p)
⎨
⎪
⎪
⎩Ts+2 ≡ Ts−1 ≡ 1 (mod p).
⎪

Then we have Ts ≡ Tmk ≡ (Tk )m ≡ Im ≡ I (mod p). Since π ′ (p2 ) ≠ π ′ (p), it follows that Tk ≢ I
(mod p2 ). At the same time we have (Tk )p ≡ (Tk )m ≡ I (mod p2 ). As p is prime, it means
that m ≥ p and s ≥ pk, which is a contradiction to our claim.
Hence π ′ (p2 ) = pπ ′ (p). To show that the theorem is true for t > 2, we use induction and
follow the same steps as above. The rest is omitted due to redundancy.

Remark. Similarly to the Pisano period for powers of prime numbers, there is no proof that
the hypothesis π ′ (p2 ) ≠ π ′ (p) is unnecessary. Meanwhile, no prime p that fulfils π ′ (p2 ) = π ′ (p)
has been found.

4.3.2 Periods of prime N

When N is a prime number p, the Trisano period is strongly related to the minimal polynomial
of the recurrence relation and its discriminant. Like with the minimal polynomial of the
Tribonacci cat map, the discriminant is −44.

Theorem 4.9. Assume p is prime and p ≠ 2, 11. The minimal polynomial of the Tribonacci
sequence is
PT (x) = x3 − x2 − x − 1.

(a) If ( 11
p
) = 1 and PT (x) is irreducible over Zp then π ′ (p) ∣ p2 + p + 1.

(b) If ( 11
p
) = 1 and PT (x) is reducible over Zp then π ′ (p) ∣ p − 1.

(c) If ( 11
p
) = −1 then π ′ (p) ∣ p2 − 1.

In order to prove Theorem 4.9, some specific results are needed. Theorem 4.10 is taken

25
from Carlitz’ article [5] and it is originally contained in a theorem of Stickelberger11 about the
relation between the discriminant of a polynomial with rational integer coefficients and the
number of irreducible polynomials modulo a prime. For more details regarding Theorem 4.10,
the reader is recommended to see [5]. Theorem 4.11 is about a property of the period of a
third order linear recurrence. The theorem is taken from Klaška and Skula’s article [13] and
its proof can be found both in Adams & Shanks’ work [1] and in Vince’s paper [22].

Proposition 4.10 (Theorem A [5]). Let D denote the discriminant of the polynomial

P (x) = xn + a1 xn−1 + ⋯ + an

where ai are rational integers. Let p be an odd prime, p ∤ D, and let

P (x) = P1 (x)⋯Ps (x) (mod p),

where Pi (x) are irreducible polynomials over Zp . Then the Legendre symbol is

D
( ) = (−1)n−s .
p

Proposition 4.11 (Theorem 1.1(i) [13]). Let P (x) = x3 + a1 x2 + a2 x + a3 be the minimal poly-
nomial of the generating matrix to the third order linear recurrence Xn = A1 Xn−1 + A2 Xn−2 +
A3 Xn−3 over the finite field Zp where p is prime. Let also K be the extension field of Zp
containing the distinct roots α1 , α2 , α3 to P (x). If Π(p) is the period of the recurrence re-
lation modulo p and ord(β) is the multiplicative order of the nonzero element β ∈ K in the
multiplicative subgroup K∗ of K, then

Π(p) = lcm(ord(α1 ), ord(α2 ), ord(α3 )).

With both the results above, we can proceed with proving Theorem 4.9. The proof is inspired
by Vince’s article on periods of linear recurrences [22].

Proof of Theorem 4.9. According to Theorem 4.10, we have ( D

p
) = (−1)3−s , where s is the
number of factors modulo p, a prime. When applying the properties of the Legendre symbol,
we get the following:

D −22 ⋅ 11 −1 22 11 p−1 11
( )=( ) = ( ) ( ) ( ) = (−1) 2 ( )
p p p p p p

(i) Let p ≡ 1 (mod 4), then for some positive integer n

D (4n+1)−1 11 p p
( ) = (−1) 2 ( ) = (−1)2n ( ) = ( ) .
p p 11 11
11 The original theorem can be found in Stickelberger’s article Über eine neue Eigenschaft der Diskriminanten

algebraischer Zahlkörper, published in ”Verhandlungen des ersten internationalen Mathematiker-Kongresses”

in Zürich, 1897. However, the article could not be found when this thesis was in progress and it is therefore
not a part of the reference list.

26
(ii) Let p ≡ 3 (mod 4), then for some positive integer n

D (4n+3)−1 11 p p
( ) = (−1) 2 ( ) = (−1)2n+1 [− ( )] = ( ) .
p p 11 11

So, when calculating the number of factors over Zp , it suffices to calculate ( 11

p
) in this case.
We complete the proof by considering the three different cases below.
(a) If ( 11
p
) = 1 and PT (x) is irreducible over Zp , then let K = Zp (α1 , α2 , α3 ) be the extension
field of Zp containing the roots of PT (x). The norm map N ∶ K∗ → Z∗p is therefore a surjective
homomorphism of the multiplicative subgroup of K to the multiplicative subgroup of Zp . Note
that both subgroups are cyclic. Since N (αi ) = (−1)3 (−1) = 1, where 3 is the degree of PT (x)
and −1 is its constant term, then αi is an element of the kernel, which is also cyclic. Then,
ord(αi ) ∣ ∣kerN ∣. The order of the kernel is

∣K∗ ∣ p3 − 1
∣kerN ∣ = = = p2 + p + 1.
∣Z∗p ∣ p−1

So we have that

ord(αi ) ∣ p2 + p + 1 and also lcm(ord(αi )) ∣ p2 + p + 1.

Hence, by Theorem 4.11, we have π ′ (p) ∣ p2 + p + 1.

(b) If ( 11
p
) = 1 and PT (x) has three factors, then they are all linear and the roots lie in Zp .
Once again, let Z∗p be the multiplicative subgroup of Zp . Since Z∗p is cyclic and αi ∈ Z∗p , we
have that ord(αi ) ∣ ∣Z∗p ∣. Furthermore

lcm(ord(αi )) ∣ ∣Z∗p ∣ = p − 1.

Thus, by Theorem 4.11, we have π ′ (p) ∣ p − 1.

(c) If ( 11
p
) = −1, then PT (x) has two factors, namely a linear factor and a quadratic factor
in Zp . Let K = Zp (α2 , α3 ) be the extension field containing the roots of the quadratic factor.
Since the root α1 of the linear factor lies already in Zp , it will automatically be an element in
K. Following the same reasoning for (b), we have

lcm(ord(αi )) ∣ ∣K∗ ∣ = p2 − 1.

Finally, by Theorem 4.11, we have π ′ (p) ∣ p2 − 1.

This completes the proof of cases (a)-(c) and hence the proof of the theorem.

The strong relation between the Trisano period and the period of the Tribonacci cat map
given by Theorem 4.2, allows us to summarise and adapt all the previous results into one
theorem.

Theorem 4.12. For every integer N ≥ 2, the period of the Tribonacci cat map modulo N
belongs to one of the following statements:

(i) If N is a prime p such that p ≠ 2, 11 and ( 11

p
) = 1, then ρ′ (p) ∣ p2 + p + 1 or ρ′ (p) ∣ p − 1.

27
 (ii) If N is a prime p such that p ≠ 2, 11 and ( 11
p
) = −1, then ρ′ (p) ∣ p2 − 1.

(iii) If N is a prime power such that N = pk , and if ρ′ (p2 ) ≠ ρ′ (p), then ρ′ (pk ) = pk−1 ρ′ (p).
′
1 p2 ⋯pn , then ρ (N ) =
(iv) If N is composite and has the prime factorisation N = pα 1 α2 αn

lcm(ρ′ (pα
i )).
i

Remark. Since the polynomial PT (x) shares the same discriminant as the minimal polynomial
to the Tribonacci cat map, PB (x) = x3 − 7x2 + 5x − 1, properties (i) and (ii) can be proven in
a similar manner as for the Trisano period. Regarding the hypothesis in property (iii), for the
first 10, 000 numbers, the only prime p with ρ′ (p2 ) = ρ′ (p) is 3, where ρ′ (9) = ρ′ (3) = 13.

Example 4.2. Below are a couple of examples comparing the Trisano period with its respective
Tribonacci cat map period modulo a prime.

(i) For p = 67, where ( 11

67
) = 1 and PT (x) is irreducible over Z67 . The periods are π ′ (67) =
1519 = ρ′ (67).

(ii) For p = 103, where ( 103

11
) = 1 and PT (x) has linear factors in Z103 . The periods are
π ′ (103) = 51 and ρ′ (103) = 17.

(iii) For p = 17, where ( 17

11
) = −1 and PT (x) has two factors in Z17 . The periods are π ′ (17) = 96
and ρ′ (17) = 32.

(iv) For p = 2, the periods are π ′ (2) = 4 = ρ′ (2).

(v) For p = 11, the periods are π ′ (11) = 110 = ρ′ (11).

4.3.3 Upper bounds

On the next page, there is a graph illustrating the periods of the Tribonacci cat map for all
primes less than 10,000. It is clear that the absolute upper bound for the prime numbers is
ρ′ (p) = p2 + p + 1. Interestingly, despite that one might first think that there should be periods
equal to ρ′ (p) = p2 − 1 for primes in group (ii) from Theorem 4.12, the greatest periods in this
group are ρ′ (p) = p 3−1 . This leads to Corollary 4.13.
2

Corollary 4.13. If N = p is a prime p, p ≠ 2, 11 and ( 11

p
) = −1, then

p2 − 1
ρ′ (p) ≤ .
3

Proof. Due to the strong relation to the Trisano period, it is enough to calculate π ′ (p). By
Theorem 4.2, it is true for any value of N that

⎧ π ′ (N )
′
⎪
⎪
⎪ 3 when 3 ∣ π ′ (N ),
ρ (N ) = ⎨
⎪
⎪ ′
⎩π (N )
⎪ otherwise.

(i) Let p ≡ 2 (mod 3), then for any positive integer n

p2 − 1 = (3n + 2)2 − 1 = 9n2 + 12n + 3 and 3 ∣ 9n2 + 12n + 3.

28
(ii) Let p ≡ 1 (mod 3), then for any positive integer n

p2 − 1 = (3n + 1)2 − 1 = 9n2 + 12n and 3 ∣ 9n2 + 12n.

And the proof is complete.

We will continue to further develop the results from Theorem 4.12 and introduce the next
corollary. This time, it concerns the periods of prime numbers, whose periods lie on the upper
curve, neatly visible in Figure 4.

Figure 4: The graph shows the periods of the Tribonacci cat map for all primes p, such that
2 ≤ p < 10, 000.

Corollary 4.14. If ρ′ (p) = p2 + p + 1 for a prime p > 3, then p ≡ 2 (mod 3).

Proof. Similar calculations to the proof to Corollary 4.13 show that p ≢ 1 (mod 3) when
ρ′ (p) = p2 + p + 1.

Remark. Observe that the converse of Corollary 4.14 is not true. There are primes p ≡ 2 (mod
3) with ρ′ (p) ≠ p2 + p + 1. Take, for example, p = 311 that has period ρ′ (311) = 310.
When it comes to finding an upper bound for all values of N , it can be interesting to look
at the ratios ρ′ (N )/N and ρ′ (N )/N 2 that are presented in their respective diagrams on the
next page. In Figure 5 (a), the patterns of the top periods created by the ratios give the false
illusion of them lying on perfect straight lines. It is confirmed in Figure 5 (b) that there is
not a single slope that fits all top periods. However, for the first 10,000 numbers, there is no
ratio in (b) that surpasses or is equal to 2. Furthermore, numerical calculations have showed
a negative trend of the ratio for higher numbers.

29
 ρ′ (N ) ρ′ (N )
(a) Plotted graf over N
. (b) Plotted graf over N2
.

Figure 5: The ratios of the Tribonacci cat map periods for 2 ≤ N ≤ 10, 000.

In Dyson & Falk [8], they calculate the upper bound of the original cat map by analysing
the factors of the period for any arbitrary N . In order to factorise the period, we must first
consider the factors of N . According to the Fundamental Theorem of Arithmetic, any number
N can be written as a product of powers of primes, like

N = 2α2 ⋅ 3α3 ⋅ 5α5 ⋅ 7α7 ⋅ 11α11 ⋅ . . . .

By Theorem 4.12 (iv), the period of such N is the least common multiple of the periods of the
prime powers in the factorisation of N . Before proceding with ρ′ (N ), we will divide the prime
numbers in sets according to their periods:
• p = 2, with ρ′ (2) = 4.
• p = 11, with ρ′ (11) = 110.

• Q = {q ∣ ρ′ (q) ≤ q 2 + q + 1}.

• R = {r ∣ ρ′ (r) ≤ r − 1}.
s2 −1
• S = {s ∣ ρ′ (s) ≤ 3
}.

Now, N can be rewritten as

⎛ ⎞
N = 2α2 ⋅ 11α11 ∏ q αq ( ∏ rαr ) ( ∏ sαs ) .
⎝q∈Q ⎠ r∈R s∈S

Applying all the results from Theorem 4.12, the period of the Tribonacci cat map modulo N
becomes

⎛ ⎞
ρ′ (N ) ≤ lcm 2α2 +1 , 11α11 (10), ∏ (q 2 + q + 1)q αq −1 , ∏ (r − 1)rαr −1 , ∏ 3−αs (s2 − 1)sαs −1 .
⎝ q∈Q r∈R s∈S ⎠
(4.5)
It is apparent in (4.5) that the periods of primes q ∈ Q are the greatest factors in ρ′ (N ). In
fact, the numerical calculations performed for 2 ≤ N ≤ 10, 000 have showed that the greatest
periods in the interval (see Figure 3 on page 20) belong to products of primes q ∈ Q, where q ≡ 2
(mod 3), and their multiples. The two top values for ρ′ (N )/N 2 in Figure 5 (b), for example,
belong to 345 and 690, whose prime factorisations are 3 ⋅ 5 ⋅ 23 and 2 ⋅ 3 ⋅ 5 ⋅ 23 respectively.

30
Nonetheless, it is not true that all products of primes qi ∈ Q, where q ≡ 2 (mod 3), generate
the greatest periods. Take for instance the number 2865 which is a product of 3, 5 and 191,
all of them elements in Q. The period of 191 is actually a product of the periods of 3 and
5, resulting in ρ′ (2865) = ρ′ (191). This means that the periods themselves must be relatively
prime.
It is not true either that all multiples of these products produce the greatest periods. Firstly,
the multiple cannot yield prime powers in the factorisation of N , i.e. 1725 = 345 ⋅ 5 = 3 ⋅ 52 ⋅ 23.
Recall that the period of a prime power q αq is at most q αq −1 greater than the period of q.
Secondly, after the periods of primes qi ∈ Q, the greatest factors in (4.5) are the periods of 2
and 11, although not simultaneously as they are not relatively prime. The periods of r ∈ R
and s ∈ S are comparably low.
The observations above, together with numerical calculations, allow us to come up with a
few conditions for the value N . In order for the periods modulo N to lie on the upper bound,
all the requirements below must be fulfilled. As noted above,

1. N = q1 q2 ⋯qn , or N = 2q1 q2 ⋯qn , or N = 11q1 q2 ⋯qn , for some qi ∈ Q and n ≥ 2;

2. qi ≡ 2 (mod 3);

3. all ρ′ (qi ) are pairwise relatively prime.

Taking into consideration the tendency of the ratios in Figure 5 (b), there is the possibility
of the existence of an asymptote as N → ∞. The highest ratios on the graph, for N = 345
and N = 690, are close to 1.87. As N increases, the top ratios approach 1.79. From this
information, we conjecture that no period of the Tribonacci cat map will be equal to or greater
than 1.88N 2 .

Conjecture 4.15. For any value of N ,

47 2
ρ′ (N ) < N .
25

4.4 Orbit lengths

Similarly to the DCM, for any value of N , the orbit lengths of the points in the N 3 -space are
divisors of ρ′ (N ). However, for some values of N , the origin is not the only fixed point. Another
remarkable difference between the original discrete mapping and the three dimensional one is
that, in the latter, the orbit lengths of the non-trivial points are not always equal to ρ′ (N )
when N is prime. The results presented in this subsection are based on empirical investigations.

4.4.1 Orbit lengths of prime N

As with periods for prime values of N, the orbit lengths depend on the factorisation of the
minimal polynomial PB (x) = x3 − 7x2 + 5x − 1 in Zp . The study of the orbits for prime N can
therefore be conducted according to their respective sets:

• p = 2 and p = 11.

31
Because both 2 and 11 are present in the discriminant, some of the roots have multiplicity
greater than 1. In fact, the polynomial PB (x) has a triple root in Z2 while it has a double
and a single root in Z11 . The orbit lengths consist of the multiplicative orders of the roots and
their multiples.

p Orbit length Number of disjoint orbits Roots αi in Zp ordp (αi )

2 1 2 α1,2,3 = 1 ord2 (1) = 1
2 1
4 1
11 1 1
5 2 α1 = 3 ord11 (3) = 5
10 11 α2,3 = 2 ord11 (2) = 10
110 11

Table 1: Since the triple root in Z2 has multiplicative order 1, there is a non-trivial point in
the mapping for N = 2 with orbit length 1.

• Q = {q ∣ ρ′ (q) ≤ q 2 + q + 1}.

For primes q ∈ Q, the polynomial PB (x) is irreducible over Zq . When this happens, the
Tribonacci cat map behaves similarly to the DCM and the orbit length of all non-trivial points
is the same as the period of the map. The table below presents the orbits for three prime
numbers q.

q Orbit length Number of disjoint orbits Roots αi in Zq ordq (αi )

3 1 1 None -
13 2

5 1 1 None -
31 4

67 1 1 None -
1519 198

Table 2: Because the period for N = q is either ρ′ (q) = q 2 + q + 1 or one of its divisors, it will
always be an odd number. There is no restriction as whether the period is a prime number
itself or not. While N = 3 and N = 5 have prime numbers as their periods, N = 67 has a
composite number, 1519 = 72 ⋅ 31.

32
 • R = {r ∣ ρ′ (r) ≤ r − 1}.

For primes r ∈ R, the polynomial PB (x) is reducible over Zr and has three linear factors.
The implication is that the orbit lengths for all non-trivial points are equal to any of the
multiplicative orders of the roots of PB (x) in Zr . Below follow the orbit lengths of three prime
numbers r.

r Orbit length Number of disjoint orbits Roots αi in Zr ordr (αi )

1 1 α1 = 31 ord47 (31) = 46
47 23 2 α2 = 25 ord47 (25) = 23
46 2256 α3 = 45 ord47 (45) = 46

1 1 α1 = 39 ord53 (39) = 52
53 13 4 α2 = 24 ord53 (24) = 13
52 2862 α3 = 50 ord53 (50) = 52

1 1 α1 = 8 ord103 (8) = 17
103 17 64278 α2 = 9 ord103 (9) = 17
α3 = 93 ord103 (93) = 17

Table 3: Note that, when all roots have the same multiplicative order, as for r = 103, the map
exhibits a similar behaviour to when N = q.

s2 −1
• S = {s ∣ ρ′ (s) ≤ 3
}.

For primes s ∈ S, the polynomial PB (x) has only one linear factor in Zs . The result is that the
orbit lengths for all non-trivial points are either equal to the multiplicative order of the root,
or to a multiple of the root, which is the period of the map. From the calculations realised
in this thesis, there is not enough material to predict the period of the mapping once the
multiplicative order of the root is known, or vice versa.

s Orbit length Number of disjoint orbits Roots αi in Zs ords (αi )

7 1 1
2 3 α=6 ord7 (6) = 2
16 21
13 1 1
4 3 α=5 ord13 (5) = 4
56 39
83 1 1
41 2 α = 48 ord83 (48) = 41
287 1992

Table 4: For the primes s = 7 and s = 13, the period of the mapping is equal to the multiplicative
order of the root multiplied by s + 1, where 16 = 2 ⋅ 8 and 56 = 4 ⋅ 14. This is not true for all
primes s, as in the case for s = 83, where 287 = 41 ⋅ 7.

33
4.4.2 Orbit lengths of composite N

When N is composite, the patterns behind the orbit lengths are no longer related to the set
in which the prime factors belong. Instead, the behaviour depends on whether N is a prime
power or a product of primes. Regardless of which, once the orbit lengths of the prime factors
are known, all orbit lengths of N can be predicted.
For instance, the orbit lengths of N = p2 include all orbit lengths of N = p and their
respective products with p. This pattern repeats itself for any power N = pn . When the
products are already existing lengths in N = pn , then no new orbit lengths related to these are
added in N = pn+1 . To illustrate this, take, for example, N = 2 with orbit lengths 1, 2 and 4
(see Table 5). As 2 is already 1 ⋅ 2 and 4 is 2 ⋅ 2, the only new orbit length for N = 22 is 4 ⋅ 2 = 8.
This follows for all powers of 2.

N Orbit lengths
2 1 2 4
22 1 2 4 8
23 1 2 4 8 16
24 1 2 4 8 16 32
⋯ ⋯

Table 5: Every new power of 2, i.e. 2n+1 , has all the orbit lengths of the previous power, i.e.
2n , together with the product between the greatest orbit length of 2n and 2.

In the case when N = 11 (see Table 6), it is easier to see that the multiples of the orbit lengths
in N = 11 appear in N = 112 , along with the original orbit lengths. Even in this case, however,
the orbit length 110 is already the product of the orbit length 10 and the prime 11. So only
the orbit lengths 5 and 110 gain their products with 11 in N = 112 . The procedure is repeated
for all powers of 11.

Period Orbit lengths

11 5 10 110
112 5 10 55 110 1210
113 5 10 55 110 605 1210 13310
114 5 10 55 110 605 1210 6655 13310 146410
⋯ ⋯

Table 6: It is visible that the orbit lengths of 11n+1 include all the lengths of 11n and their
respective products with 11.

34
Examples of primes from the other sets are shown in Table 7. They all follow the same pattern
of orbit lengths as presented earlier. The only exception found in the interval 0 < N ≤ 10, 000
is N = 32 , which has the same orbit length as N = 3. Thereafter, the powers of 3 follow the
same patterns as any other prime power.

N Orbit lengths
7 2 16
72 2 14 16 112
73 2 14 16 98 112 784
74 2 14 16 98 112 686 784 5488
⋯ ⋯
53 13 52
532 13 52 689 2756
533 13 52 689 2756 36517 146068
⋯ ⋯
3 13
32 13
33 13 39
34 13 39 117
⋯ ⋯
5 31
52 31 155
53 31 155 775
54 31 155 775 3875
⋯ ⋯

Table 7: In all cases, it is visible that N = pn+1 contains the same orbit lengths as N = pn plus
their respective products with p.

When N is a product of primes, it will inherit all orbit lengths of the non-trivial points from its
factors. Furthermore, it will also have all possible least common multiples of the orbit lengths
of the different factors. This is similar to the period of N being the least common multiple of
the periods of all its factors. Tables 8 and 9 present the orbit lengths of composite numbers
where at least one factor is a prime power, while tables 10 and 11 have square-free values of N .
Each factor and its orbit lengths are shaded with a specific colour to better illustrate which
orbit lengths of N are derived from which factor. When the same orbit length is shared by
two factors, it is shaded with both colours when presented for N .

35
 N Orbit lengths

52 31 155
19 6 120

475 6 31 120 155 186 930 3720

Table 8: The shaded orbit lengths in N = 475 have the same colour as the factor from which they
derive. The non-shaded orbit lengths are the least common multiples of the lengths between the
factors. These are 186 = lcm(6, 31), 930 = lcm(6, 155) and 3720 = lcm(31, 120) = lcm(120, 155).

N Orbit lengths
23 1 2 4 8 16
3 13
17 16 32

408 1 2 4 8 13 16 26 32 52 104 208 416

Table 9: Note that the orbit length 16 appears in both N = 23 and N = 17. The new orbit
lengths of N = 408 are 26 = lcm(2, 13); 52 = lcm(4, 13); 104 = lcm(8, 13); 208 = lcm(13, 16); and
416 = lcm(13, 16, 32).

When two or more factors of N share orbit lengths, the number of new lengths in N is less
than when all orbit lengths are unique. Similarly, when two or more factors have orbit lengths
with greatest common divisor (gcd) greater than 1, there are fewer new lengths in N than
when the factor’s orbit lengths are relatively prime. Take for instance the examples in Tables
10 and 11. The total number of orbit lengths among their factors is the same. However, since
no length appears in two or more factors of N = 66 and only a few have gcd greater than 1,
N = 66 ends up having many more orbits than N = 182. The latter has two orbit lengths that
appear in more than one factor, and almost all lengths have gcd greater than 1.

N Orbit lengths
2 1 2 4
7 2 16
13 4 56

182 1 2 4 16 56 112

Table 10: The orbit length 2 appears in both N = 2 and N = 7, and the orbit length 4 appears
in both N = 2 and N = 13. Besides, apart from the orbit length 1, all the others have greatest
common divisor greater than 1. Consequently, there is only one new orbit length in the product
N = 182, which is the least common multiple of all three periods.

36
 N Orbits lengths

2 1 2 4
3 13
11 5 10 110

66 1 2 4 5 10 13 20 26 52 65 110 130 220 260 1430 2860

Table 11: Apart from the even orbit lengths in N = 2 and N = 11, where their greatest common
divisor is 2, all the other lengths have 1 as their greatest common divisor.This results in N = 66
having relatively more new orbit lengths than the previous examples.

The three examples where N is even have the orbit length 1 for non-trivial points. This is
actually true for all even values of N . In fact, there is only one non-trivial point that is fixed
when N is even, and that point is ( N2 , N2 , N2 ). This is summarized in the following theorem.

Theorem 4.16. When N is even, the Tribonacci cat map has exactly two fixed points: the
trivial point (0, 0, 0) and the non-trivial point ( N2 , N2 , N2 ).

Proof. Let B be the Tribonacci cat matrix and let N be even. The point X = (x1 , x2 , x3 ) is
fixed when
BX ≡ X (mod N ). (4.6)

Rearranging (4.6), we get

(B − I)X ≡ 0 (mod N ), (4.7)

⎛0 1 1⎞ ⎛x1 ⎞ ⎛0⎞
⎜ ⎟⎜ ⎟ ⎜ ⎟
⎜1 1 2⎟ ⎜ ⎟≡⎜ ⎟ (mod N ). (4.8)
⎜ ⎟ ⎜x2 ⎟ ⎜0⎟
⎝2 3 3 ⎝x3 ⎠ ⎝0⎠
⎠

where I is the identity matrix. We can rewrite (4.8) as a system of equations modulo N :

⎧
⎪ x2 + x3 ≡ 0 (mod N )
⎪
⎪
⎪
⎪
⎨ x1 + x2 + 2x3 ≡ 0 (mod N ) (4.9)
⎪
⎪
⎪
⎪
⎪
⎩2x1 + 3x2 + 3x3 ≡ 0 (mod N )

The second equation in (4.9) can be rewritten as

x1 ≡ −x2 − 2x3 (mod N )

and inserted in the third equation of the system in (4.9). We get:

x2 − x3 ≡ 0 (mod N ). (4.10)

If we take (4.10) and the first equation in (4.9), we end up with a new and more simplified

37
system of equations modulo N :

⎧
⎪
⎪
⎪x2 + x3 ≡ 0 (mod N )
⎨ (4.11)
⎪
⎪x2 − x3 ≡ 0 (mod N ).
⎪
⎩

We repeat the same procedure of rewriting the second equation in (4.11) so that x2 is the only
term on the left hand side, and inserting the right hand side into the first equation in (4.11).
Finally, we end up with the modular homogeneous equation

2x3 ≡ 0 (mod N ). (4.12)

Since gcd(2, N ) = 2, the equation in (4.12) has exactly two distinct solutions. This implies
that the system of equations in (4.9) has two solutions and, consequently, there are two points
X1 and X2 that fulfil the equation in (4.6).
One of the points is the trivial point X1 = (0, 0, 0). The other one is X2 = ( N2 , N2 , N2 ), as

⎛0 1 1⎞ ⎛ N2 ⎞ ⎛ 3N
2 ⎞ ⎛2⎞
N

⎜ ⎟ ⎜ N ⎟ ⎜ 5N ⎟ ⎜ N ⎟
⎜1 1 2⎟ ⎜ ⎟≡⎜ ⎟≡⎜ ⎟ (mod N ).
⎜ ⎟⎜ 2 ⎟ ⎜ 2 ⎟ ⎜ 2 ⎟
⎝2 3 3⎠ ⎝ N ⎠ ⎝ 9N ⎠ ⎝ N ⎠
2 2 2

And the proof is complete.

The results from Theorem 4.16 lead naturally to Corollary 4.17.

Corollary 4.17. When N is odd, the Tribonnaci cat map has only one fixed point, the trivial
point (0, 0, 0).

Proof. If N is composite, then its orbit lengths are derived from the orbit lengths of its prime
factors and their least common multiples. For this reason, it suffices to prove for when N is
an odd prime.
The procedure is similar to the proof of Theorem 4.16, leading to the same equation as
in (4.12):
2x3 ≡ 0 (mod N ).

Since gdc(2, N ) = 1, the equation has only one solution, the trivial point (0, 0, 0).

4.5 Generalised Tribonacci cat map

Like with the original DCM, the Tribonacci cat map can also be generalised. For any integers
a, b ∈ {0, 1, ⋯, N − 2}, a general form of the mapping is

⎛xt ⎞ ⎛ 1 1 1 ⎞ ⎛xt−1 ⎞
⎜ ⎟ ⎜ ⎟⎜ ⎟
⎜ yt ⎟ ≡ ⎜ a a+1 a + 1⎟ ⎜ ⎟ (mod N ). (4.13)
⎜ ⎟ ⎜ ⎟ ⎜ yt−1 ⎟
⎝ zt ⎠ ⎝a + 1 b b + 1 ⎠ ⎝ zt−1 ⎠

A simple calculation shows that the determinant of the generalised matrix is always equal to 1,
independently of the choices for a and b. As with the original Tribonacci cat map, this mapping

38
is volume preserving and periodic. But even though the determinant remains the same, the
minimal polynomial and its discriminant are different from the original. Depending on the
choices for a and b, the same value of N can have different periods. Example 4.3 illustrates a
couple of these differences.

Example 4.3. In the original Tribonacci cat map, the period modulo N = 31 is 331.

(a) For a = 3 and b = 25, the discriminant is 517712 = 2 ⋅ 3 ⋅ 21563 and the period is 960.

(b) For a = 3 and b = 7, the discriminant is 4064 = 25 ⋅ 127 and the period is 192.

(c) For a = 11 and b = 4, the discriminant is −10611 = −34 ⋅ 131 and the period is 320.

A further investigation in the generalised Tribonacci cat map may reveal how the choices
of a and b interfere in the discriminant and, as a consequence, in the periods of the map. Like
in Bao’s and Chen’s studies on the generalised DCM ([2] and [6] respectively), there can be
some interesting general properties of the mapping in (4.13). In the next section, we use the
generalised Tribonacci cat map to encrypt the RGB-colours of an image.

39
5 Applications
As an alternative to the three dimensional DCM, the Tribonacci cat map can be used for the
same purposes, such as encryption and watermarking. The purpose of this section is merely to
illustrate and exemplify how this mapping can be used in 3D image encryption and in colour
encryption. In subsection 5.1, we use two 3D images and encrypt them using the proposed cat
map. We comment on the appearances of ghosts and miniatures, and discuss the impact of
the choice of N on the iterations. In subsection 5.2, we try colour encryption on a 2D image
using both the original Tribonacci cat map and a generalised form of the map. We compare
the outcomes from the two mappings, and discuss briefly on the role of the discriminant in the
formation of chaotic colour schemes.

5.1 3D image encryption

From the definition of the Tribonacci cat map, the pixels of the 3D image are shuffled within
the domain, creating chaotic patterns, before eventually returning to their original places
simultaneously. In the two dimensional DCM, it is known that ghosts and miniatures of the
image can appear in the middle of the process for certain values of N . These values have been
studied by Behrends and presented in his article [3]. For security reasons, such values are not
ideal for 2D image encryption.
After a few experiments with the Tribonacci cat map, it became clear that even this map-
ping creates ghosts when encrypting 3D images. However, the appearance of miniatures could
neither be confirmed nor dismissed based on the experiments performed for this thesis because
possible miniatures were difficult to distinguish. While there are studies about these phenom-
ena in the DCM (once again we refer to Behrends’ work [3]), there is still much left to learn
about them in the Tribonacci cat map.

(a) Original images (b) t = 1

(c) t = 11 (d) t = 114

Figure 6: N = 67 and ρ′ (67) = 1519.

40
 (a) t = 506 (b) t = 620

(c) t = 1013 (d) t = 1519

Figure 7: N = 67 and ρ′ (67) = 1519 (cont.).

For a better illustration of the 3D image encryption, two different types of three dimensional
images were used in the experiments. One consists of several layers of two dimensional images
while the other is an MR-image in three dimensions. When exposed to the mapping, they
present similar behaviours at t iterations.
The choice of N = 67 lies on the fact that it is a prime number from the set Q, where all
orbit lengths of non-trivial points are equal to the period. The expectation, based on results
from the original DCM, was that all iterations would present a chaotic image until the very
last one. From Figure 7, it is clear that it was not the case. In fact, at approximately one third
of the period, the original image was completely retrieved but in a different position. Later, at
approximately two thirds of the period, ghosts of the original image appeared. As mentioned
earlier, miniatures were difficult to identify in both cases.
The same behaviour was noted for other prime values of N , not necessarily from the same
set. The original image resurfaced in a different position after one third of the period, and
then ghosts emerged after two thirds of the period. Even for some composite values of N the
map presented the same behaviour. Meanwhile, when the period was a small number, like for
N = 163 where ρ′ (163) = 54, none of these phenomena took place. Further investigations are
however required before any conclusions can be made.
The Tribonacci cat map is clearly not very secure if used alone. From the size of the image,
the period is easily calculated. Even if the period is unknown, just by applying the mapping
on the image, the original picture will be eventually retrieved. A solution would be to use a
generalised form of the map and keep the values of a and b secret. Nevertheless, in order to
increase the security and secrecy of the encrypted image, the Tribonacci cat map should be
used as one of several steps in the encryption process.

41
5.2 Colour encryption
For the colour encryption, we used the RGB-values from 0 to 255. Since each pixel consists
of a vector with three entries, (Red, Green, Blue), the Tribonacci cat map could be used to
change their values and therefore change the colours inside the picture. For our experiments, a
two dimensional image was used for a better visualisation of the changes (see Figures 8 and 9).
When encrypting colours, the size of the picture is no longer relevant. Instead, all calcu-
lations are performed modulo 256. This means that the period of the mapping will always
be 512, regardless of how big or little the picture is. From a security point of view, this is
far from ideal. One way to circumvent this is by using a generalised Tribonacci cat map. By
choosing appropriate values of a and b, the period can become greater than 512. By keeping
them secret, it increases the difficulty in retrieving the original picture by brute force.

Using the original Tribonacci cat map

(a) Original image (b) t = 64 (c) t = 85 (d) t = 170

(e) t = 171 (f) t = 341 (g) t = 484 (h) t = 512

Figure 8: After 512 iterations, the colours of the image are restored.

Even though the pixels remain on the same positions all the time, by simply changing the values
of their colours, the image becomes chaotic and unrecognisable. When using the Tribonacci
cat map, however, the image resurfaces many times during the iterations but with different
colour schemes, as illustrated in Figure 8. A hypothesis would be that this is a consequence of
N = 256 being a power of 2, one of the primes in the discriminant of the minimal polynomial.
In order to confirm or reject this hypothesis, as well as to find more information about this
pattern, more research is clearly needed.
A few iterations from the encryption process with the generalised Tribonacci cat map are
seen in Figure 9. In this investigation, the generalised mapping used for comparison had the
parameters a = 10 and b = 5, and the period 896. The choice of the values for a and b lies
on the fact that the period is greater than 512. Unlike with the original Tribonacci cat map,
the image does not reappear as often and, when it does, it is not as easily recognisable. In
Figure 9, the images (d) and (g) show hints of the original picture, but their colour schemes
are not as defined as in Figure 8. Overall, the image becomes more chaotic than in the original

42
 Using a generalised Tribonacci cat map

(a) Original image (b) t = 104 (c) t = 247 (d) t = 448

(e) t = 587 (f) t = 672 (g) t = 885 (h) t = 896

Figure 9: For a = 10 and b = 5, the period becomes 896.

mapping.
More study on the generalised Tribonacci cat map is evidently needed. Firstly, to clarify how
much more secure it is in relation to the original mapping when it comes to colour encryption.
Secondly, to identify possible strong and weak relations (from a security point of view) between
the parameters a and b. It is equally important to analyse how the values of a and b affect the
period.
Colour encryption, as presented here, can also be realised in 3D images as long as their
colour values are given in RGB-vectors. Like with the 3D image encryption, using either of the
mappings for colour encryption should be but one of several steps in the encryption process in
order to increase the security of the information.

43
6 Discussion
Based on the generating matrix to the Tribonacci sequence, the Tribonacci cat map is a three
dimensional discrete chaotic dynamical system defined by the following mapping:

⎛xt ⎞ ⎛1 1 1⎞ ⎛xt−1 ⎞
⎜ ⎟ ⎜ ⎟⎜ ⎟
⎜ y t ⎟ ≡ ⎜1 2 2⎟ ⎜ ⎟ (mod N ),
⎜ ⎟ ⎜ ⎟ ⎜ yt−1 ⎟
⎝ zt ⎠ ⎝2 3 4⎠ ⎝ zt−1 ⎠

where t ≥ 1 and (x, y, z) are the coordinates of a point in an N 3 space. Like its predecessor,
Arnold’s discrete cat map, it has proved itself of having an interesting mathematical structure
and of being quite useful for different kinds of image based encryption. Here, we will discuss
the results presented in the previous sections and propose future investigations on the subject.

6.1 Tribonacci cat map

As with the two dimensional discrete mapping, there is a strong relation between the period of
the Tribonacci cat map, defined by ρ′ (N ), and the period of the Tribonacci sequence, defined
by π ′ (N ) and also known as the Trisano period. This relation was proved in Theorem 4.2,
where it was also made clear that the period of the map is either equal to the whole or a third
of the Trisano period for the same N . So, in the analysis of the periods of the Tribonacci cat
map, we followed the steps from previous studies on the original Arnold’s cat map and focused
on proving the properties of the Trisano period.
The main result of this thesis is the proof of Theorem 4.9, which states the properties of
the Trisano periods for prime values of N . According to the theorem, the period is determined
by the factorisation of the minimal polynomial of the generating Tribonacci matrix modulo N .
Whether N is a quadratic residue of the discriminant of the polynomial or not is helpful in
the determination of the number of irreducible factors modulo N . In fact, the proof of the
theorem can be easily adapted to the Tribonacci cat map because of shared properties between
the minimal polynomials, like the discriminant.
When N is a prime power, i.e. N = pα where p is prime and α is a natural number greater
than 1, then Theorem 4.8 claims that its Trisano period is equal to pα−1 π ′ (p). Meanwhile,
when N is a product of primes, the period is, according to Theorem 4.5, the least common
multiple of the periods of its prime factors. Both theorems, together with Theorem 4.9, have
their results translated to the Tribonacci cat map in Theorem 4.12.
In the study of upper bounds, we divided the prime numbers into sets according to their
periods and their appearance in the discriminant, as in the case for p = 2, 11. With straight-
forward modular calculations, we managed to establish upper bounds to the periods of two
of these sets in Corollaries 4.13 and 4.14. In order to identify a possible upper bound for all
values of N , we analysed the ratios of the periods of the Tribonacci cat map for 2 ≤ N ≤ 10, 000.
From the gathered data, we noticed that the highest ratios belonged to the composite numbers
345 and 690. Apart from these two, it appeared to be an overall negative correlation between
the values of N and the ratios ρ′ (N )/N 2 . Based on these observations, Conjecture 4.15 was
proposed as a limit to the upper bound. Alongside with these observations, we listed a few
requirements that must be fulfilled in order for the period to lie on the upper bound for all

44
values of N .
Besides the connection between the map and the recurrence sequence, there is another
resemblance to the original Arnold’s cat map. It is the fact that the orbit lengths in the
Tribonacci cat map are divisors of the periods. However, the resemblance stops there. The orbit
lengths of non-trivial points depend on the factorisation of the minimal polynomial modulo
N when N is a prime other than 2 and 11. When the polynomial has linear factors, the
orbit lengths are equal to the multiplicative orders of the roots. When the polynomial has
a quadratic factor, then the orbit lenghts consist of the multiplicative order of the root in
the linear factor and its multiple. Because of the limitations in the investigation, there are
inconclusive results regarding the prediction of the multiple. In the case when the polynomial
is irreducible modulo N , there is only one orbit length for non-trivial points, and it is the same
as the period.
It is easier to predict the orbit lengths for composite values of N once we know the orbit
lengths of the factors. Based on empirical investigations, when N is a prime power, i.e. N = pα ,
the orbit lengths are composed of the orbit lengths of pα−1 and their respective multiples with p.
When N is a product of different primes, i.e. N = pα
1 p2 ⋯pm , then the orbit lengths consist
1 α2 αm

of the orbit lengths of each prime factor and the least common multiples of the lengths. From
the observations, we could see that when N is even, there are two disjoint orbits with length
1. Theorem 4.16 asserts that this is true for all even values of N , and states that the origin
and the point ( N2 , N2 , N2 ) are the only ones with orbit length equal to 1. As a consequence of
the theorem, Corollary 4.17 proves that the origin is the only point with orbit length 1 when
N is odd.

6.2 Applications
The main purpose of this thesis was to investigate the Tribonacci cat map and its mathematical
properties. Still, a couple of examples in encryption were demonstrated in order to show the
mapping’s practical applications. Nonetheless, these examples are not enough to generalise the
results presented here. The limitations regarding the hardware affected the choice of values of
N , as well as hampered any detailed visualization of single iterations. The three dimensional
equivalent of ghosts in Arnold’s cat map were perceived in the Tribonacci cat map, but we
were unable to identify the appearance of miniatures because of the inadequate image quality.
Two 3D images of equal dimensions and different characteristics were used for image en-
cryption. One consisted of multiple layers of 2D images and the other was an original 3D
graphic. Inspired by the results on encryption using Arnold’s discrete cat map, a prime num-
ber from the set where all orbit lengths of non-trivial numbers are equal to the period was
chosen. The expectation was to see chaotic images for all iterations before the last one. How-
ever, after approximately one third of the period, both images were completely retrieved but
in a different position than the one from the beginning. At approximately two thirds of the
period, ghosts covered the entire images. The same behaviour was observed for primes from
the other sets. Only when the period of a prime N was relatively small did the images become
chaotic until the end.
For colour encryption, a 2D image was used. Since the value of N was fixed to 256,
the number of RGB-values for every pixel, the results from the Tribonacci cat map were

45
compared with those from a generalised form of the map. By choosing appropriate values to
the parameters of the generalised map, its period became greater than ρ′ (256) = 512. The
outcomes of the encryption showed that, besides having a greater period, the iterations of the
generalised map turned out to be more chaotic than those from the original Tribonacci cat
map. In many iterations of the original map, the image was distinguishable even if with a
different colour scheme. A hypothesis is that the chaotic behaviour in colour encryption is
strongly related to the connection between the discriminant and the value of N . By changing
the parameters of the matrix, the discriminant is also changed, resulting in different properties
of the periods and orbit lengths for the same value of N .

6.3 Future investigations

For several decades, researchers have studied Arnold’s cat map, fascinated by its mathematical
properties and practical applications. The Tribonacci cat map is equally fascinating and may
also require many years before being completely understood. More data is needed in order to
prove or refute Conjecture 4.15 about the map’s upper bound. It can also be of interest to
investigate other possible upper bounds for different values of composite N . The limitations
in this thesis have also opened the doors to further investigations on orbit lengths. More study
is needed on the orbit lengths when N is a prime from the set where the minimal polynomial
has only one linear factor modulo N .
In this thesis, there was a short introduction to a generalised Tribonacci cat map and
its application in encryption. Clearly, more research is needed on the subject, especially in
consideration to its role in cryptography and cryptanalysis. The choice of parameters and their
influence over the chaotic behaviour of the map can be relevant for future encryptions and
attacks on encrypted images. In general, further investigations on encryption with Tribonacci
cat map are essential in a world where more 3D graphics are being used and security of
information is as important as ever.

46
References
[1] Adams W. & Shanks D. (1982). Strong primality tests that are not sufficient. Mathematics
of Computation. Vol 39.159 pp 255-300. American Mathematica Society.

[2] Bao J. & Yang Q. (2012). Period of the discrete Arnold cat map and general cat map.
Nonlinear Dynamics. Vol 70.2 pp 1365-1375. Springer Science+Business Media.

[3] Behrends E. (1998). The ghosts of the cat. Ergodic Theory and Dynamical Systems. Vol
18 pp 321 - 330. Cambridge University Press.

[4] Brindha M. (2017). Periodicity analysis of Arnold Cat Map and its application to im-
age encryption. 2017 International Conference on Inventive Computing and Informatics
(ICICI). Pp 495 - 498. IEEE.

[5] Carlitz L. (1953). A theorem of Stickelberger. Mathematica Scandinavica. Vol 1 pp 82-84.

Royal Danish Library.

[6] Chen F. et al. (2014). Period distribution of generalized discrete Arnold cat map. Theo-
retical Computer Science. Vol 552 pp 13 - 25. Elsevier.

[7] Choi U. S. et al. (2019). Color Medical Image Encryption Using 3D Chaotic Cat Map
and NCA. 2019 10th IFIP International Conference on New Technologies, Mobility and
Security (NTMS). Pp 1 - 5. IEEE.

[8] Dyson F. J. & Falk H. (1992). Period of a discrete cat mapping. The American Mathe-
matical Monthly. Vol 99.7 pp 605 - 614. Mathematical Association of America.

[9] Fransson J. (2013). Generalized Fibonacci Series Considered Modulo n. (Bachelor thesis).
Linnæus University, Växjö, Sweden.

[10] Ganesan K. & Murali K. (2014). Image encryption using eight dimensional chaotic cat
map. The European Physical Journal: Special Topics. Vol 223 pp 1611-1622. EDP Sciences,
Springer-Verlag.

[11] Gaspari G. (1994). The Arnold cat map on prime lattices. Physica D. Vol 73.4 pp 352-372.
Elsevier.

[12] Hungerford T. W. (2014). Abstract Algebra. Third Edition. Brooks/Cole, Cengage Learn-
ing.

[13] Klaška J. & Skula L. (2010). Periods of the Tribonacci sequence modulo a prime p ≡ 1
(mod 3). Fibonacci Quarterly. Vol 48.3 pp 228-235. Fibonacci Association.

[14] Mishra M. et al. (2012). High Security Image Steganography with Modified Arnold’s Cat
Map. International Journal of Computer Applications. Vol 37.9 pp 16 - 20. Foundation of
Computer Science.

[15] Nance J. (2011). Periods of the discretized Arnold’s cat mapping and its extension to
n-dimensions. Cornell University Library.
http://arxiv.org/abs/1111.2984v1 (downloaded 2019-12-08).

47
[16] Peng W. (2020). ABC implies there are infinitely many non-Fibonacci-Wieferich primes.
Journal of Number Theory. Vol 212 pp 354-375. Elsevier.

[17] PrimeGrid. (2015). http://www.primegrid.com/forumthread.php?id=3008&nowrap=

true#45946 (visited 2020-07-03).

[18] Raj B. et al. (2019). A new transformation of 3D models using chaotic encryption based
on Arnold cat map. In: Barolli L., Xhafa F., Khan Z., Odhabi H. (eds) Advances in
Internet, Data and Web Technologies. EIDWT 2019. Lecture Notes on Data Engineering
and Communications Technologies. Vol 29 pp 1-11. Springer.

[19] Rosen K. H. (2011). Elementary Number Theory. Sixth Edition. Pearson.

[20] Spickerman W. R. (1982). Binet’s formula for the Tribonacci sequence. The Fibonacci
Quarterly. Vol 20.2 pp 118-120.

[21] Svanström F. (2014). Properties of a generalized Arnold’s cat map. (Master thesis). Lin-
næus University, Växjö, Sweden.

[22] Vince A. (1981). Period of a linear recurrence. Acta Arithmetica. Vol 39.4 pp 303-311.

[23] Wadill M. E. (1978). Some properties of a generalized Fibonacci sequence modulo m. The
Fibonacci Quarterly. Vol 16.4 pp 344-353. Fibonacci Association.

[24] Wall D. D. (1960). Fibonacci series modulo m. The American Mathematical Monthly. Vol
67.6 pp 525-532. Mathematical Association of America.

48
A Mathematica code
Finding the periods for the first 10,000 numbers:

Periods = ParallelTable[k = 1;
A = {{1, 1, 1}, {1, 2, 2}, {2, 3, 4}};
Ak = A;
While[Ak != IdentityMatrix[3],
k++;
Ak = Mod[A.Ak, n]];
{n, k}, {n, 2, 10000}]

Finding the orbit lengths modulo N :

Orbits[n_] := Module[{list, list1, A, v, vk},

list = {};
A = {{1, 1, 1}, {1, 2, 2}, {2, 3, 4}};
For[i = 0, i < n, i++,
For[j = 0, j < n, j++,
For[k = 0, k < n, k++,
v = {{i}, {j}, {k}};
If[MemberQ[list, v] == False,
list1 = {};
AppendTo[list, v];
AppendTo[list1, v];
vk = Mod[A.v, n];
m = 1;
While[vk != v,
AppendTo[list, vk];
AppendTo[list1, vk];
vk = Mod[A.vk, n];
m++];
Print[{v, m}]]]]];
Print[Length[list]]]

Finding the period of a generalised Tribonacci cat map:

PeriodGenTriCat[n_, a_, b_]:= Module[{A,At,k},

A = {{1, 1, 1}, {a, a + 1, a + 1}, {a + 1, b, b + 1}};
At = A;
k = 1;
While[At \neq IdentityMatrix[3],
k++;
At = Mod[A.At, n]];
Print[k]]

49
Encrypting a 3D image with Tribonacci cat map:

TribonacciCatMap = Compile[{{pic, _Real, 3}},

Module[{n},
n = Dimensions[pic][[1]];
Table[pic[[
Mod[x + y + z, n , 1], Mod[x + 2y + 2z, n, 1],
Mod[2x + 3y + 4z, n , 1]]], {x, n}, {y, n}, {z, n}]]]

Encrypting colours with Tribonacci cat map:

TribonacciCatMap = Compile[{{pic, _Integer, 3}},

Module[{A},
A = {{1, 1, 1}, {1, 2, 2}, {2, 3, 4}};
Table[pic[[
Mod[x + y + z, n , 1], Mod[x + 2y + 2z, n, 1],
Mod[2x + 3y + 4z, n , 1]]], {x, n}, {y, n}, {z, n}]]]

50
B Prime number sets
Here we present the primes p under 10,000 divided into the sets presented in section 4. The
tables were created directly in Mathematica by using commands such as Partition[] and Grid[],
which may have resulted in the removal of the last numbers of the lists.

Table A1: R = {r ∣ ρ′ (r) ≤ r − 1}

51
Table A2: Q = {q ∣ ρ′ (q) ≤ q 2 + q + 1}
 s2 −1
Table A3: S = {s ∣ ρ′ (s) ≤ 3
}
Faculty of Technology
SE-391 82 Kalmar ∣ SE-351 95 Växjö
Phone +46 (0) 772-28 80 00
[email protected]
Lnu.se/faculty-of-technology?!=en