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

Mat. Vopr. Kriptogr., 2014 Volume 5, Issue 2, Pages 57–70 (Mi mvk117)

This article is cited in 5 papers

Description of maximal skew linear recurrences in terms of multipliers

S. N. Zaitsev

LLC "Certification Research Center", Moscow

Abstract: Let $P=\mathrm{GF}(q)$ be a field, $F=\mathrm{GF}(q^n)$ be an extension of $P$. We construct a wide class of skew MP-polynomials over $F$ by the description of multipliers of skew MP LRS. For $P$-skew MP LRS $v$ over $F$ we call linear transformation $\psi$ (generalized) multiplier if there exists a number $l\geq0$ such that $\psi(v(i))=v(i+l)$, $i\geq0$. Denote by $\mathfrak M(v)^*$ the set of all multipliers of a skew MP LRS $v$, and $\mathfrak M(v)=\mathfrak M(v)^*\cup\{0\}$. It is proved that $\mathfrak M(v)$ is a field and $\mathfrak M(v)\cong F$ if and only if $v$ is linearized. Sufficient conditions for $\mathfrak M(v)\cong P$ are given. It is proved that for any $P$-skew MP LRS $v$ there exists a transformation $\psi$ such that the sequence $\psi(v)$ is $\mathfrak M(v)$-skew MP LRS of the same order, and for any field $K<F$ there exists MP LRS $v$ such that $\mathfrak M(v)\cong K$.

Key words: skew linear recurrence, skew polynomial of maximal period, generalized multiplier, maximal non-reducible sequence.

UDC: 519.624+519.113.6

Received 25.IX.2013

Language: English

DOI: 10.4213/mvk117



© Steklov Math. Inst. of RAS, 2024