Kurakin, V. L. Polynomial transformations of linear recurring sequences over \(\mathbb{Z}_{p^2}\). (English. Russian original) Zbl 1001.11006 Discrete Math. Appl. 9, No. 2, 185-210 (1999); translation from Diskret. Mat. 11, No. 2, 40-65 (1999). Summary: Let \(u\) be a linear recurring sequence (LRS) over the ring \(R= \mathbb{Z}_{p^2}\) with absolutely irreducible characteristic polynomial \(F(x)\in R[x]\), and \(\Phi(x_1,\dots, x_s)\in R[x_1,\dots, x_s]\). We give an upper bound for the rank (the degree of a minimal polynomial) of the sequence \[ \nu(i)= \Phi(u(i), u(i+1),\dots, u(i+s-1)) \] over \(R\). In the special case where \(\overline{u}\) is a maximal LRS over the field \(\overline{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 \(\nu(i)= \Phi(u(i))\) over \(R\) is obtained. An upper bound for the rank of the sequence \(\nu(i)= \Phi(u_1(i),\dots, 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,\dots, s\), and \(\Phi(x_1,\dots, x_s)\in R[x_1,\dots,x_s]\). If \(m_1,\dots, m_s\) are pairwise relatively prime, \(\overline{u}_t\) is a maximal LRS over the field \(\overline{R}\), and the degree of \(\Phi(x_1,\dots, x_s)\) in \(x_t\) is less than \(\min \{p,m_t,m_t(p-2)/(p-1)+ 1\}\), \(t= 1,\dots, s\), then the exact formula for the rank of the sequence \(\nu\) over \(R\) is obtained. Cited in 2 Documents MSC: 11B37 Recurrences 94A55 Shift register sequences and sequences over finite alphabets in information and communication theory 11B50 Sequences (mod \(m\)) 11T99 Finite fields and commutative rings (number-theoretic aspects) Keywords:polynomial transformations; linear recurring sequence; upper bound; rank; degree of a minimal polynomial PDFBibTeX XMLCite \textit{V. L. Kurakin}, Discrete Math. Appl. 9, No. 2, 185--210 (1999; Zbl 1001.11006); translation from Diskret. Mat. 11, No. 2, 40--65 (1999) Full Text: DOI