# Linear recurrent cryptography:
golden-like cryptography for higher order linear recurrences

Sergiy Koshkin* and Daniel Rodriguez†

*Corresponding author
Department of Mathematics and Statistics
University of Houston-Downtown
One Main Street
Houston, TX 77002
e-mail<EMAIL_ADDRESS>

†Department of Mathematics and Statistics
University of Houston-Downtown
One Main Street
Houston, TX 77002
e-mail<EMAIL_ADDRESS>
###### Abstract

We develop matrix cryptography based on linear recurrent sequences of any
order that allows securing encryption against brute force and chosen plaintext
attacks. In particular, we solve the problem of generalizing error detection
and correction algorithms of golden cryptography previously known only for
recurrences of a special form. They are based on proving the checking
relations (inequalities satisfied by the ciphertext) under the condition that
the analog of the golden $Q$-matrix has the strong Perron-Frobenius property.
These algorithms are proved to be especially efficient when the characteristic
polynomial of the recurrence is a Pisot polynomial. Finally, we outline
algorithms for generating recurrences that satisfy our conditions.

Keywords: Matrix encryption, golden cryptography, checking relations, error
correction, linear recurrence, companion matrix, dominant eigenvalue, strong
Perron-Frobenius property, Pisot polynomial

##  1 Introduction

Golden cryptography, as originally proposed by Stakhov [21, 22], is a type of
matrix encryption where the matrices are $2\times 2$ and their entries are
consecutive terms of the Fibonacci sequence. It has attractive error detection
and correction properties, and was applied to creating digital signatures [4],
and, with some modifications, to image encryption and scrambling [15].
However, it is vulnerable to brute force and chosen plaintext attacks [19, 24]
due to a small number of parameters in the encryption key that are relatively
easy to guess or back engineer.

Some external countermeasures were proposed in [16, 23], and in [12] using
second order linear recurrences more general than the Fibonacci was proposed
to increase the number of key parameters while preserving the error
detection/correction properties. Some special higher order recurrences, such
as $p$-Fibonacci [6] and Tribonacci [5], have also been used. However, for
security purposes it is desirable to develop matrix encryption based on more
or less general linear recurrences if the attractive properties of golden
cryptography can be preserved.

In this paper, we accomplish this task. First, we prove that the coding
matrices whose entries are consecutive terms of order $k$ linear recurrent
integer sequences are exactly of the form
$M_{n}=\begin{pmatrix}L^{n+k-1}x_{0}&\dots&L^{n}x_{0}\end{pmatrix}$, where $L$
is a matrix that naturally generalizes the $Q$-matrix of golden cryptography
and $x_{0}$ is an initial vector (Theorem 1 and Corollary 1). Simple
conditions on $L$ and $x_{0}$ guarantee that $M_{n}$ are invertible, as needed
for decryption, and have entries of feasible size. In the special case when
$L$ is of companion form, $M_{n}$ are symmetric and their entries are terms of
a single recurrent sequence, as in golden cryptography.

A major problem that we had to solve was to generalize the so-called checking
relations of golden cryptography (inequalities satisfied by the ciphertext
entries) upon which its error detection and correction algorithms are based.
It turned out that for this $L$ must have the strong Perron-Frobenius property
[18], i.e. have a simple dominant positive eigenvalue with a strictly positive
eigenvector. The $Q$-matrix, the unimodular $2\times 2$ matrices that arise in
[12] and other generalizations, and the special higher order matrices of [5,
6] happen to have this property, but they are all very special cases of a
general template. By the Perron-Frobenius theory [13, ch. 9], [14, 1.4],
primitive matrices with non-negative entries have the strong Perron-Frobenius
property, and even matrices with some negative entries can have it as well
[18].

The explicit computations traditionally used to establish the checking
relations are exceedingly cumbersome already for the special third order
sequences [5, 6], and become intractable for higher orders. We propose a
different approach based on spectral theory, and our choice of $M_{n}$ ensures
that the checking relations take a particularly simple form (Theorem 2).
Moreover, further analysis of the error correction algorithm shows that the
range where the checking relations locate the correct value shrinks to a point
asymptotically only when $L$ satisfies an additional Pisot condition: all of
its subdominant eigenvalues are confined to the interior of the unit disk
(Theorem 3).

The characteristic polynomials of strong Perron-Frobenius matrices with this
property are known as Pisot polynomials [1]. They have been extensively
studied in number theory and are well understood. In particular, there are
explicit formulas and efficient algorithms for generating them [7, 10]. Our
result also clarifies the role of the unimodularity condition on $L$ imposed
in [12], it implies the Pisot condition for $2\times 2$ matrices.

From our general perspective, the $Q$-matrix played three different roles in
the generation of the coding matrices. It was the initial matrix $M_{0}$, the
generating matrix $L$, and (the transpose of) another generating matrix $R$
defined by $M_{n}=L^{n}M_{0}=M_{0}R^{n}$. In general, all three matrices are
different, $L$ is not necessarily symmetric, and $M_{n}$ are not necessarily
powers of a single matrix. These novelties require suitable changes that we
work out, we also propose a number of methods for generating $L$ and $x_{0}$
that satisfy all our conditions.

The paper is organized as follows. In Section 2 we review the main features of
golden cryptography. It also serves as preliminaries for introducing some
standard notation and terminology of cryptography and linear algebra. In
Section 3 we consider a special case where $M_{n}$ are symmetric and $L$ is
the companion matrix of a recurrence. In Section 4 this is generalized to
coding matrices whose rows are segments of different recurrent sequences that
satisfy the same recurrence. In Section 5 we prove the main results of the
paper on the checking relations for general coding matrices. The transition
ratio, which generalizes the golden ratio, is introduced in Section 6 and its
role in regulating the size of $M_{n}$ entries is highlighted. Section 7
develops error detection and correction algorithms based on the checking
relations and illustrates their application with examples. Generation of the
coding matrices that satisfy the strong Perron-Frobenius and Pisot conditions
is discussed in Section 8, and also illustrated by examples. Finally, in the
last section we summarize the conclusions.

##  2 Golden cryptography

In this section, we review the main points of golden cryptography [22] with an
eye on the general setting. Recall that the Fibonacci sequence is defined by
the linear recurrence $F_{n+2}=F_{n+1}+F_{n}$ with the initial values
$F_{0}=0$ and $F_{1}=1$. For the purposes of encryption we assemble the terms
of the sequence into the golden matrices:

$M_{n}:=\begin{pmatrix}F_{n+2}&F_{n+1}\\\ F_{n+1}&F_{n}\end{pmatrix}.$ (1)

The recurrence relation can be written in a first order form in terms of these
matrices, namely $M_{n+1}=QM_{n}$, where $Q:=\begin{pmatrix}1&1\\\
1&0\end{pmatrix}$ is called the $Q$-matrix. By induction, we then have
$M_{n}=Q^{n}M_{0}$. Note that $Q$ is symmetric, and we also have a happy
coincidence:

$M_{0}=\begin{pmatrix}F_{2}&F_{1}\\\
F_{1}&F_{0}\end{pmatrix}=\begin{pmatrix}1&1\\\ 1&0\end{pmatrix}=Q.$

As a result, $M_{n}=Q^{n+1}$. It is convenient to extend the sequence to the
negative values of $n$ while preserving the recurrence $M_{n+1}=QM_{n}$, this
leads to $M_{-n}=Q^{-n}M_{0}=Q^{-n+1}$.

For the purposes of encryption, the plaintext is digitized (e.g. by using
ASCII codes) and split into blocks of four numbers each that are then arranged
into plaintext matrices $P=\begin{pmatrix}p_{11}&p_{12}\\\
p_{21}&p_{22}\end{pmatrix}$. The encryption key is a (large) natural number
$n$, and the corresponding ciphertext matrix is computed as $C=PM_{n}$. Since
$M_{n}$ are all powers of $Q$, which is invertible, so are they, and the
decryption is done simply as $P=CM_{n}^{-1}$. Moreover,

$M_{n}^{-1}=(Q^{n}M_{0})^{-1}=M_{0}^{-1}Q^{-n}=M_{0}^{-1}M_{-n}M_{0}^{-1}=M_{-n}Q^{-2},$
(2)

i.e. the decryption can be performed by computing the Fibonacci sequence
backwards and inverting $Q$. We note another happy coincidence that $M_{n}$
commute with $Q$ because they are its powers. Explicitly, we find

$M_{n}^{-1}=\left(-1\right)^{n+1}\begin{pmatrix}F_{n}&-F_{n+1}\\\
-F_{n+1}&F_{n+2}\end{pmatrix}.$ (3)

For error detection and correction we need a deeper property of the coding
matrices. It can be derived as follows. Since $P=CM_{n}^{-1}$ and the entries
of $P$ are non-negative integers we get four inequalities for the entries of
$C$ using (3). They can be packaged into two double inequalities for their row
ratios, namely

$\frac{F_{n+1}}{F_{n}}\leq\frac{c_{11}}{c_{12}}\,,\frac{c_{21}}{c_{22}}\leq\frac{F_{n+2}}{F_{n+1}}$
(4)

for odd $n$. For even $n$ the inequality signs are reversed. These are the
checking relations in the inequality form. The recipient of the ciphertext can
test both checking relations and determine in which row the single error, if
any, is located. The two suspect entries can then be estimated by assuming the
other one to be correct.

A well-known property of the Fibonacci sequence, which goes back to Kepler
[9], is that $\lim_{n\to\infty}\frac{F_{n+1}}{F_{n}}=\varphi$, where
$\varphi=1.618\dots$ is the golden ratio and the convergence is exponential.
Therefore, the bounds in (4) get tighter and tighter with increasing $n$, and
ultimately shrink to a single value, the golden ratio. Thus, for large $n$ we
get the asymptotic form of checking relations:

$\frac{c_{11}}{c_{12}}\approx\frac{c_{21}}{c_{22}}\approx\varphi.$ (5)

The next examples briefly illustrates the main ideas. In the traditional
golden cryptography the determinant of $P$ is often transmitted as additional
checking data to enhance error correction, but we do not discuss it here
because its utility diminishes for higher order recurrences, see Section 7.

