RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2000 Volume 12, Issue 3, Pages 3–36 (Mi dm342)

This article is cited in 4 papers

Polynomial transformations of linear recurrent sequences over finite commutative rings

V. L. Kurakin


Abstract: Let $u$ be a linear recurring sequence (LRS) over a finite commutative local ring $R$ with identity, and let $\Phi(x)\in R[x]$. We find a characteristic polynomial $H(x)$ and prove an upper estimate for the rank (linear complexity) over $R$ of the sequence $v=\Phi(u)$. If $\bar u$ is an $m$-sequence over the residue field $\bar R=R/J(R)=GF(q)$ of the ring $R$ and $\deg\Phi(x)\le q-1$, then this estimate is attained and $H(x)$ is a minimal polynomial of $v$. Analogous results are obtained for the sequence $v=\Phi(u_1, \ldots, u_K)$ which is a polynomial transform of $K$ linear recurrences $u_1, \ldots, u_K$ over $R$.

UDC: 519.7

Received: 15.10.1999

DOI: 10.4213/dm342


 English version:
Discrete Mathematics and Applications, 2000, 10:4, 333–366

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025