Skew $\sigma$-splittable linear recurrent sequences with maximal period

M. A. Goltvanitsa

Matematičeskie voprosy kriptografii, Tome 13 (2022) no. 1, pp. 33-67

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 $\sigma$ be a Frobenius automorphism of $S$ over $R$. We study sequences $v$ over $S$ satisfying recursion laws of the form $$\forall i\in\mathbb{N}_0 \colon v(i+m) = s_{m - 1}\sigma^{k_{m-1}}(v(i+m-1))+\ldots+s_1\sigma^{k_1}(v(i+1)) + s_0\sigma^{k_0}(v(i)),$$ where $s_0,\ldots,s_{m-1}\in S, k_{0},\ldots, k_{m-1}\in \mathbb{N}_{0}$. We say that $v$ is $\sigma$-splittable skew linear recurrent sequence (LRS) over $S$ of order $m$. The period of such LRS is not greater than $(q^{mn}-1)p^{d-1}$. We obtain neccessary and sufficient conditions for $\sigma$-splittable skew LRS to have maximal period. We prove that under some conditions $\sigma$-splittable skew LRS are non-linearized skew LRS. Also we consider linear complexity of such sequences and uniqueness of minimal polynomial over $S$.

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 | Zbl

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

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

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

[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] Goltvanitsa M. A., “Ob odnom klasse skruchennykh lineinykh rekurrent maksimalnogo perioda nad koltsom Galua”, Sistemy vysokoi dostupnosti, 11:3 (2015), 28–49

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

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

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

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

[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 | MR | Zbl

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

[28] McDonald B. R., Finite Rings with Identity, Markel Dekker, New York, 1974, 429 pp. | MR | Zbl

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

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

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

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

[33] Nechaev A. A., “Lineinye rekurrentnye posledovatelnosti nad kommutativnymi koltsami”, Diskretnaya matematika, 3:4 (1991), 107–121