Periodical properties of multidimensional polynomial generator over Galois ring.~IV

O. A. Kozlitin

Matematičeskie voprosy kriptografii, Tome 13 (2022), pp. 69-95.

Résumé

$m$-dimensional polynomial substitutions of Galois rings consisting of $q^n$ elements and having the characteristic $p^n$ are investigated in this paper. The maximum cycle length in such substitutions is $L_m(R)=q^m(q^m-1)p^{n-2}$. Substitutions that contain an $L_m(R)$ length cycle are called full-length cycle substitutions (FLC-substitutions). A method permitting to construct FLC-substitutions is proposed. The number of substitutions that can be constructed by this method is estimated. The obtained results are applied to the synthesis of polynomial shift registers with a given cyclic structure.

Bibliographie

[1] Glukhov M.M., Elizarov V.P., Nechaev A.A., Algebra, Uchebnik, 2-e izd., ispr. i dop., Lan, SPb., 2015, 608 pp.

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

[3] Anashin V.S., “Uniformly distributed sequences in computer algebra or how to construct program generators of random numbers”, J. Math. Sciences, 89:4 (1998), 1355–1390 | DOI | MR

[4] Larin M.V., “Tranzitivnye polinomialnye preobrazovaniya kolets vychetov”, Diskretnaya matematika, 14:2 (2002), 20–32

[5] Viktorenkov V.E., “O stroenii orgrafov polinomialnykh preobrazovanii nad konechnymi kommutativnymi koltsami s edinitsei”, Diskretnaya matematika, 29:3 (2017), 3–23

[6] Viktorenkov V.E., “Tsiklovaya struktura sluchainykh podstanovok na mnozhestve dvukhtsvetnykh elementov. I”, Matematicheskie voprosy kriptografii, 10:3 (2019), 9–32 | DOI | MR

[7] Viktorenkov V.E., “Tsiklovaya struktura sluchainykh podstanovok na mnozhestve dvukhtsvetnykh elementov. II”, Matematicheskie voprosy kriptografii, 12:1 (2021), 5–21 | DOI | MR

[8] Ermilov D.M., “Svoistva polinomialnykh generatorov s vykhodnoi posledovatelnostyu naibolshego perioda nad koltsom Galua”, Prikladnaya diskretnaya matematika, 2015, no. 1(27), 52–61

[9] Ermilov D.M., “Kolichestvo polinomialnykh preobrazovanii maksimalnogo perioda nad koltsami Galua nechetnoi kharakteristiki”, Matematicheskie voprosy kriptografii, 9:4 (2018), 85–100 | DOI | MR

[10] Elizarov V.P., Konechnye koltsa. Osnovy teorii, Gelios-ARV, M., 2006, 304 pp.

[11] Kozlitin O.A., “Periodicheskie svoistva mnogomernykh polinomialnykh preobrazovanii nad koltsom Galua — Eizenshteina”, Matematicheskie voprosy kriptografii, 13:1 (2022), 69–99 | DOI | MR

[12] Kozlitin O.A., “Periodicheskie svoistva mnogomernogo polinomialnogo generatora nad koltsom Galua. I”, Matematicheskie voprosy kriptografii, 9:3 (2018), 61–98 | DOI | MR

[13] Kozlitin O.A., “Periodicheskie svoistva mnogomernogo polinomialnogo generatora nad koltsom Galua, II”, Matematicheskie voprosy kriptografii, 11:1 (2020), 63–100 | MR

[14] Kozlitin O.A., “Periodicheskie svoistva mnogomernogo polinomialnogo generatora nad koltsom Galua, III”, Matematicheskie voprosy kriptografii, 11:4 (2020), 49–76 | MR

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

[16] Brawley J.V., Mullen G.L., “Functions and Polynomials over Galois Ring”, J. Numb. Theory, 1992, no. 41, 156–166 | DOI | MR

[17] Asanov M.O., Baranskii V.A., Rasin V.V., Diskretnaya matematika: grafy, matroidy, algoritmy, Uchebnoe posobie, 2-e izd., ispr. i dop., Lan, Sankt-Peterburg – Moskva – Krasnodar, 2010, 368 pp.

[18] Rozhkov M.I., “O nekotorykh klassakh nelineinykh registrov sdviga, obladayuschikh odinakovoi tsiklovoi strukturoi”, Diskretnaya matematika, 22:2 (2010), 96–119 | DOI

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

[20] Kozlitin O.A., “Generatory psevdosluchainykh posledovatelnostei, ispolzuyuschie registrovye preobrazovaniya konechnykh tsepnykh kolets”, Matematicheskie voprosy kriptografii, 10:3 (2019), 49–65 | DOI | MR