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

Mat. Vopr. Kriptogr., 2022 Volume 13, Issue 1, Pages 33–67 (Mi mvk401)

This article is cited in 1 paper

Skew $\sigma$-splittable linear recurrent sequences with maximal period

M. A. Goltvanitsa

LLC «Certification Research Center», Moscow

Abstract: Let $p$ be a prime number, $R=\mathrm{GR}(q^d,p^d)$ be a Galois ring of cardinality $q^d$ and characteristic $p^d$, where $q = p^r$, $S=\mathrm{GR}(q^{nd},p^d)$ be its extension of degree $n$ and $\sigma$ be a Frobenius automorphism of $S$ over $R$. We study sequences $v$ over $S$ satisfying recursion laws of the form
$$\forall i\in\mathbb{N}_0 \colon v(i+m) = s_{m - 1}\sigma^{k_{m-1}}(v(i+m-1))+\ldots+s_1\sigma^{k_1}(v(i+1)) + s_0\sigma^{k_0}(v(i)),$$
where $s_0,\ldots,s_{m-1}\in S, k_{0},\ldots, k_{m-1}\in \mathbb{N}_{0}$. We say that $v$ is $\sigma$-splittable skew linear recurrent sequence (LRS) over $S$ of order $m$. The period of such LRS is not greater than $(q^{mn}-1)p^{d-1}$. We obtain neccessary and sufficient conditions for $\sigma$-splittable skew LRS to have maximal period. We prove that under some conditions $\sigma$-splittable skew LRS are non-linearized skew LRS. Also we consider linear complexity of such sequences and uniqueness of minimal polynomial over $S$.

Key words: Galois ring, Frobenius automorphism, ML-sequence, skew LRS, recursion law.

UDC: 519.113.6+512.714+519.719.2

Received 12.V.2021

DOI: 10.4213/mvk401



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024