Methods of construction of skew linear recurrent sequences with maximal period based on the Galois polynomials factorization in the ring of matrix polynomials

M. A. Goltvanitsa

Matematičeskie voprosy kriptografii, Tome 10 (2019), pp. 25-51.

Résumé

Let $p$ be a prime, $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 an $R$-extension of degree $n$ and $\check{S}$ be an endomorphism ring of the module $_RS$. A sequence $v$ over $S$ with the recursion law $$ \forall i\in\mathbb{N}_0 :\;\;\;v(i+m)= \\psi_{m-1}(v(i+m-1))+...+\psi_0(v(i)),\;\;\;\psi_0,...,\psi_{m-1}\in \check{S},$$ is called a skew LRS over $S$ with a characteristic polynomial $\Psi(x) = x^m - \sum_{j=0}^{m-1}\psi_jx^j$. The maximal period $T(v)$ of such sequence equals $\tau = (q^{mn}-1)p^{d-1}$. In this article we propose some new methods for construction the polynomials $\Psi(x)$, which define the recursion laws of skew linear recurrent sequences of maximal period. These methods are based on the search in $\check{S}[x]$ the divisors for classic Galois polynomials of period $\tau$ over $R$.

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 | DOI | 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 | DOI | 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 | DOI | MR

[10] Goltvanitsa M. A., “Equidistant filters based on skew ML-sequences over fields”, Matematicheskie voprosy kriptografii, 9:2 (2018), 71–86 | DOI | 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 Fields 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 | DOI

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

[21] Bishoi S., 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 | DOI

[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 (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 | DOI | MR

[26] Lam T. Y., A First Course in Noncommutative Rings, Springer–Verlag, New York, 1991 | MR | Zbl

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

[28] Leng S., Algebra, Mir, M., 1968

[29] Nechaev A. A., “Tsiklovye tipy lineinykh podstanovok nad konechnymi kommutativnymi koltsami”, Matem. sb., 1993, no. 3, 21–56 | Zbl

[30] Lidl R., Niderraiter G., Konechnye polya, Mir, M., 1988 | MR

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