New representaions of elements of skew linear recurrent sequences via trace function based on the noncommutative Hamilton – Cayley theorem

M. A. Goltvanitsa

Matematičeskie voprosy kriptografii, Tome 12 (2021) no. 1, pp. 23-57

Résumé

Let $p$ be a prime number, $R=\mathrm{GR}(q^d,p^d)$ be a Galois ring of cardinality $q^d$ and characteristic $p^d$, where $q = p^r$, $S=\mathrm{GR}(q^{nd},p^d)$ be its extension of degree $n$ and $\mathrm{End}(_RS)$ be a ring of endomorphisms of the module $_RS$. A sequence $v$ over $S$ satisfying a recursion law $$ \forall i\in\mathbb{N}_0 \colon v(i+m)= \ \psi_{m-1}(v(i+m-1))+\ldots+\psi_0(v(i)), $$ $\psi_0,\ldots,\psi_{m-1}\in \mathrm{End}(_RS),$ is called skew linear recurrent sequence (LRS) over $S$; the maximal period of such sequence is equal to $(q^{mn}-1)p^{d-1}$. Using the trace function for representations of elements of skew LRS of maximal period we show that such LRS may be linearized if the coefficients in the recursion law are pairwise commuting.

Bibliographie

[1] Kurakin V. L., Kuzmin A. S., Mikhalev A. V., Nechaev A. A., “Lineinye rekurrentnye posledovatelnosti nad koltsami i modulyami”, Algebra-2, Itogi nauki i tekhniki, Ser. Sovr. matem. i ee pril., 10, 1994, 1–130

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

[3] Goltvanitsa M. A., Zaitsev S. N., Nechaev A. A., “Skruchennye lineinye rekurrentnye posledovatelnosti maksimalnogo perioda nad koltsami Galua”, Fundam. i prikl. matem., 17:3 (2011), 5–23 | MR

[4] Kurakin V. L., Mikhalev A. V., Nechaev A. A., Tsypyshev V. N., “Lineinye rekurrentnye posledovatelnosti nad abelevoi gruppoi i modulem”, Algebra-15, Itogi nauki i tekhniki, Ser. Covr. matem. i ee pril., 74, 2000, 1–30

[5] Chen E., Tseng D., “The splitting subspace conjecture”, Finite Fields Appl., 24 (2013), 15–28 | DOI | MR | Zbl

[6] Zeng G., Yang Y., Han W., Fan S., “Word oriented cascade jump $\sigma$-LFSR”, Lect. Notes Comput. Sci., 5527, 2009, 127–136 | DOI | MR | Zbl

[7] Goltvanitsa M. A., Nechaev A. A., Zaitsev S. N., “Skew LRS of maximal period over Galois rings”, Matematicheskie voprosy kriptografii, 4:2 (2013), 59–72 | MR

[8] Goltvanitsa M. A., “Digit sequences of skew linear recurrences of maximal period over Galois rings”, Matematicheskie voprosy kriptografii, 6:2 (2015), 19–27 | MR

[9] Goltvanitsa M. A., “The first digit sequence of skew linear recurrence of maximal period over Galois ring”, Matematicheskie voprosy kriptografii, 7:3 (2016), 5–18 | MR

[10] Goltvanitsa M. A., “Equidistant filters based on skew ML-sequences over fields”, Matematicheskie voprosy kriptografii, 9:2 (2018), 71–86 | MR

[11] Niederreiter H., “The multiple-recursive matrix method for pseudorandom number generation”, Finite Fiields Appl., 1 (1995), 3–30 | DOI | MR | Zbl

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

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

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

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

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

[17] Hasan S., Panario D., Wang Q., “Word-oriented transformation shift registers and their linear complexity”, Lect. Notes Comput. Sci., 7280, 2012, 190–201 | DOI | MR | Zbl

[18] Cohen S., Hasan S., Panario D., Wang Q., “An asymptotic formula for the number of irreducible transformation shift registers”, Linear Algebra Appl., 484 (2015), 46–62 | DOI | MR | Zbl

[19] Zaitcev S. N., “Description of maximal skew linear recurrences in terms of multipliers”, Matematicheskie voprosy kriptografii, 5:2 (2014), 57–70

[20] Zaitsev S. N., “Treugolnyi klass skruchennykh mnogochlenov maksimalnogo perioda”, Problemy peredachi informatsii, 52:4 (2016), 84–93 | MR

[21] Bishoi S., Haran H., Hasan S., “A note on the multiple-recursive matrix method for generating pseudorandom vectors”, Discr. Appl. Math., 222 (2017), 67–75 | DOI | MR | Zbl

[22] Goltvanitsa M. A., “A construction of skew LRS of maximal period over finite fields based on the defining tuples of factors”, Matematicheskie voprosy kriptografii, 5:2 (2014), 37–46

[23] Goltvanitsa M. A., “Ob odnom klasse skruchennykh lineinykh rekurrent maksimalnogo perioda nad koltsom Galua”, Cistemy vysokoi dostupnosti, 11:3 (2015), 28–49

[24] Hassan S., Panario D., Wang Q., “Nonlinear vectorial primitive recursive sequences”, Cryptogr. Commun., 10:6 (2018), 1075–1090 | DOI | MR

[25] Goltvanitsa\;M.A., “Non-commutative Hamilton – Cayley theorem and roots of characteristic polynomials of skew maximal period linear recurrences over Galois rings”, Matematicheskie voprosy kriptografii, 8:2 (2017), 65–76 | MR

[26] Goltvanitsa M. A., “Metody postroeniya skruchennykh lineinykh rekurrentnykh posledovatelnostei maksimalnogo perioda, baziruyuschiesya na faktorizatsii mnogochlenov Galua v koltse matrichnykh mnogochlenov”, Matematicheskie voprosy kriptografii, 10:4 (2019), 25–51

[27] McDonald B. R., Finite Rings with Identity, Markel Dekker, N. Y., 1974, 429 pp. | MR | Zbl

[28] Nechaev A. A., “Finite Rings with Applications”, Handbook of Algebra, 5, Elsevier B. V., 2008, 213–320 | DOI | MR | Zbl

[29] Sison V., Bases of the Galois ring $\mathrm{GR}(p^r, m)$ over the integer ring $\mathbb{Z}_{p^r}$, arXiv: 1410.0289v1

[30] Kurakin V. L., “Pervaya koordinatnaya posledovatelnost lineinoi rekurrenty maksimalnogo perioda nad koltsom Galua”, Diskretnaya matematika, 6:2 (1994), 88–100 | Zbl

[31] Lam T. Y., A First Course in Noncommutative Rings, Springer-Verlag, N. Y., 1991, 398 pp. | MR | Zbl

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

[33] Leng S., Algebra, Mir, M., 1968, 564 pp.

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

[35] Lidl R., Niderraiter G., Konechnye polya, Mir, M., 1988, 830 pp. | MR

[36] Suprunenko D. A., Tyshkevich R. I., Perestanovochnye matritsy, Nauka i tekhnika, Minsk, 1966, 104 pp. | MR