Polynomial transformations of linear recurrent sequences over finite commutative rings

V. L. Kurakin

Diskretnaya Matematika, Tome 12 (2000) no. 3, pp. 3-36.

Résumé

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$.

Bibliographie

[1] Atya M., Makdonald I., Vvedenie v kommutativnuyu algebru, Mir, Moskva, 1972 | MR

[2] Burbaki N., Kommutativnaya algebra, Mir, Moskva, 1971 | MR

[3] Van der Varden B. L., Algebra, Nauka, Moskva, 1979 | MR

[4] Glukhov M. M., Elizarov V. P., Nechaev A. A., Algebra, Chast II, Moskva, 1991 | Zbl

[5] Zarisskii O., Samyuel P., Kommutativnaya algebra, IL, Moskva, 1963

[6] Kurakin V. L., “Predstavleniya nad koltsom $Z_{p^n}$ lineinoi rekurrentnoi posledovatelnosti maksimalnogo perioda nad polem $GF(p)$”, Diskretnaya matematika, 4:4 (1992), 96–116 | MR | Zbl

[7] Kurakin V. L., “Polinomialnye preobrazovaniya lineinykh rekurrentnykh posledovatelnostei nad koltsom $Z_{p^2}$”, Diskretnaya matematika, 11:2 (1999), 40–65 | MR | Zbl

[8] Lidl R., Niderraiter G., Konechnye polya, t. 1, 2, Mir, Moskva, 1988 | Zbl

[9] Nechaev A. A., “Lineinye rekurrentnye posledovatelnosti nad kommutativnymi koltsami”, Diskretnaya matematika, 3:4 (1991), 105–127 | MR

[10] Sachkov V. N., Vvedenie v kombinatornye metody diskretnoi matematiki, Nauka, Moskva, 1982 | MR | Zbl

[11] Bernasconi J., Günter C. G., “Analysis of a nonlinear feedforward logic for binary sequence generators”, Lect. Notes Comput. Sci., 219, 1986, 161–166 | Zbl

[12] Brynielsson L., “On the linear complexity of combined shift register sequences”, Lect. Notes Comput. Sci., 219, 1986, 156–160 | Zbl

[13] Chan A. H., Goresky M., Klapper A., “On the linear complexity of feedback registers”, IEEE Trans. Inform. Theory, 36, no. 3, 1990, 640–644 | MR | Zbl

[14] GolićS. D., “On the linear complexity of functions of periodic $GF(q)$ sequences”, IEEE Trans. Inform. Theory, 35, no. 1, 1989, 69–75 | MR

[15] Herlestam T., “On the complexity of functions of linear shift register sequences”, Int. Symp. Inform. Theory, Les Arc, France, 1982

[16] Herlestam T., “On functions of linear shift register sequences”, Lect. Notes Comput. Sci., 219, 1986, 119–129 | MR | Zbl

[17] Key E. L., “An analysis of the structure and complexity of nonlinear binary sequence generators”, IEEE Trans. Inform. Theory, 22, no. 6, 1976, 732–736 | Zbl

[18] Klapper A., “The vulnerability of geometric sequences based on fields of odd characteristic”, J. Cryptology, 7 (1994), 33–51 | DOI | MR | Zbl

[19] Kurakin V. L., Kuzmin A. S., Mikhalev A. V., Nechaev A. A., “Linear recurring sequences over rings and modules”, J. Math. Sci., 76: 6 (1995), 2793–2915 | DOI | MR | Zbl

[20] Lu P., Song G., “Feasible calculation of the generator for combined LFSR sequences”, Lect. Notes Comput. Sci., 508, 1991, 86–95 | MR | Zbl

[21] Lu P., Song G., Zhou J., “Tenzor product with application to linear recurring sequences”, J. Math. Res. Exposition, 12:4 (1992), 551–558 | MR | Zbl

[22] Rueppel R. A., Staffelbach O. J., “Products of linear recurring sequences with maximum complexity”, IEEE Trans. Inform. Theory, 33, no. 1, 1987, 126–131

[23] Selmer E. S., Linear Recurrence Relations Over Finite Fields, Univ. Bergen, Bergen, 1966

[24] Vajda I., Nemetz T., “Substitution of characters in $q$-ary $m$-sequences”, Lect. Notes Comput. Sci., 508, 1991, 96–105 | MR | Zbl

[25] Zierler N., Mills W. H., “Products of linear recurring sequences”, J. Algebra, 27:1 (1973), 147–157 | DOI | MR | Zbl