##  3 Linear recurrent sequences and symmetric
coding matrices

We will now formally extend the encryption scheme of golden cryptography to
higher order linear recurrent sequences. In this section, we consider the
special case of symmetric coding matrices. They are generated based on a
single sequence, and the analogy with golden cryptography is most transparent.
However, the methods we develop will carry over to the more general case
studied in Section 4.

Recall that a $k$-th order linear recurrent sequence satisfies

$X_{n+k}=a_{k-1}X_{n+k-1}+\dots+a_{1}X_{n+1}+a_{0}X_{n}$ (6)

for some coefficients $a_{i}$ [2, ch. 6]. The characteristic (companion)
polynomial of the recurrence is defined as

$f(z):=z^{k}-a_{k-1}z^{k-1}-\dots-a_{1}z-a_{0}.$ (7)

It is convenient to collect the initial values into the initial vector
$x_{0}=\begin{pmatrix}X_{k-1}&\dots&X_{1}&X_{0}\end{pmatrix}^{T}$, which,
together with $a_{i}$, determines the entire sequence. For the purposes of
cryptography, we are mostly interested in integer (even positive integer)
sequences, so it is natural to assume that $a_{i}$ and the entries of $x_{0}$
are integers, although formal considerations in this and the next section do
not depend on this.

######  Definition 1.

Symmetric coding matrices $M_{n}$ associated with a linear recurrent sequence
$X_{n}$ are defined as

$M_{n}:=\begin{pmatrix}X_{n+2k-2}&\dots&X_{n+k-1}\\\ \vdots&\ddots&\vdots\\\
X_{n+k-1}&\dots&X_{n}\end{pmatrix}.$ (8)

$M_{0}$ will be called the initial matrix.

The definition is in direct analogy to the golden matrices (1). Note that the
columns of $M_{n}$ are segments of the same recurrent sequence shifted by a
single entry from one column to the next. This means that each one is obtained
from the one preceding by multiplying the latter by a matrix of special form.

######  Definition 2.

The left companion matrix of a linear recurrence (6) is defined as

$L:=\begin{pmatrix}a_{k-1}&a_{k-2}&\dots&a_{1}&a_{0}\\\ 1&0&\dots&0&0\\\
0&1&\dots&0&0\\\ \vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&\dots&1&0\end{pmatrix}$ (9)

######  Remark.

This is essentially the companion matrix of the characteristic polynomial (7)
of the recurrence, see [11, 7.1]. Under the more common convention, the
companion matrix of a polynomial has the coefficients $a_{i}$ appear in the
last row, and the $1$-s appear above the diagonal rather than below. Our form
is the result of following Stakhov’s convention to place the sequence terms
into vectors in descending order. Accordingly, one can recover the usual
companion form by reversing the order of the indices.

Note that for $k>2$ the matrix $L$ is non-symmetric in non-degenerate cases,
and hence cannot be equal to the initial matrix $M_{0}$, which is. The
$Q$-matrix of golden cryptography, therefore, splits into two different ones,
$L$ and $M_{0}$. With the above notation, we can write

$M_{n}:=\begin{pmatrix}L^{n+k-1}x_{0}&\dots&L^{n}x_{0}\end{pmatrix},$ (10)

hence the entire coding sequence is determined by $L$ and $x_{0}$. In
particular,

$M_{0}=\begin{pmatrix}L^{k-1}x_{0}&\dots&Lx_{0}&x_{0}\end{pmatrix}.$ (11)

As in the golden case, $M_{n}$ satisfy a first order matrix recurrence
$M_{n+1}=LM_{n}$, and $M_{n}=L^{n}M_{0}$.

######  Remark.

The authors of [5, 6] take the bare powers $L^{n}$ rather than $M_{n}$ as the
coding matrices. This choice generalizes a different feature of the golden
matrices, that they are powers of the $Q$-matrix. However, then the entries of
$M_{n}$ have more complex expressions in terms of the sequence $X_{n}$, and
removing the dependence on $M_{0}$ takes away additional parameters that make
encryption more secure.

######  Example 1.

Two higher order examples considered in the cryptographic literature are
$k$-bonacci [5] and $p$-Fibonacci [6] sequences ($p:=k-1$). In the former all
$a_{i}=1$, i.e. $X_{n+k}=X_{n+k-1}+\dots+X_{n+1}+X_{n}$, and in the latter all
$a_{i}=0$ except $a_{0}=a_{k-1}=1$, i.e. $X_{n+k}=X_{n+k-1}+X_{n}$. In both
examples $x_{0}:=(1,0\dots,0)^{T}$. Only the cases $k=3$, Tribonacci and
$2$-Fibonacci, have been studied in any detail. For the Tribonacci the left
transition and initial matrices are, respectively,

$L=\begin{pmatrix}1&1&1\\\ 1&0&0\\\ 0&1&0\end{pmatrix},\ \ \ \
M_{0}=\begin{pmatrix}2&1&1\\\ 1&1&0\\\ 1&0&0\end{pmatrix};$

and for the $2$-Fibonacci they are

$L=\begin{pmatrix}1&0&1\\\ 1&0&0\\\ 0&1&0\end{pmatrix},\ \ \ \
M_{0}=\begin{pmatrix}1&1&1\\\ 1&1&0\\\ 1&0&0\end{pmatrix}.$

Another natural recurrence to consider is $X_{n+k}=X_{n+1}+X_{n}$. For $k=3$
the matrices are:

$L=\begin{pmatrix}0&1&1\\\ 1&0&0\\\ 0&1&0\end{pmatrix},\ \ \ \
M_{0}=\begin{pmatrix}1&0&1\\\ 0&1&0\\\ 1&0&0\end{pmatrix}.$

This $L$, and its higher dimensional analogs, come up in the Perron-Frobenius
theory due to a result of Wielandt [17, 20], so we will refer to the
recurrence as the order $k$ Wielandt recurrence. Just as with $k$-bonacci and
$p$-Fibonacci matrices the entries of its powers grow slowly, making them
feasible for encryption. For $k=2$ all three reduce to the Fibonacci
recurrence.

As in the golden case, we extend the sequence to the negative values so that
$M_{n+1}=LM_{n}$ continues to hold. This extension exists uniquely if $L$ is
invertible, which we must assume anyway. Recall that a vector $x$ is called
cyclic for a $k\times k$ matrix $A$ if $x,Ax,\dots A^{k-1}x$ span the entire
space [11, 7.1].

######  Lemma 1 (Invertibility of $M_{n}$).

The coding matrices $M_{n}$ are invertible if and only if $L$ is invertible
and $x_{0}$ is its cyclic vector. Moreover,

$M_{n}^{-1}=M_{0}^{-1}M_{-n}M_{0}^{-1},$ (12)

###### Proof.

Since $M_{n}=L^{n}M_{0}$ both $L$ and $M_{0}$ must be invertible. But
$M_{0}=\begin{pmatrix}L^{k-1}x_{0}&\dots&Lx_{0}&x_{0}\end{pmatrix}$, so it is
invertible if and only if $x_{0}$ is cyclic. The inversion formula is
established by the same computation as in (2), with $Q$ replaced by $L$. ∎

Unlike in the golden case, the inversion formula identity cannot be simplified
further because $L$ and $M_{0}$ do not necessarily commute. By the cofactor
expansion in the last column, $\det L=(-1)^{k-1}a_{0}$, so it is invertible if
and only if $a_{0}\neq 0$. It is straightforward to check that
$x_{0}:=(1,0\dots,0)^{T}$, which is typically chosen as the vector of initial
values in golden cryptography and its generalizations [5, 6], is always cyclic
for a left companion matrix. But it has plenty more cyclic vectors, and their
entries can provide welcome extra parameters for the encryption key.

Encryption and decryption proceed analogously to the golden cryptography.
Numerical plaintext is split into blocks of $k^{2}$ numbers each and arranged
into plaintext matrices $P$ (say, row by row, left to right). The encryption
key is a triple: $k$ coefficients of the recurrence $a_{i}$, $k$ entries of
the initial vector $x_{0}$, and a natural number $n$. In total, we have $2k+1$
parameters. The ciphertext matrix is computed as $C=PM_{n}$, and the
decryption is performed by $P=CM_{n}^{-1}$.

######  Example 2.

Consider the $p$-Fibonacci sequence with $p=2$. The recurrence is
$X_{n+3}=X_{n+2}+X_{n}$, and for $x_{0}:=(1,0\dots,0)^{T}$ the sequence is

$X_{n}=0,0,1,1,2,3,4,6,9,13,19,28,41,60,88,129,189,277,406\dots$

Forming the coding matrix for $n=15$ according to (14) we find:

$M_{15}=\begin{pmatrix}X_{19}&X_{18}&X_{17}\\\ X_{18}&X_{17}&X_{16}\\\
X_{17}&X_{16}&X_{15}\end{pmatrix}=\begin{pmatrix}406&277&189\\\ 277&189&129\\\
189&129&88\end{pmatrix}\\!.$

Suppose the word ALGORITHM is digitized using ASCII values $A=65,\ L=76,\
G=71,\ O=79,\ R=82,\ I=73,\ T=84,\ H=72,\ M=77$, so the plaintext matrix is
$P=\begin{pmatrix}65&76&71\\\ 79&82&73\\\ 84&72&77\end{pmatrix}$. Selecting
$n=15$ we compute

$C=PM_{15}=\begin{pmatrix}65&76&71\\\ 79&82&73\\\
84&72&77\end{pmatrix}\begin{pmatrix}406&277&189\\\ 277&189&129\\\
189&129&88\end{pmatrix}=\begin{pmatrix}60861&41528&28337\\\
68585&46798&31933\\\ 68601&46809&31940\end{pmatrix}$

