Быстрое умножение матрицы с большим мультипликативным порядком на вектор над конечным полем

Д. М. Иванов

Ярославский государственный университет им. П. Г. Демидова, 150000 Россия, г. Ярославль, ул. Советская, 14

Аннотация: Рассмотрим линейную рекуррентную последовательность векторов $\left\{ \vec{v}_k \right\}_{k \geq 0}$ длины $n$ с элементами из $\mathbb{F}_{q}$, для которой верно соотношение
$$ \forall k \in \mathbb{N} \;\;\; \vec{v}_{k+1} = Y \vec{v}_{k}, $$
где $Y$ — это $n \times n$-матрица из $GL_{n}{q}$. Период этой последовательности будет равен мультипликативному порядку матрицы $Y$, максимально возможным значением которого будет $q^n - 1$ [3, c. 363].
В статье решается задача построения матрицы $Y$ с большим мультипликативным порядком, которая позволяла бы вычислять элементы последовательности за меньшее количество арифметических операций, чем стандартное умножение матрицы на вектор, и при этом порождала бы последовательности с большим периодом.
Главное утверждение статьи звучит следующим образом. Пусть $n = st, \; 1 < s, t < n$. Тогда существуют $s \times s$-матрицы $A_1, A_2, \ldots, A_s $ и $t \times t$-матрицы \linebreak $B_1, B_2, \ldots, B_s $ над полем $\mathbb{F}_{q}$ такие, что матрица ${Y=\sum_{i=1}^s A_i \otimes B_i}$ из $GL_{n}{q}$ имеет мультипликативный порядок $\frac{q^n - 1}{(s, q^t - 1)}$.

Ключевые слова: умножение матрицы на вектор, рекуррентные последовательности.

УДК: 512.643.8

Поступила в редакцию: 03.02.2014