×

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.

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)
PDFBibTeX XMLCite
Full Text: DOI