Fast Multiplication of a Matrix with Large Multiplicative Order by a Vector Over a Finite Field

D. M. Ivanov

Modelirovanie i analiz informacionnyh sistem, Tome 21 (2014) no. 2, pp. 39-49.

Résumé

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)}$.

Détail

Mots-clés : matrix-vector multiplication
Keywords: recurrent sequences.

Bibliographie

[1] Suprunenko D. A., Tyshkevich R. I., Perestanovochnye matritsy, Nauka i Tekhnika, 1966 (in Russian) | MR

[2] Vinberg E. B., Kurs algebry, Izdatelstvo MTsNMO, M., 2011 (in Russian)

[3] G. Birkhoff, T. Bartee, Modern applied algebra, McGraw-Hill Companies, 1970 | Zbl