Abstract:
Consider a linear recurrent sequence of vectors $\left\{ \vec{v}_k \right\}_{k \geq 0}$ of length $n$ over $\mathbb{F}_{q}$ that satisfies the relation
$$
\forall k \in \mathbb{N} \;\;\; \vec{v}_{k+1} = Y \vec{v}_{k},
$$
where $Y$ is an $n \times n$-matrix from $GL_{n}{q}$. The period of this sequence equals the multiplicative order of the matrix $Y$, whose maximum is $q^n - 1$ [3, p. 363].
The paper solves a problem of constructing a matrix $Y$ with large multiplicative order that requires less arithmetic operations than standard matrix-vector multiplication to compute elements of this recurrent sequence and that generates a sequence with large period.
The main assertion of the paper is the following. Let $n = st, \; 1 < s, t < n$, then there exist $s \times s$-matrices $A_1, A_2, \ldots, A_s $ and $t \times t$-matrices $B_1, B_2, \ldots, B_s $ over the field $\mathbb{F}_{q}$ such that a matrix ${Y=\sum_{i=1}^s A_i \otimes B_i}$ from $GL_{n}{q}$ has the multiplicative order equal to $\frac{q^n - 1}{(s, q^t - 1)}$.
Fulltext:
PDF file (397 kB)