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

Diskr. Mat., 1999 Volume 11, Issue 2, Pages 40–65 (Mi dm373)

This article is cited in 2 papers

Polynomial transformations of linear recurrent sequences over the ring $\mathbf Z_{p^2}$

V. L. Kurakin


Abstract: Let $u$ be a linear recurring sequence (LRS) over the ring $R=\mathbf Z_{p^2}$ with absolutely irreducible characteristic polynomial $F(x)\in R[x]$, and $\Phi(x_1,\ldots, x_s)\in R[x_1,\ldots, x_s]$. We give an upper bound for the rank (the degree of a minimal polynomial) of the sequence
$$ v(i) = \Phi(u(i), u(i+1),\ldots, u(i+s-1)) $$
over $R$. In the special case, where $\bar u$ is a maximal LRS over the field $\bar R=R/pR=GF(p)$, and $\Phi(x)\in R[x]$ is a polynomial in one variable of degree less than $p$, an exact formula for the rank of the sequence $v(i)=\Phi(u(i))$ over $R$ is obtained.
An upper bound for the rank of the sequence $v(i)= \Phi(u_1(i),\ldots,u_s(i))$ over $R$ is also given, where $u_t$ is a LRS over $R$ with absolutely irreducible characteristic polynomial $F_t(x)\in R[x]$, $t=1,\ldots,s$, and $\Phi(x_1,\ldots, x_s)\in R[x_1,\ldots, x_s]$. If $m_1,\ldots,m_s$ are pairwise relatively prime, $\bar u_t$ is a maximal LRS over the field $\bar R$, and the degree of $\Phi(x_1,\ldots, x_s)$ in $x_t$ is less than $\min\{p, m_t, m_t(p-2)/(p-1) + 1\}$, $t=1,\ldots,s$, the exact formula for the rank of the sequence $v$ over $R$ is obtained.

UDC: 519.7

Received: 14.06.1998

DOI: 10.4213/dm373


 English version:
Discrete Mathematics and Applications, 1999, 9:2, 185–210

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025