To decrypt, we make use of (12). First, we extend the sequence to the negative
indices, $X_{-n}=1,0,-1,1,1,-2,0,3,-2,-3,5,1,-8,4,9...$, and find
$M_{-15}=\begin{pmatrix}5&1&-8\\\ 1&-8&4\\\ -8&4&9\end{pmatrix}$. We know
$M_{0}$ from Example 1 and compute $M_{0}^{-1}=\begin{pmatrix}0&0&1\\\
0&1&-1\\\ 1&-1&0\end{pmatrix}$. This is the only inversion that needs to be
performed. Since the entries of $M_{0}$ are small compared to those of $M_{n}$
computational effort is saved. Moreover, according to (12), we now only need
to perform two matrix multiplications to find $M_{n}^{-1}$. Thus,

$\displaystyle M_{15}^{-1}=\begin{pmatrix}9&5&-12\\\ -5&-7&21\\\
-12&21&-5\end{pmatrix},\text{\ and}$ $\displaystyle
P=CM_{15}^{-1}=\begin{pmatrix}60861&41528&28337\\\ 68585&46798&31933\\\
68601&46809&31940\end{pmatrix}\\!\\!\\!\begin{pmatrix}9&5&-12\\\ 5&-7&21\\\
-12&21&-5\end{pmatrix}=\begin{pmatrix}65&76&71\\\ 79&82&73\\\
84&72&77\end{pmatrix}\\!\\!.$

##  4 General coding matrices

The symmetric coding matrices of the previous section are generated by a
single linear recurrent sequence. As a result, the left transition matrix $L$
had a special companion form, and its $k^{2}$ entries were completely
determined by merely $k$ parameters $a_{i}$. We could instead pick an
arbitrary matrix $L$ in addition to an arbitrary initial vector $x_{0}$,
produce $M_{0}$ according to (11), and then generate the coding matrices
$M_{n}:=L^{n}M_{0}$ as before. This increases the number of encryption key
parameters from $2k+1$ to $k^{2}+k+1$. It turns out that such general coding
matrices still have a nice characterization in terms of recurrent sequences.
We discuss two alternative representations in this section.

###  4.1 Row sequences

While the symmetric coding matrices are generated by a single recurrent
sequence, general ones involve $k$ different sequences, albeit all satisfying
the same recurrence. For second order recurrences golden cryptography was
extended to general coding matrices in [12].

######  Theorem 1 (Recurrent coding matrices).

Let $L$ be a $k\times k$ matrix with the characteristic polynomial
$\chi_{L}(z)=z^{k}-a_{k-1}z^{k-1}-\dots-a_{1}z-a_{0}$ and $x_{0}$ be a
$k$-vector. Set

$M_{0}:=\begin{pmatrix}L^{k-1}x_{0}&\dots&Lx_{0}&x_{0}\end{pmatrix}$ (13)

and $M_{n+1}=LM_{n}$. Then

$M_{n}=L^{n}M_{0}=\begin{pmatrix}X_{n+k-1}^{(k-1)}&\dots&X_{n}^{(k-1)}\\\\[5.0pt]
\vdots&&\vdots\\\ X_{n+k-1}^{(0)}&\dots&X_{n}^{(0)}\end{pmatrix},$ (14)

where $X_{n}^{(i)}$ are some sequences satisfying the same recurrence

$X_{n+k}=a_{k}X_{n+k-1}+\dots+a_{1}X_{n+1}+a_{0}X_{n}.$

###### Proof.

By induction,

$M_{n}:=\begin{pmatrix}L^{n+k-1}x_{0}&\dots&L^{n}x_{0}\end{pmatrix},$ (15)

so the columns of $M_{n}$ shift one place to the right in $M_{n+1}$.
Therefore, $M_{n}$ have the form (14) for some sequences $X_{n}^{(i)}$. By the
Cayley–Hamilton theorem,

$\chi_{L}(L)=L^{k}-a_{k-1}L^{k-1}-\dots-a_{1}L-a_{0}I=0.$

Applying both sides to $x_{n}:=L^{n}x_{0}$ and noting that
$L^{s}x_{n}=x_{n+s}$, we see that the $i$-th entry of $\chi_{L}(L)x_{n}$ is
$X_{n+k}^{(i)}-a_{k-1}X_{n+k-1}^{(i)}-\dots-
a_{1}X_{n+1}^{(i)}-a_{0}X_{n}^{(i)}$, and all these entries are $0$. In other
words, $X_{n}^{(i)}$ satisfy the recurrence for each $i$. ∎

In the symmetric case, we picked a single $X_{n}$ and chose
$X_{0}^{(i)}=X_{i}$, so the rows of $M_{n}$ were shifted segments of the same
sequence.

######  Definition 3.

Consider a matrix sequence $M_{n}$ of the form (14). We call the linear
recurrent sequences $X_{n}^{(i)}$ its row sequences.

######  Example 3.

Take $L=\begin{pmatrix}1&2\\\ 3&4\end{pmatrix}$. Its characteristic polynomial
is $\chi_{L}(z)=z^{2}-5z-2$, so $a_{0}=2$ and $a_{1}=5$. If we take the
initial vector to be $x_{0}=\begin{pmatrix}1&0\end{pmatrix}^{T}$ then
$M_{0}=\begin{pmatrix}1&1\\\ 3&0\end{pmatrix}$ from (13), which gives us the
initial values for the recurrent row sequences. Computing them recursively, we
find

$\displaystyle X_{m}^{(1)}$
$\displaystyle=1,1,7,37,199,1069,5743,30853,165751,890461,4783807...$
$\displaystyle X_{m}^{(0)}$
$\displaystyle=0,3,15,81,435,2337,12555,67449,362355,1946673,10458075...$

For $n=9$ this gives

$M_{9}=\begin{pmatrix}X_{10}^{(1)}&X_{9}^{(1)}\\\\[2.5pt]
X_{10}^{(0)}&X_{9}^{(0)}\\\ \end{pmatrix}=\begin{pmatrix}4783807&890461\\\
10458075&1946673\end{pmatrix}\\!.$

The rapid growth of these sequences may cause problems in practice, when large
values of $n$ need to be used, both for security purposes and for effective
error correction. The underlying reason (see Section 6) is that the spectral
radius of our $L$ is quite large, $\approx 5.372$. This has to be addressed
when generating feasible $L$, see Section 8.

###  4.2 Right companion matrices

We will now derive an alternative representation for $M_{n}$ that proves
useful for both theoretical and practical purposes.

######  Definition 4.

Consider a matrix sequence $M_{n}$. If $M_{n+1}=LM_{n}$ we call $L$ its left
transition matrix, and if $M_{n+1}=M_{n}R$ we call $R$ its right transition
matrix.

Equivalently, $M_{n}=L^{n}M_{0}$ if $L$ is a left transition matrix, and
$M_{n}=M_{0}R^{n}$ if $R$ is a right one. Of course, a general matrix sequence
does not have either a left or a right transition matrix, and they may not be
unique even when it does have them. However, if $M_{0}$ is invertible then $L$
and $R$, if any, are uniquely determined, and if there is one then there is
also the other. Indeed, if $L$ is the left transition matrix then we set
$R:=M_{0}^{-1}LM_{0}$, and compute by induction

$L^{n}M_{0}=L^{n-1}LM_{0}=L^{n-1}M_{0}R=\dots=LM_{0}R^{n-1}=M_{0}R^{n}.$

For a symmetric coding sequence (8) the left transition matrix coincides with
the left companion matrix of the recurrence (9), but in general it is not of
the companion form, and is not determined by the recurrence alone. Indeed, it
can be an arbitrary matrix with the characteristic polynomial coinciding with
the characteristic polynomial of the recurrence.

However, even for a general coding sequence (14) the right transition matrix
depends on the recurrence only. Indeed, that the row sequences satisfy the
same recurrence can be expressed in the matrix form as $M_{n+1}=M_{n}R$, or
explicitly

$\begin{pmatrix}X_{n+k}^{(k-1)}&\dots&X_{n+1}^{(k-1)}\\\\[5.0pt]
X_{n+k}^{(k-2)}&\dots&X_{n+1}^{(k-2)}\\\ \vdots&&\vdots\\\
X_{n+k}^{(0)}&\dots&X_{n}^{(0)}\\\
\end{pmatrix}\\!\\!=\\!\\!\begin{pmatrix}X_{n+k-1}^{(k-1)}&\dots&X_{n}^{(k-1)}\\\\[5.0pt]
X_{n+k-1}^{(k-2)}&\dots&X_{n}^{(k-2)}\\\ \vdots&&\vdots\\\
X_{n+k-1}^{(0)}&\dots&X_{n}^{(0)}\\\
\end{pmatrix}\\!\\!\begin{pmatrix}a_{k-1}&1&0&\dots&0\\\
a_{k-2}&0&1&\dots&0\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
a_{1}&0&0&\dots&1\\\ a_{0}&0&0&\dots&0\end{pmatrix}\\!\\!.$

######  Definition 5.

The right companion matrix of a linear recurrence (6) is defined as the
transpose of its left companion matrix:

$R:=\begin{pmatrix}a_{k-1}&1&0&\dots&0\\\ a_{k-2}&0&1&\dots&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\ a_{1}&0&0&\dots&1\\\
a_{0}&0&0&\dots&0\end{pmatrix}\\!.$ (16)

Thus, while the left transition matrix may be arbitrary, the right transition
matrix is always of the right companion form. In the symmetric case $R=L^{T}$,
and again coincides with the $Q$-matrix in the golden case. In general, all
three matrices $M_{0}$, $L$ and $R$ are different.

Recall that to enable decryption we need $L$ and $M_{0}$ to be invertible. The
latter implies that $x_{0}$ must be a cyclic vector for $L$. Under this
assumption, $R$ can be characterized as the unique matrix that satisfies
$LM_{0}=M_{0}R$. Moreover, a converse of Theorem 1 holds.

######  Corollary 1.

Invertible matrices of the form (14), whose row sequences satisfy the same
recurrence, are given by $M_{n}=L^{n}M_{0}$ for some matrix $L$ and $M_{0}$ of
the form (13).

###### Proof.

We know that $M_{n}=M_{0}R^{n}$ for $R$ in (16). If we set
$L:=M_{0}RM_{0}^{-1}$ then we have by induction $M_{n}=L^{n}M_{0}$. Due to the
companion structure of $R$, all columns after the first in $M_{0}R$ are the
columns of $M_{0}$ shifted one place to the right. Since $LM_{0}=M_{0}R$ by
construction it follows that the columns of $M_{0}$ can be obtained by
successively multiplying its last column by $L$. Taking the last column as
$x_{0}$, we thereby represented $M_{0}$ as in (13). ∎

