RUS  ENG
Full version
JOURNALS // Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] // Archive

Mat. Vopr. Kriptogr., 2023 Volume 14, Issue 1, Pages 27–43 (Mi mvk429)

Representations of skew linear recurrent sequences of maximal period over finite field

M. A. Goltvanitsa

LLC «Certification Research Center», Moscow

Abstract: Let $p$ be a prime number, $R=\mathrm{GF}(q)$ be a finite field, where $q = p^r$, $S=\mathrm{GF}(q^{n})$ be its extension of degree $n$ and $\check{S}$ be a ring of linear transforms of the vector space ${}_RS$. A sequence $v$ over $S$ with a recursion law of the form
$$ \forall i\in\mathbb{N}_0 \colon v(i+m)= \psi_{m-1}(v(i+m-1))+\ldots+\psi_0(v(i)), \psi_0,\ldots,\psi_{m-1 }\in\check{S}, $$
is called skew linear recurrent sequence over $S$ of order $m$ with the characteristic polynomial $\Psi(x) = x^m - \sum_{j=0}^{m-1}\psi_jx^j$. It is well known that maximal period of such sequence is equal to $q^{mn}-1$. Let $v$ be a skew LRS of maximal period over $S$, $J$ be an arbitrary ring with identity $\mathbf{e}$ such that $q\mathbf{e}$ is not a zero divisor and $f: S \to J$ be a map. Below under certain conditions we describe the annihilator of the sequence $f(v)$.

Key words: finite field, ML-sequence, skew LRS, rank, annihilator.

UDC: 519.113.6+519.719.2

Received 27.V.2022

DOI: 10.4213/mvk429



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025