Representations of skew linear recurrent sequences of maximal period over finite field

M. A. Goltvanitsa

Matematičeskie voprosy kriptografii, Tome 14 (2023) no. 1, pp. 27-43

Résumé

Let $p$ be a prime number, $R=\mathrm{GF}(q)$ be a finite field, where $q = p^r$, $S=\mathrm{GF}(q^{n})$ be its extension of degree $n$ and $\check{S}$ be a ring of linear transforms of the vector space ${}_RS$. A sequence $v$ over $S$ with a recursion law of the form $$ \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\check{S}, $$ is called skew linear recurrent sequence over $S$ of order $m$ with the characteristic polynomial $\Psi(x) = x^m - \sum_{j=0}^{m-1}\psi_jx^j$. It is well known that maximal period of such sequence is equal to $q^{mn}-1$. Let $v$ be a skew LRS of maximal period over $S$, $J$ be an arbitrary ring with identity $\mathbf{e}$ such that $q\mathbf{e}$ is not a zero divisor and $f: S \to J$ be a map. Below under certain conditions we describe the annihilator of the sequence $f(v)$.

Bibliographie

[1] Lidl R., Niderraiter G., Konechnye polya, Mir, M., 1988, 830 pp.

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

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

[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] Niederreiter H., “The multiple-recursive matrix method for pseudorandom number generation”, Finite Fields Appl., 1:1 (1995), 3–30 | DOI | MR | Zbl

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

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

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

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

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

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

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

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

[14] 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 | Zbl

[15] Goltvanitsa M.A., “Skruchennye $\sigma$-razdelimye lineinye rekurrentnye posledovatelnosti maksimalnogo perioda”, Matematicheskie voprosy kriptografii, 13:1 (2022), 33–67 | DOI | MR

[16] 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 | DOI | MR | Zbl

[17] 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 | Zbl

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

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

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

[21] 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 | Zbl

[22] 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 | Zbl

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

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

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

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

[27] 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 | Zbl

[28] Goltvanitsa M.A., “Novye predstavleniya znakov skruchennykh LRP pri pomoschi funktsii sled, baziruyuschiesya na nekommutativnoi teoreme Gamiltona – Keli”, Matematicheskie voprosy kriptografii, 12:1 (2021), 7–22 | DOI | MR

[29] Kurakin V.L., “Predstavleniya lineinykh rekurrentnykh posledovatelnostei maksimalnogo perioda nad konechnym polem”, Diskretnaya matematika, 7:2 (1995), 34–39 | Zbl

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

[31] Kuzmin A.S., Kurakin V.L., Nechaev A.A., “Psevdosluchainye i polilineinye posledovatelnosti”, Trudy po diskretnoi matematike, 1 (1997), 139–202 | Zbl

[32] Kamlovskii O.V., “Otsenki chisla poyavlenii vektorov na tsiklakh lineinykh rekurrentnykh posledovatelnostei nad konechnym polem”, Diskretnaya matematika, 20:4 (2008), 102–112 | DOI | MR | Zbl

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