It follows that we can start with an arbitrary linear recurrence having
$a_{0}\neq 0$, and an arbitrary invertible matrix $M_{0}$, instead of $L$ and
$x_{0}$, to get the same class of coding matrices (14). In particular, to
generate the coding matrices $M_{n}$, we only need to generate $k$ recurrent
sequences whose terms fill their rows. The entries of $R$ package the
recurrence coefficients, and the rows of $M_{0}$ package the initial values
for each.

Moreover, if we take $M_{0}=R$ then $LM_{0}=M_{0}R$ implies that $L=M_{0}=R$,
and all three matrices coincide. Then the coding matrices are bare powers
$M_{n}=R^{n+1}$, as with the $Q$-matrix. This is similar to the setup adopted
in [5] for the Tribonacci recurrence, except the authors use the transpose
$R^{T}$ in place of $R$ when taking the powers. This results in the checking
relations having a more complicated form.

######  Remark.

While left companion matrices (9) always have cyclic vectors this is not the
case for general $L$. Nonetheless, matrices with cyclic vectors are generic.
Recall that the minimal polynomial $\mu_{L}(z)$ of a matrix $L$ is the monic
polynomial of the least degree such that $\mu_{L}(L)=0$. The matrix is called
non-derogatory if $\mu_{L}(z)=\chi_{L}(z)$, or, equivalently, if its Jordan
cells have distinct eigenvalues. It follows from linear algebra that a matrix
has a cyclic vector if and only if it is non-derogatory [11, 7.1]. When this
is the case non-cyclic vectors are confined to a subvariety of smaller
dimensions, so almost every vector is cyclic. Moreover, if $\chi_{L}$ is
irreducible over some subfield of ${\mathbb{R}}$ then $L$ is diagonalizable
with distinct eigenvalues, and every non-zero vector with entries from that
subfield is cyclic. This is particularly useful to us when the subfield is
${\mathbb{Q}}$.

######  Example 4.

Using a random number generator (between $0$ and $2$) for the entries we
generated $L=\begin{pmatrix}2&1&2\\\ 0&1&2\\\ 2&2&2\end{pmatrix}$. Its
characteristic polynomial is computed to be $z^{3}-5z^{2}+4$, so $a_{0}=-4$,
$a_{1}=0$, and $a_{2}=5$. Since $a_{0}\neq 0$ this $L$ is invertible.
Moreover, the recurrence relation is $X_{n+3}=5X_{n+2}-4X_{n}$, and the right
companion matrix is $R=\begin{pmatrix}5&1&0\\\ 0&0&1\\\ -4&0&0\\\
\end{pmatrix}$.

Note that $z^{3}-5z^{2}+4$ reduces over ${\mathbb{Q}}$ since $1$ is a root.
Nonetheless, the standard initial vector $x_{0}=\begin{pmatrix}1\\\ 0\\\
0\end{pmatrix}$ is cyclic, and the initial matrix
$M_{0}=\begin{pmatrix}8&2&1\\\ 4&0&0\\\ 8&2&0\end{pmatrix}$ is invertible.
Generating the row sequences by the recurrence with the initial values from
$M_{0}$, we find, for example, $M_{5}=\begin{pmatrix}19292&3996&828\\\
11300&2340&484\\\ 21632&4480&928\\\ \end{pmatrix}.$

Theorem 1 and Corollary 1 mean that $L,x_{0},n$ and $M_{0},a_{i},n$ provide
two alternative parametrizations of the encryption key, both with $k^{2}+k+1$
parameters. In the first representation, $L$ is arbitrary, but $M_{0}$ is of
the special cyclic form (13); in the second one, $M_{0}$ is arbitrary, but $R$
is of the special companion form (16). For the second order recurrences these
parametrizations and matrices were introduced in [12].

##  5 Checking relations

In this section, we turn from formal considerations to spectral conditions
needed for the feasibility of encryption and error detection/correction, and
prove the main technical results of the paper that generalize the checking
relations of golden cryptography. Their inequality form turns out to hold
universally when the coding and plaintext matrices have non-negative entries,
and nothing needs to be assumed about $M_{n}$. But the asymptotic form
requires much stronger conditions, such as the strong Perron-Frobenius and
Pisot conditions for the left transition matrix $L$. Readers interested in
applications to cryptography can skip most of this section, and only refer to
definitions and the statements of Theorems 2 and 3 as needed.

###  5.1 Checking relations: inequality form

The usual method for deriving the two-sided inequalities (4) based on
explicitly inverting the coding matrices quickly becomes too cumbersome in
higher orders, as can be seen already for the simplest third order sequences
in [5] and [6]. We give instead a very short proof based on an elementary
inequality from [14, 2.1] for $k$-tuples of real numbers $r_{l},q_{l}$ with
$q_{l}\geq 0$:

$\min_{1\leq l\leq
k}\left(\frac{r_{l}}{q_{l}}\right)\leq\frac{\sum_{l=1}^{k}r_{l}}{\sum_{l=1}^{k}q_{l}}\leq\max_{1\leq
l\leq k}\left(\frac{r_{l}}{q_{l}}\right).$ (17)

Here it is customary to assume $q_{l}>0$, but one can allow $q_{l}=0$ if
$\frac{r_{l}}{0}$ is interpreted as $\pm\infty$ with the sign matching the
sign of $r_{l}$, and $\frac{0}{0}$ are simply dropped from the list under
$\min$ and $\max$.

######  Lemma 2.

Suppose $C=PM$, where $P$ and $M$ have non-negative entries. Then

$\min_{1\leq l\leq
k}\left(\frac{m_{lj}}{m_{lj^{\prime}}}\right)\leq\frac{c_{ij}}{c_{ij^{\prime}}}\leq\max_{1\leq
l\leq k}\left(\frac{m_{lj}}{m_{lj^{\prime}}}\right).$ (18)

In other words, the ratios of same row entries of $C$ are between the minimal
and the maximal ratios of same row entries of $M$ taken in the corresponding
two columns.

###### Proof.

By definition of matrix multiplication,

$\frac{c_{ij}}{c_{ij^{\prime}}}=\frac{\sum_{l=1}^{k}p_{il}\,m_{lj}}{\sum_{l=1}^{k}p_{il}\,m_{lj^{\prime}}}\,.$

Applying (17) with $r_{l}=p_{il}\,m_{lj}$ and $q_{l}=p_{il}\,m_{lj^{\prime}}$
we get the desired conclusion. ∎

If we apply Lemma 2 to the golden matrices $M=M_{n}$ from (1) with $j=1$,
$j^{\prime}=2$ then we immediately get the golden checking inequalities (4).
For the general coding matrices (14) same row entries in $M_{n}$ are terms of
the same row sequences $X_{n}^{(q)}$ with $m^{(n)}_{ij}=X_{n+k-j}^{(k-i)}$.

###  5.2 Checking relations: asymptotic form

Now let us turn to the asymptotic form of the checking relations (5). As with
the Fibonacci recurrence, we need the ratios of consecutive terms in the row
sequences to converge to a common limit that depends only on the recurrence.
Recall that

$M_{n}=\begin{pmatrix}L^{n+k-1}x_{0}&\dots&L^{n}x_{0}\end{pmatrix},$ (19)

i.e. consecutive columns of $M_{n}$ are obtained by applying consecutive
powers of $L$ to the initial vector $x_{0}$. Therefore, the limit ratios
between their corresponding entries are determined by the asymptotic behavior
of $L^{n}x_{0}$. This behavior can be conveniently studied using the
decomposition of $x_{0}$ into generalized eigenvectors of $L$.

For notation and terminology from linear algebra used in this and the next
subsection see e.g. [2, 13]. Recall that a non-zero vector $x$ is called its
eigenvector of a matrix $A$ when it satisfies $Ax=\lambda x$, and $\lambda$ is
called the eigenvalue. All vectors annihilated by some power of $A-{\lambda}I$
are called generalized eigenvectors of $A$ corresponding to ${\lambda}$, and
they form the generalized eigenspace of $A$. As a consequence of the canonical
Jordan decomposition, any matrix has a basis of generalized eigenvectors.

######  Definition 6.

An eigenvalue ${\lambda}$ is called simple when it has multiplicity $1$ in the
characteristic polynomial. It is called dominant when $|\mu|<|\lambda|$ for
all other eigenvalues $\mu$.

When an eigenvalue is simple the corresponding generalized eigenspace is one
dimensional and is spanned by a single eigenvector. And if a matrix has real
entries, the case of primary interest to us, then the dominant eigenvalue, if
any, must be real. Otherwise, it cannot dominate its complex conjugate, which
is also an eigenvalue.

######  Definition 7 ([18]).

A matrix $L$ is said to have the strong Perron-Frobenius property if it has a
simple positive dominant eigenvalue, and the corresponding eigenvector has
strictly positive entries.

The $Q$-matrix, and the left transition matrices of the $k$-Bonacci,
$p$-Fibonacci, and any order Wielandt recurrences have the strong Perron-
Frobenius property, as do all primitive matrices from the Perron-Frobenius
theory. It is the condition we will use to derive the asymptotic form of the
checking relations.

######  Lemma 3.

Let $M_{n}$ be the general recurrent coding matrices (14). Assume that they
are invertible and the left transition matrix $L$ of $M_{n}$ has the strong
Perron-Frobenius property. Then for the ratios of terms in the row sequences
of $M_{n}$ we have $\frac{X_{n+s}^{(i)}}{X_{n}^{(i)}}=\tau^{s}+o(n)$ with
exponentially small $o(n)$, where $\tau$ is the dominant eigenvalue.

###### Proof.

