This article is cited in 10 papers

Skew LRS of maximal period over Galois rings

M. A. Goltvanitsa^a, A. A. Nechaev^b, S. N. Zaitsev<sup>a

a</sup> Moscow State Technical University of Radio Engineering, Electronics and Automatics, Moscow
^b Academy of Cryptography of the Russian Federation, Moscow

Abstract: Let $p$ be a prime number, $R=\mathrm{GR}(q^d,p^d)$ be a Galois ring with $q^d=p^{rd}$ elements and characteristic $p^d$. Denote by $S=\mathrm{GR}(q^{nd},p^d)$ a Galois extension of the ring $R$ of dimension $n$ and by $\breve S$ the ring of all linear transformations of the module $_RS$. A sequence $v$ over the ring $S$ satisfying the recursion $\forall i\in\mathbb N_0\colon v(i+m)=\psi_{m-1}(v(i+m-1))+\dots+\psi_0(v(i))$, $\psi_0,\dots,\psi_{m-1}\in\breve S$, is called a skew LRS over $S$ with a characteristic polynomial $\Psi(x)=x^m-\sum_{t=0}^{m-1}\psi_tx^t\in\breve S[x]$. We investigate the problem of construction the polynomials $\Psi$ generating LRS $v$ with the maximal possible period $\tau=(q^{mn}-1)p^{d-1}$.

Key words: Galois ring, Frobenius automorphism, skew linear recurrence of maximal period, skew MP-polynomial, rank of a sequence.

UDC: 512.53+519.113.6

Received 18.IX.2012

Language: English

DOI: 10.4213/mvk83