Geodesic
Skew linear recurring sequences of maximal period over Galois rings
Fundamentalʹnaâ i prikladnaâ matematika, Tome 17 (2012) no. 3, pp. 5-23.

Voir la notice de l'article provenant de la source Math-Net.Ru

Let $p$ be a prime number, $R=GR(q^d,p^d)$ be a Galois ring of $q^d=p^{rd}$ elements and of characteristic $p^d$. Denote by $S=GR(q^{nd},p^d)$ a Galois extension of the ring $R$ of dimension $n$ and by $\check S$ the ring of all linear transformations of the module $_RS$. We call a sequence $v$ over the ring $S$ with the law of recursion $$ \text{for all}\ i\in\mathbb N_0\colon v(i+m)=\psi_{m-1}\bigl(v(i+m-1)\bigr)+\dots+\psi_0\bigl(v(i)\bigr),\quad\psi_0,\dots,\psi_{m-1}\in\check S $$ (i.e., a linear recurring sequence of order $m$ over the module ${}_{\check S}S$) a skew LRS over $S$. It is known that the period $T(v)$ of such a sequence satisfies the inequality $T(v)\le\tau=(q^{nm}-1)p^{d-1}$. If $T(v)=\tau$, then we call $v$ a skew LRS of maximal period (a skew MP LRS) over $S$. A new general characterization of skew MP LRS in terms of coordinate sequences corresponding to some basis of a free module $_RS$ is given. A simple constructive method of building a big enough class of skew MP LRS is stated, and it is proved that the linear complexity of some of them (the rank of the linear recurring sequence) over the module $_SS$ is equal to $mn$, i.e., to the linear complexity over the module $_RS$. 
@article{FPM_2012_17_3_a0,
     author = {M. A. Goltvanitsa and S. N. Zaitsev and A. A. Nechaev},
     title = {Skew linear recurring sequences of maximal period over {Galois} rings},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {5--23},
     publisher = {mathdoc},
     volume = {17},
     number = {3},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2012_17_3_a0/}
}
TY  - JOUR
AU  - M. A. Goltvanitsa
AU  - S. N. Zaitsev
AU  - A. A. Nechaev
TI  - Skew linear recurring sequences of maximal period over Galois rings
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2012
SP  - 5
EP  - 23
VL  - 17
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/FPM_2012_17_3_a0/
LA  - ru
ID  - FPM_2012_17_3_a0
ER  - 
%0 Journal Article
%A M. A. Goltvanitsa
%A S. N. Zaitsev
%A A. A. Nechaev
%T Skew linear recurring sequences of maximal period over Galois rings
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2012
%P 5-23
%V 17
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/FPM_2012_17_3_a0/
%G ru
%F FPM_2012_17_3_a0
M. A. Goltvanitsa; S. N. Zaitsev; A. A. Nechaev. Skew linear recurring sequences of maximal period over Galois rings. Fundamentalʹnaâ i prikladnaâ matematika, Tome 17 (2012) no. 3, pp. 5-23. http://geodesic.mathdoc.fr/item/FPM_2012_17_3_a0/

[1] Glukhov M. M., Elizarov V. P., Nechaev A. A., Algebra, v. 2, Gelios ARV, M., 2003

[2] Kurakin V. L., “Algoritm Berlekempa–Messi nad konechnymi koltsami, modulyami i bimodulyami”, Diskret. mat., 10:4 (1998), 3–34 | DOI | MR | Zbl

[3] Nechaev A. A., “Konechnye koltsa glavnykh idealov”, Mat. sb., 91(133):3 (1973), 350–366 | MR | Zbl

[4] Nechaev A. A., “Kod Kerdoka v tsiklicheskoi forme”, Diskret. mat., 1:4 (1989), 123–139 | MR | Zbl

[5] Nechaev A. A., “Lineinye rekurrentnye posledovatelnosti nad kommutativnymi koltsami”, Diskret. mat., 3:4 (1991), 105–127 | MR | Zbl

[6] Nechaev A. A., “Tsiklovye tipy lineinykh podstanovok nad konechnymi kommutativnymi koltsami”, Mat. sb., 184:3 (1993), 21–56 | MR | Zbl

[7] Ghorpade S. R., Hasan S. U., Kumari M., “Primitive polynomials, Singer cycles, and word-oriented linear feedback shift registers”, Des. Codes Cryptogr., 58:2 (2011), 123–134 | DOI | MR | Zbl

[8] Ghorpade S. R., Ram S., “Block companion Singer cycles, primitive recursive vector sequences, and coprime polynomial pairs over finite fields”, Finite Fields Appl., 17:5 (2011), 461–472 | DOI | MR | Zbl

[9] 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

[10] Kurakin V. L., Mikhalev A. V., Nechaev A. A., Tsypyschev V. N., “Linear and polylinear recurring sequences over Abelian groups and modules”, J. Math. Sci., 102:6 (2000), 4598–4626 | MR | Zbl

[11] Lidl R., Niederreiter H., Finite Fields, Encyclopedia of Mathematics and Its Applications, 20, Cambridge Univ. Press, Cambridge, 1983 | MR | Zbl

[12] McDonald B. R., Finite Rings with Identity, Marcel Dekker, New York, 1974 | MR | Zbl

[13] Nechaev A. A., “Finite rings with applications”, Handbook of Algebra, 5, ed. M. Hazewinkel, Elsevier, 2008, 213–320 | DOI | MR | Zbl

[14] Tsaban B., Vishne U., “Efficient linear feedback shift registers with maximal period”, Finite Fields Appl., 8:2 (2002), 256–267 | DOI | MR | Zbl

[15] Zeng G., Han W., He K., Word-oriented feedback shift register: $\sigma$-LFSR, Cryptology ePrint Archive: Report 2007/114 http://eprint.iacr.org/2007/114

[16] Zeng G., He K. C., Han W., “A trinomial type of $\sigma$-LFSR oriented toward software implementation”, Sci. China. Ser. F Information Sci., 50:3 (2007), 359–372 | MR | Zbl

[17] Zeng G., Yang Y., Han W., Fan S., “Word oriented cascade jump $\sigma$-LFSR”, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, 18th Int. Symp., AAECC-18 (Tarragona, Sapin, June 8–12, 2009), Proceedings, Lect. Notes Comput. Sci., 5527, ed. M. Bras-Amorós, Springer, Berlin, 2009, 127–136 | DOI | MR | Zbl