For simplicity, we sketch the proof for the case when all generalized
eigenvectors are eigenvectors, only indicating changes needed for the general
case. Let ${\lambda}_{i}$ be the eigenvalues of $L$ (possibly repeating) and
$u_{i}$ be the corresponding eigenvectors, with ${\lambda}_{1}=\tau$ and
$u_{1}=u$ being the dominant eigenvalue and the corresponding eigenvector. In
the basis of eigenvectors $x_{0}=x_{0}^{1}\,u_{1}+\dots+x_{0}^{k}\,u_{k}$ and

$L^{n}x_{0}=x_{0}^{1}\,\tau^{n}u+x_{0}^{2}\,\lambda_{2}^{n}u_{2}+\dots+x_{0}^{k}\,\lambda_{k}^{n}u_{k}\\\
=\tau^{n}\left(x_{0}^{1}\,u+\left(\frac{\lambda_{2}}{\tau}\right)^{n}x_{0}^{2}\,u_{2}+\dots+\left(\frac{\lambda_{k}}{\tau}\right)^{n}x_{0}^{k}\,u_{k}\right).$

In general, the second and further terms may have polynomials in $n$
multiplying the factors $\left(\frac{\lambda_{i}}{\tau}\right)^{n}$, but they
still decrease exponentially since $\tau$ is dominant. Applying this
asymptotic to the corresponding entries in $L^{n+s}x_{0}$ and $L^{n}x_{0}$ we
find

$\frac{X_{n+s}^{(i)}}{X_{n}^{(i)}}=\frac{(L^{n+s}x_{0})^{i}}{(L^{n}x_{0})^{i}}=\frac{\tau^{n+s}\,x_{0}^{1}\,u^{i}+o(n)}{\tau^{n}\,x_{0}^{1}\,u^{i}+o(n)}=\tau^{s}+o(n),$

assuming that the dominant terms in the numerator and the denominator are non-
zero.

Since $u$ has strictly positive entries $u^{i}\neq 0$, so it remains to show
that $x_{0}^{1}\neq 0$. By contradiction, suppose $x_{0}^{1}=0$. Then applying
$L^{n}$ to the generalized eigenvector expansion of $x_{0}$ we see that $u$
component never appears in the expansions of $L^{n}x_{0}$ for any $n$.
Therefore, $L^{n}x_{0}$ do not span the entire space and $x_{0}$ is not
cyclic. But invertibility of $M_{0}$ implies that $x_{0}$ is cyclic by
Corollary 1, contradiction. ∎

Note that the proof implies that the entries of $M_{n}$ have the same sign for
large $n$, namely the sign of $x_{0}^{1}$, and we can always make them
positive by switching the sign of the initial vector if necessary. Combining
Lemmas 2 and 3 we arrive at the announced main result.

######  Theorem 2.

Let the ciphertext matrix be $C=PM_{n}$, where $M_{n}$ are the general
recurrent coding matrices (14), and $L$ be the left transition matrix of
$M_{n}$. Assume the following:

(i) $P$ has non-negative entries;

(i) $M_{n}$ are invertible with positive entries;

(iii) $L$ has the strong Perron-Frobenius property.

Let $m_{ij}^{(n)}$ be the entries of $M_{n}$ and $\tau$ be the dominant
eigenvalue of $L$. Then for the entries $c_{ij}$ of $C$ we have

$\min_{1\leq l\leq
k}\left(\frac{m_{lj}^{(n)}}{m_{lj^{\prime}}^{(n)}}\right)\leq\frac{c_{ij}}{c_{ij^{\prime}}}\leq\max_{1\leq
l\leq k}\left(\frac{m_{lj}^{(n)}}{m_{lj^{\prime}}^{(n)}}\right),$ (20)

and both bounds converge to $\tau^{j^{\prime}-j}$ exponentially fast for all
$i,j,j^{\prime}$ when $n\to\infty$. In particular,

$\frac{c_{ij}}{c_{ij^{\prime}}}=\tau^{j^{\prime}-j}+o(n)$ (21)

with exponentially small $o(n)$.

We recover the more traditional checking relations for consecutive entries by
taking $j^{\prime}=j+1$.

###  5.3 Pisot condition

One might hope that for large enough $n$ the ranges for $c_{ij}$ allowed by
the checking relations will shrink, eventually leaving a single integer within
them, and eliminate the need for trial and error in correction. However, this
is not the case in general. True, the distance between the bounds in (20) does
go to $0$ since they both converge to $\tau$. But if we are using
$c_{ij^{\prime}}$ to recover $c_{ij}$, the range of $c_{ij}$’s possible values
gets scaled by $c_{ij^{\prime}}$. And the size of $c_{ij^{\prime}}$ grows
exponentially with $n$ for a given plaintext, because $C=PM_{n}$ and the
entries of $M_{n}$ grow exponentially.

######  Definition 8.

The checking range for $c_{ij}$ (relative to $c_{ij^{\prime}}$) is the
interval for its values specified by the checking relations (20).

To ensure the shrinking of the checking range we need a stronger condition on
$L$ than the strong Perron-Frobenius property. It turns out that the range’s
asymptotic behavior depends on the subdominant eigenvalues of $L$, and it will
shrink to a point when they are all located inside the unit disk. This is the
Pisot condition [1].

######  Definition 9.

A polynomial is called Pisot if it has real coefficients, the free term $\geq
1$, a simple positive dominant root, and the rest of the roots have absolute
values $<1$. We call a linear recurrence or a matrix Pisot if their
characteristic polynomial is Pisot.

Pisot polynomials with integer coefficients are well studied in number theory
and there are explicit formulas and effective algorithms for generating them
[7, 10]. Second order recurrences with real coefficients, simple positive
dominant root $\tau$, and the free term $\pm 1$, like the Fibonacci recurrence
or unimodular recurrences of [12], are automatically Pisot because the second
root is $\pm\frac{1}{\tau}$. One can check directly that Tribonacci,
$2$-Fibonacci and order $3$ Wielandt recurrences are also Pisot. However,
order $4$ Wielandt recurrence is not Pisot, its second largest eigenvalue pair
has absolute values $\approx 1.06$.

######  Theorem 3.

In conditions of Theorem 2 suppose additionally that $L$ is Pisot. Then the
checking ranges shrink to a point when $n\to\infty$.

###### Proof.

Let $\sigma$ denote the second largest eigenmodulus of $L$. Following the
notation of Lemma 3 and keeping only the leading terms of the asymptotic, we
compute

$\displaystyle\frac{X_{n+s}^{(i)}}{X_{n}^{(i)}}-\frac{X_{n+s}^{(j)}}{X_{n}^{(j)}}=\frac{(L^{n+s}x_{0})^{i}}{(L^{n}x_{0})^{i}}-\frac{(L^{n+s}x_{0})^{j}}{(L^{n}x_{0})^{j}}=\frac{x_{0}^{1}\sum\limits_{|\lambda_{l}|=\sigma}Q_{i,j}(n)\left(\frac{\lambda_{l}}{\tau}\right)^{n}+\text{LOT}}{(x_{0}^{1})^{2}\,u^{i}u^{j}+\text{LOT}},$
(22)

where $Q_{i,j}(n)$ are polynomials of degree at most $k-2$, and LOT are
exponentially smaller terms. Note that in conditions of Theorem 2
$(x_{0}^{1})^{2}\,u^{i}u^{j}\neq 0$. Therefore,

$\left|\frac{X_{n+s}^{(i)}}{X_{n}^{(i)}}-\frac{X_{n+s}^{(j)}}{X_{n}^{(j)}}\right|\leq
Q(n)\,\left(\frac{\sigma}{\tau}\right)^{n},$

where the polynomial $Q(n)$ absorbs all the constants. In particular, this
estimate holds for the difference between the bounds in (20). Since
$c_{ij^{\prime}}$ is a positive linear combination of $X_{m}^{(i)}$ with
$n\leq m\leq n+k-1$ by (14), it is bounded by $K\tau^{n}$ for some $K>0$.
Hence the length of the checking range is bounded by $KQ(n)\,\sigma^{n}$.
Under the Pisot condition, $\sigma<1$ and it goes to $0$ when $n\to\infty$. ∎

##  6 Transition ratio and the size of entries

In view of the checking relations and by analogy to the golden ratio, it is
convenient to give the dominant eigenvalue of the left transition matrix a
name.

######  Definition 10.

Let $L$ be the left transition matrix of a coding sequence $M_{n}$ with a
simple positive dominant eigenvalue $\tau$. We call $\tau$ the transition
ratio of $M_{n}$.

The golden ratio $\varphi$ is exactly the dominant eigenvalue of the
$Q$-matrix and the transition ratio of the golden matrices $M_{n}=Q^{n+1}$. In
general, when $M_{0}$ is invertible $L$ and $R$ are intertwined by it and
hence similar, so the transition ratio can also be characterized as the
dominant eigenvalue of $R$. In particular, like $R$, the transition ratio is
determined by the recurrence (6) alone.

Of course, $\tau$ is nothing other than the spectral radius of $L$, which is
defined for any matrix. But its relation to the size of entries of $M_{n}$ is
stronger than for arbitrary matrices where the growth of some entries may have
no effect on the spectral radius, as in triangular matrices. Since the rows of
$M_{n}$ are segments of recurrent sequences with the limit ratio $\tau$ they
asymptotically grow as $K\tau^{n}$ for some constant $K$. This means that
practical considerations require $\tau$ not to be too large if large $n$ are
to still be feasible for encryption, see Example 3. Note that for invertible
integer valued matrices we always have $\tau\geq 1$ because the determinant is
at least $1$ by absolute value. In examples appearing in the literature one
typically has $\tau<2$.

We can also give a more straightforward characterization of the transition
ratio analogous to the usual definition of the golden ratio, which is
convenient for estimating its numerical values.

######  Definition 11.

Given a linear recurrence (6) define its standard sequence $S_{n}$ as the one
satisfying it with the initial values $S_{k-1}=1$, $S_{k-2}=\dots=S_{0}=0$.

For the Fibonacci recurrence the standard sequence will be exactly the
sequence of Fibonacci numbers. The authors of [5, 6] use the standard
sequences of the Tribonacci and $2$-Fibonacci recurrences, respectively.

######  Corollary 2.

Suppose the left companion matrix (9) of a linear $k$-th order recurrence is
invertible and has a simple dominant eigenvalue $\tau$, whose eigenvector has
strictly positive entries. Let $S_{n}$ be its standard sequence, then

$\tau=\lim_{n\to\infty}\frac{S_{n+1}}{S_{n}},$ (23)

and the convergence is exponentially fast.

###### Proof.

We apply Lemma 3 with $M_{0}$ of the form (11). For the standard sequence,
$x_{0}=\begin{pmatrix}1&0&\dots&0\end{pmatrix}^{T}$ and is cyclic for any
invertible companion matrix $L$. Hence $M_{0}$ and all $M_{n}=L^{n}M_{0}$ are
invertible, so all conditions of the lemma are met. In this case, $M_{n}$ are
of the form (8) with $S_{m}$ in place of $X_{m}$. Thus,
$\frac{S_{n+1}}{S_{n}}=\tau+o(n)$ with exponentially small $o(n)$. ∎

This generalizes the property of the Fibonacci numbers and the golden ratio
observed already by Kepler. The first result of this sort for general linear
recurrences is due to Poincare [9]. The same property holds for any recurrent
sequence with a cyclic initial vector, not just the standard one. However,
without some non-degeneracy conditions the limit ratio may not exist, and may
not coincide with the transition ratio even when it does exist [9]. This
happens because the initial vector $x_{0}$ may have zero projection on the
dominant eigenvector, and the asymptotic behavior is then determined by
subdominant eigenvalues and (generalized) eigenvectors. This is ruled out for
the standard sequence, and for the row sequences from Lemma 3 generally,
because $x_{0}$ is cyclic, and hence has a non-zero projection on every
eigenvector.

######  Example 5.

Using the Tribonacci recurrence $X_{n+3}=X_{n+2}+X_{n+1}+X_{n}$ we have the
standard sequence using the initial values $S_{2}=1$, $S_{1}=0$, and
$S_{0}=0$. We can estimate the transition ratio by taking ratios of
consecutive terms in the standard sequence. For example, $n=20$ gives
$\tau\approx\frac{S_{n+1}}{S_{n}}=\frac{66012}{35890}\approx 1.8393$. This can
be used as the initial guess for a non-linear numerical solver to get a more
precise value. Solving $z^{3}=z^{2}+z+1$ in Maple we find $\tau\approx
1.839286755...$

##  7 Error detection and correction

In this section, we illustrate error detection and correction algorithms for
cryptography with higher order recurrences. By the checking relations, for
large $n$ all consecutive entries in a row of the ciphertext matrix have
ratios close to $\tau$. Hence, if we know even a single correct entry in a row
we should be able, in principle, to recover the entire row. Subject to two
caveats. First, as we saw already in golden cryptography, the bounds in the
checking relations may not be tight enough to pick a single value. Either one
has to test all candidate values by trial and error, or transmit additional
check data (traditionally, the determinant) to determine them.

Second, to work from a single entry in a row we must know which entry is
correctly transmitted. If we do not know that by other means we need at least
two entries in each row to be correct. Then we can detect the correct pair
from the fact that their ratio is close to the appropriate power of the
transition ratio (determined by how far they are separated in the row). Once
this is done, the remaining row entries can be recovered as above. In the
second order case, having two correct entries in each row meant no errors at
all, and the determinant had to be used to make up for the missing information
when they did occur. In the higher order case there is enough built-in
redundancy to make transmission of additional check data less appealing. The
examples below illustrate some typical situations, when no extra data is
transmitted.

######  Example 6 (Single error, unknown location).

Consider the ciphertext matrix from Example 2 transmitted with a single error
in the top row. The received matrix is
$C^{*}=\begin{pmatrix}60861&41528&28373\\\ 68585&46798&31933\\\
68601&46809&31940\end{pmatrix}$. The transition ratio can be estimated as in
Example 5 and is $\tau\approx 1.465571232$. Calculation shows that
$\frac{c_{12}^{*}}{c_{13}^{*}}=\frac{41528}{28373}$ is the only consecutive
ratio that is not approximately $\tau$. Since $\frac{c_{11}^{*}}{c_{12}^{*}}$
is correct the error has to be in $c_{13}^{*}$. Taking the ratios of the
second and third column entries of $M_{15}=\begin{pmatrix}406&277&189\\\
277&189&129\\\ 189&129&88\end{pmatrix}$ we have by the checking relations
(20):

$1.465\approx\frac{189}{129}\leq\frac{c_{12}}{c_{13}}\leq\frac{129}{88}\approx
1.466,$

which gives

$28329\approx 41528\cdot\frac{88}{129}\leq c_{13}\leq
41528\cdot\frac{129}{189}\approx 28345.$

The checking range has $16$ possible values for $c_{13}$ that can be tried and
the one producing a coherent text upon decryption is selected. However, the
estimate obtained using the transition ratio, i.e. $41528\cdot\tau\approx
28335.7$ is much closer to the correct value $28337$ than the checking bounds,
and this is typical. Therefore, a spiral search algorithm centered around this
estimate will be faster, and will find the correct value after checking just
three candidates. Moreover, the $2$-Fibonacci sequence used here is Pisot, so
the checking range shrinks to a point with $n\to\infty$. For $n\geq 29$ it
contains a single integer. The correct value of $c_{13}$ (which becomes
$6,736,252$ when $n=29$ is used for encryption) can then be recovered
uniquely.

There is a tradeoff between having smaller ciphertexts (small $n$) and being
able to correct without trial and error (large $n$). Larger $n$ means greater
redundancy in the ciphertext, so one expects to have an easier time with
correction. However, as we know from Section 5.3, extra redundancy can be
reliably leveraged only when $L$ is Pisot.

######  Example 7 (Checking ranges).

Let $\sigma$ denote the second largest eigenmodulus of $L$ used in the proof
of Theorem 3. Tribonacci, $2$-Fibonacci and order $3$ Wielandt recurrences
have $\sigma\approx 0.74,\,0.83$ and $0.87$, respectively. The smallest $n$
for which the checking ranges are $<1$ in length are $19$, $29$, and $43$,
respectively. As expected, the smallest $n$ increases with $\sigma$. For many
other Pisot recurrences the value of $\sigma$ is even closer to $1$, so the
smallest such $n$ will be larger. For the Tribonacci recurrence the dependence
of the checking range $[a,b]$ on $n$ is shown in Table 1. As one can see, its
length is not quite monotone decreasing with $n$.

$n$ | $12$ | $16$ | $17$ | $19$
---|---|---|---|---
$a$ | $135,256.10$ | $1,547,924.82$ | $2,847,074.91$ | $9,631,589.62$
$b$ | $135,245.10$ | $1,547,923.40$ | $2,847,077.51$ | $9,631,588.74$
$b-a$ | $11.00$ | $1.42$ | $2.61$ | $0.87$
Table 1:  Checking ranges for the Tribonacci recurrence at various $n$.

######  Example 8 (Double error, unknown location).

Suppose the word EXTRATERRESTRIAL is encrypted using symmetric coding matrices
of the Tetranacci recurrence $X_{n+4}=X_{n+3}+X_{n+2}+X_{n+1}+X_{n}$ with the
standard initial vector and $n=5$. Two entries in the top row of the
ciphertext matrix are transmitted with errors, and the transmitted matrix is

$C^{*}=\begin{pmatrix}16460&8332&4123&2239\\\ 14955&7767&4025&2087\\\
16387&8510&4413&2282\\\ 15969&8292&4297&2226\\\ \end{pmatrix}\\!.$

The transition ratio of the Tetranacci sequence is $\tau\approx 1.927562$, and
the second eigenmodulus is $\sigma\approx 0.8182726$. The consecutive ratios
in the top row are $\frac{c_{11}}{c_{12}}\approx 1.9755$,
$\frac{c_{12}}{c_{13}}\approx 2.0208$, $\frac{c_{13}}{c_{14}}\approx 1.8439$,
and they are all incorrect. The square of the transition ratio is
$\tau^{2}\approx 3.715495$, and $\frac{c_{11}}{c_{13}}\approx 3.9922$,
$\frac{c_{12}}{c_{14}}\approx 3.7262$. The last ratio is close to the limit
value (correct and incorrect ratios are more clearly separated for larger
$n$), so we conclude that the errors are in $c_{11}$ and $c_{13}$ entries.

To recover the correct values we use the same approach as in Example 6. The
coding matrix is

$M_{5}=\begin{pmatrix}108&56&29&15\\\ 56&29&15&8\\\ 29&15&8&4\\\ 15&8&4&2\\\
\end{pmatrix}\\!.$

For $c_{11}$ the reference value is $c_{12}=8332$, and the corresponding
ranges are

$1.875\approx\frac{15}{8}\leq\frac{c_{11}}{c_{12}}\leq\frac{29}{15}\approx
1.9333,$

and

$15623\approx 8332\cdot\frac{15}{8}\leq c_{11}\leq
8332\cdot\frac{29}{15}\approx 16108.$

The case of $c_{13}$ is analogous with the reference value $c_{14}=2239$. The
starting value for the spiral search should again be $c_{12}\cdot\tau\approx
16060.4$, which is closer to the correct value $16046$ than the checking
bounds. About thirty candidate values would have to be tested, and, in this
case, it has to be done in combination with testing candidates for $c_{13}$.
Picking a larger $n$ would narrow down the checking ranges and make the
correction easier.

The correction algorithm is somewhat modified when the error location is
known, and, as already mentioned, more errors in the same row can be
corrected. In fact, one just needs to have a single correct entry in each row.
The next example also illustrates that, and the use of non-consecutive ratios
for error correction.

######  Example 9 (Triple error, known location).

As in the previous example, we encrypted EXTRATERRESTRIAL with the symmetric
coding matrices of the Tetranacci sequence and $n=5$. The transmitted
ciphertext matrix is

$C^{*}=\begin{pmatrix}16046&4513&7211&1337\\\ 14955&7767&4025&2087\\\
16387&8510&4413&2282\\\ 15969&8292&4297&2226\end{pmatrix}$

There are three errors in the top row, but $c_{11}$ is known to be transmitted
correctly. The rough estimates for the remaining entries are
$c_{12}\approx\frac{c_{11}}{\tau}\approx 8326$,
$c_{13}\approx\frac{c_{11}}{\tau^{2}}\approx 4321$, and
$c_{14}\approx\frac{c_{11}}{\tau^{3}}\approx 2239$.

The checking ranges are calculated by taking maximal and minimal ratios in the
corresponding columns of $M_{5}$.

$\displaystyle 8299.66\approx 16046\cdot\frac{29}{15}\leq c_{12}\leq
16046\cdot\frac{15}{8}\approx 8557.87$ $\displaystyle 4278.93\approx
16046\cdot\frac{15}{4}\leq c_{13}\leq 16046\cdot\frac{29}{8}\approx 4426.48$
$\displaystyle 2139.47\approx 16046\cdot\frac{15}{2}\leq c_{14}\leq
16046\cdot\frac{56}{8}\approx 2292.29$

The ranges are wide because $n$ is small, but they shrink to containing a
single integer for $n\geq 34$.

Additional check data can also be transmitted to avoid or narrow down trial
and error searches. In particular, one can use determinants to correct single
errors by solving a linear equation, or double errors by solving Diophantine
equations within the range of solutions narrowed down by the checking
relations as in [12]. However, this requires one to assume that all other
entries, and the determinant itself, are correctly transmitted. Considering
also the inefficiency of calculations with determinants in higher dimensions,
it seems more reasonable to transmit row sums of $C$ instead as additional
check data. For example, this would allow correcting a single error by solving
a linear equation without assuming that all other rows are correctly
transmitted.

##  8 Generation of the coding matrices

In this section, we review some approaches to generating coding matrices that
meet the conditions of Theorems 2 and 3, and hence are suitable for encryption
with error detection and correction.

###  8.1 Companion matrices

Generation is quite straightforward if one is content with using symmetric
coding matrices. When $L$ is a left companion matrix (9) then, by direct
computation, its eigenvectors are of the form
$\begin{pmatrix}{\lambda}^{k-1}&\dots&{\lambda}&1\end{pmatrix}^{T}$, where
${\lambda}$ is the eigenvalue. Therefore, if the characteristic polynomial of
$L$ has a simple positive dominant root $\tau$ the dominant eigenvector will
automatically have strictly positive entries, i.e. $L$ will be strong Perron-
Frobenius. Generation of such polynomials with integer coefficients is
discussed in [8]. Writing the polynomial as $f(z):=z^{k}-a_{k-1}z^{k-1}-\dots-
a_{1}z-a_{0}$, one can simply pick $a_{i}$ randomly from a range $[-M,N]$ and
select those that have small positive dominant roots, say $\tau<3$. The Pisot
condition can be used to further restrict selection.

Invertibility is ensured by restricting to $a_{0}\neq 0$. Moreover, left
companion matrices always have a cyclic vector, namely
$\begin{pmatrix}1&0&\dots&0\end{pmatrix}^{T}$, and, in fact, almost every
vector is cyclic. Finding cyclic vectors deterministically is discussed in
[3].

######  Example 10.

For this example we generated polynomials with $a_{i}$ selected from $[0,3]$.
Skipping those with $0$-$1$ coefficients we took

$f(z)=z^{4}-z^{3}-z^{2}-2z-1.$

Its dominant root is $\tau\approx 2.066$ and the second largest eigenmodulus
is $\sigma\approx 0.9582$, i.e. this polynomial is Pisot. Taking the standard
initial vector $x_{0}=\begin{pmatrix}1&0&0&0\end{pmatrix}^{T}$ we generate

$L=\begin{pmatrix}1&1&2&1\\\ 1&0&0&0\\\ 0&1&0&0\\\ 0&0&1&0\end{pmatrix}\
\text{and}\ M_{0}=\begin{pmatrix}5&2&1&1\\\ 2&1&1&0\\\ 1&1&0&0\\\
1&0&0&0\end{pmatrix}\\!.$

The last component of the key, positive integer $n$, can also be generated
randomly from a large range $[M,N]$. When it is selected the rows of $M_{0}$
provide initial values to generate the sequences $X_{m}$ recursively up to
$m=n+6$. In this case, we calculate for $n=10$ :

$\displaystyle
X_{m}=0,0,0,1,1,2,5,10,20,42,87,179,370,765,1580,3264,6744,\dots;$
$\displaystyle M_{10}=\begin{pmatrix}6744&3264&1580&765\\\
3264&1580&765&370\\\ 1580&765&370&179\\\ 765&370&179&87\end{pmatrix}\\!.$

###  8.2 Pisot polynomials

If one wishes to use only Pisot transition matrices there are more selective
methods to generate them without sieving through general polynomials. For
example, there is a complete description of Pisot polynomials with integer
coefficients and $1<\tau<2$ due to Amara, Boyd and Talmoudi [7, 10]. The set
of limit points of their dominant roots, called Pisot numbers, consists of two
infinite series $\phi_{r}$ and $\psi_{r}$ and one exceptional value $\chi$.
The Pisot polynomials for $\psi_{r}$ are none other than the characteristic
polynomials $\Psi_{r}(z)=z^{r+1}-z^{r}-\dots-z-1$ of the ($r+1$)-bonacci
recurrences. Pisot numbers in a neighborhood of $\psi_{r}$ are roots of
$z^{m}\,\Psi_{r}(z)\pm(z^{r+1}-1)$ or
$z^{m}\,\Psi_{r}(z)\pm\frac{z^{r}-1}{z-1}$ (for small $m$ we may have
$\tau>2$), with these polynomials either being themselves Pisot or becoming
Pisot after dividing out some trivial factors. There are similar descriptions
for Pisot numbers associated with $\phi_{r}$ and $\chi$. The (finitely many)
irregular Pisot numbers not covered are also known.

######  Example 11.

Consider polynomials $f_{m}(z)=z^{m}\,\Psi_{2}(z)-(z^{3}-1)$ associated with
the Tribonacci recurrence. They are Pisot if $m$ is odd, and
$\frac{f_{m}(z)}{z+1}$ are if $m$ is even [7]. We skip $m=1,2$, where
$\tau>2$, and for $m=3,4$ find:

$\displaystyle f_{3}(z)$ $\displaystyle=z^{6}-z^{5}-z^{4}-2z^{3}+1;\ \ \
\tau\approx 1.98139,\sigma\approx 0.94792$ $\displaystyle\frac{f_{4}(z)}{z+1}$
$\displaystyle=z^{6}-2z^{5}+z^{4}-2z^{3}+z^{2}-z+1;\ \ \ \tau\approx
1.91616,\sigma\approx 0.93460$

Note that some $a_{i}<0$, including the free term. Forming the left companion
matrices and selecting some cyclic vector $x_{0}$ one can calculate the
remaining key data as in Example 10.

###  8.3 Primitive matrices

Recall that a matrix with non-negative entries is called primitive when some
power of it has strictly positive entries. By a theorem of Perron, all
primitive matrices have the strong Perron-Frobenius property [13, 9.4]. One
can see that the primitivity only depends on where $0$ entries are located in
the matrix. Hence, to test for the primitivity it is sufficient to inspect
$0$-$1$ matrices. Those, in turn, can be associated to directed graphs (with
self-loops) as their adjacency matrices.

######  Definition 12.

A directed graph is called strongly connected if there is a directed path in
it from any vertex to any other vertex, and it is called acyclic if the
greatest common divisor of the lengths of directed cycles in it is $1$.

A $0$-$1$ matrix is primitive if and only if its directed graph is strongly
connected and acyclic [25, 2.4]. Thus, the primitivity of a matrix can be
checked quite easily. In particular, a $k\times k$ left companion matrix $L$
with non-negative coefficients $a_{i}\geq 0$ is primitive if and only if
$a_{0}>0$ and $a_{i}>0$ for some $i>0$ relatively prime to $k$. Directed
graphs of some left companion matrices are shown on Figure 1. All of them are
strongly connected, and all but c) are acyclic.

a) b) c) d)

Figure 1:  Directed graphs of left companion matrices of a) Tribonacci; b)
$2$-Fibonacci; c) recurrence with $a_{0}=a_{1}=1$, $a_{2}=0$; d)
$4$-Fibonacci.

Primitive $0$-$1$ matrices can be used as seeds to generate primitive matrices
with any non-negative entries because replacing entries by larger entries
preserves the primitivity. It also increases $\tau$, which can serve as a
limiting factor in a generation algorithm. Since $\tau$ is bounded above by
the matrix’s maximal row sum and by its maximal column sum [14, 2.1],
generation should favor sparse matrices with many zeros and low non-zero
entries. Imposing the Pisot condition narrows the selection further.

######  Example 12.

Starting with the order $3$ Wielandt left transition matrix
$\begin{pmatrix}0&1&1\\\ 1&0&0\\\ 0&1&0\end{pmatrix}$ we increase some of the
$0$ entries in it, and check for the size of $\tau$. One of the non-companion
matrices so generated is $L=\begin{pmatrix}0&1&1\\\ 1&2&1\\\
0&1&0\end{pmatrix}$. Although $\tau\approx 2.831>2$, it is not too large, and
in return this matrix is Pisot with a fairly small second eigenmodulus
$\sigma\approx 0.594$. The initial vector
$\begin{pmatrix}0&0&1\end{pmatrix}^{T}$ is cyclic for $L$, and
$M_{0}=\begin{pmatrix}1&1&0\\\ 3&1&0\\\ 1&0&1\end{pmatrix}$. The
characteristic polynomial of $L$ is $f(z)=z^{3}-2z^{2}-2z-1$, which means that
the recurrence is $X_{n+3}=2X_{n+2}+2X_{n+1}+X_{n}$. Since $L$ is not a left
companion matrix the rows of $M_{n}$ are formed by three (potentially)
different sequences satisfying this recurrence with the initial values given
by the rows of $M_{0}$, see (14). Generating them recursively up to the $6$-th
term we compute:

$\displaystyle X_{m}^{(2)}=0,1,1,4,11,31,88,249,705,\dots$ $\displaystyle
X_{m}^{(1)}=0,1,3,8,23,65,184,521,1475,\dots$ $\displaystyle
X_{m}^{(0)}=1,0,1,3,8,23,65,184,521,\dots;$ $\displaystyle
M_{6}=\begin{pmatrix}705&249&88\\\ 1475&521&184\\\
521&184&65\end{pmatrix}\\!.$

###  8.4 Right companion representation

The methods discussed above generated $M_{n}$ from left transition matrices.
However, one can use the alternative representation described in Section 4.2
instead, and start from a right companion matrix $R$, and an initial matrix
$M_{0}$. The benefit is that $M_{0}$ does not have to be computed from a
cyclic vector and can be generated randomly. The approach is based on the
following lemma.

######  Lemma 4.

Let $R$ be an invertible right companion matrix of the form (16) with the
strong Perron-Frobenius property. Let $M_{0}$ be any invertible matrix with
non-negative entries and set $M_{n}:=M_{0}R^{n}$. Then the left transition
matrix of $M_{n}$ also has the strong Perron-Frobenius property.

###### Proof.

By construction, $M_{n}$ are invertible. Set $L:=M_{0}RM_{0}^{-1}$, then $L$
is similar to $R$ and has the same eigenvalues with the same multiplicities.
In particular, it has the same simple dominant eigenvalue $\tau$ as $R$. We
just have to show that the corresponding eigenvector has strictly positive
entries. Let $\xi$ be the dominant eigenvector of $R$. Then
$LM_{0}\xi=M_{0}R\xi=\tau M_{0}\xi$, so $M_{0}\xi$ is the dominant eigenvector
of $L$. Since $\xi$ has strictly positive entries and $M_{0}$ has non-negative
entries by assumption, $M_{0}\xi$ also has non-negative entries. Moreover,
they can be $0$ only if $M_{0}$ has a row of all $0$-s, which contradicts its
invertibility. ∎

In the following example we use the transpose of a left companion matrix as
both $R$ and $M_{0}$.

######  Example 13.

Take $R=\begin{pmatrix}1&1&0\\\ 0&0&1\\\ 2&0&0\end{pmatrix}$ and $M_{0}:=R$.
It follows that $L=R$ and $M_{n}:=R^{n+1}$. Note that $L$ is not a left
companion matrix. The transition ratio is $\tau\approx 1.6956$, and the
corresponding eigenvector (computed with Maple) is approximately
$\begin{pmatrix}0.84781&0.58975&1\end{pmatrix}^{T}$. The coding matrices can
be generated as in Example 12.

##  9 Conclusions

We introduced a generalization of golden cryptography to higher order linear
recurrences, and gave explicit conditions for preserving its error correction
properties. We also described a number of ways to randomly generate coding
matrices that satisfy these conditions, and algorithms for error detection and
correction.

In the simpler case the coding matrices $M_{n}$ are symmetric and filled with
consecutive entries of a single recurrent sequence. The encryption key
consists, in addition to the index $n$, of $k$ coefficients of the recurrence
and $k$ initial values, where $k$ is the order of the recurrence. In the most
general case, the rows of $M_{n}$ are segments of different sequences, albeit
satisfying the same recurrence, and $k$ initial values are replaced by $k^{2}$
ones, $k$ for each row sequence. Additional parameters greatly improve the
security of encryption, which is no longer vulnerable to the known types of
brute force and chosen plaintext attacks. The tradeoff is the increased
computational burden, especially when $k$ and $n$ are large.

Although our coding matrices can be represented in the form
$M_{n}=L^{n}M_{0}$, their special recurrent structure ensures that matrix
multiplication is not needed to compute them. This makes the
encryption/decryption procedures computationally attractive, especially for
large $k$ and $n$. At the same time, our main results show that certain
spectral properties of $L$ play a central role in determining which coding
matrix sequences are feasible in practice. First, there is a tradeoff between
the size of the spectral radius $\tau$ of $L$ and the size of indices $n$ that
can be used without producing intractably large ciphertexts. Second, $L$ must
have the strong Perron-Frobenius property to induce the checking relations in
the ciphertext leveraged by the error detection and correction algorithms.
Finally, an even stronger Pisot condition on $L$ is needed to minimize trial
and error in those algorithms, and utilize encryption redundancy most
efficiently.

These restrictions, especially the last one, somewhat reduce the variety of
feasible coding matrices compared to merely formal considerations. In
particular, if we bound the sizes of both $\tau$ and $k$ then there are only
finitely many integer matrices $L$ that are strong Perron-Frobenius or Pisot.
However, their number grows quickly with $k$, and the additional freedom of
choosing the initial values still provides abundant means for ensuring
encryption security.

Finally, we presented a number of methods for generating feasible coding
matrices. Most of them favor cases where $L$ has non-negative entries.
However, the companion matrices of Pisot polynomials often have negative
entries, and finding systematic ways of generating strong Perron-Frobenius and
Pisot matrices of more general form with some negative entries is desirable.
Especially those that allow controlling the sizes of the spectral radius and
of the second largest eigenmodulus.

One may also wish to explore coding matrices of the form $M_{n}=L^{n}M_{0}$,
where no relation between $L$ and $M_{0}$ is assumed (in our setting $M_{0}$
is always generated by a single cyclic vector of $L$). In that case, the
entries of $M_{n}$ may no longer be terms of recurrent sequences, and hence
may be harder to compute. It is also unclear how one can establish the
checking relations in this generality. However, in some special cases, at
least, a version of them may still hold. For example, in [5] the right
companion matrix of the Tribonacci sequence is used as both $L$ and $M_{0}$,
and the row ratios of the ciphertext matrices are shown to approach some
rational functions of $\tau$. It is of interest to characterize classes of
pairs $L$, $M_{0}$ that admit such generalizations of the checking relations.

## References

  * [1] S. Akiyama, D. Kwon, Constructions of Pisot and Salem numbers with flat palindromes, Monatshefte für Mathematik, 155 (2008), no. 3-4, 265-275.
  * [2] D. Andrica, O. Bagdasar, Recurrent sequences, Springer, Cham, 2020.
  * [3] D. Augot, P. Camion, On the computation of minimal polynomials, cyclic vectors, and Frobenius forms, Linear Algebra and its Applications, 260 (1997), pp. 61-94.
  * [4] F. Bani-Ahmad, M. Shatnawi, N. Tahat, S. Shatnawi, A new kind of digital signature scheme using golden matrices based on factoring problem, International Journal of Pure and Applied Mathematics, 107 (2016), no. 1, 49-57.
  * [5] M. Basu, M. Das, Tribonacci matrices and a new coding theory, Discrete Mathematics, Algorithms and Applications, 6 (2014), no. 1, 17 pp.
  * [6] M. Basu, B. Prasad, The generalized relations among the code elements for Fibonacci coding theory, Chaos, Solitons & Fractals, 41 (2009), no. 5, pp. 2517-2525.
  * [7] D. Boyd, On beta expansions for Pisot numbers, Mathematics of Computation, 65 (1996) no. 214, pp. 841-860.
  * [8] A. Dubickas, M. Sha, Counting and testing dominant polynomials, Experimental Mathematics, 24 (2015), no. 3, 312-325.
  * [9] A. Fiorenza, G. Vincenzi, Limit of ratio of consecutive terms for general order-$k$ linear homogeneous recurrences with constant coefficients, Chaos, Solitons & Fractals, 44 (2011) no. 3, pp. 145-152.
  * [10] K. Hare, N. Sidorov, Conjugates of Pisot numbers, International Journal of Number Theory, 17 (2021) no. 6, pp. 1307-1321.
  * [11] K. Hoffman, R. Kunze, Linear algebra, Prentice-Hall, Englewood Cliffs, NJ, 1971.
  * [12] S. Koshkin, T. Styers, From golden to unimodular cryptography, Chaos, Solitons & Fractals, 105 (2017), pp. 208-214.
  * [13] P. Lancaster, Theory of Matrices, Academic Press, New York-London, 1969.
  * [14] H. Minc, Nonnegative Matrices, Wiley, New York, 1988.
  * [15] M. Mishra, P. Mishra, M. Adhikary, S. Kumar, Image encryption using Fibonacci-Lucas transformation, International Journal on Cryptography and Information Security, 2 (2012), no.3, pp. 131-141.
  * [16] M. Mohamed, Y. Mahdy, W. Abd El-Wahed Shaban, Confidential algorithm for golden cryptography using Haar wavelet, International Journal of Computer Science and Information Security, 12 (2014), no. 8, pp. 1-9.
  * [17] M. Nej, A. Satyanarayana Reddy, Exponents of primitive companion matrices, Rocky Mountain J. Math., 49 (5) (2019) 1633-1645.
  * [18] D. Noutsos, On Perron–Frobenius property of matrices having some negative entries, Linear Algebra and its Applications 412 (2006) 132-153.
  * [19] A. del Rey, G. Rodríguez Sánchez, On the Security of “Golden” Cryptography, International Journal of Network Security, 7 (2008), no.3, pp. 448-450.
  * [20] H. Schneider, Wielandt’s proof of the exponent inequality for primitive nonnegative matrices, Linear Algebra and its Applications, 353 (2002) 5-10.
  * [21] A. Stakhov, Fibonacci matrices, a generalization of the Cassini formula and a new coding theory. Chaos, Solitons and Fractals, 32 (2006), no. 3, pp. 56-66.
  * [22] A. Stakhov, The “golden” matrices and a new kind of cryptography, Chaos, Solitons & Fractals, 32 (2007), pp. 1138-1146.
  * [23] K. Sudha, A. Chandra Sekhar, P. Reddy, Cryptography protection of digital signals using some recurrence relations, International Journal of Computer Science and Network Security, 7 (2007), no.5, pp. 203-207.
  * [24] M. Tahghighi, S. Turaev, R. Mahmod, A. Jafaar and M. Said, The cryptanalysis and extension of the generalized golden cryptography, in Proceedings of the IEEE Conference on Open Systems, September 25 - 28, Langkawi, Malaysia, 2011, pp. 65-69.
  * [25] R. Varga, Matrix iterative analysis, Springer-Verlag, Berlin, 2000.