Pseudorandom sequence generators based on shift registers over finite chain rings

O. A. Kozlitin

Matematičeskie voprosy kriptografii, Tome 10 (2019) no. 3, pp. 49-65

Résumé

This article is based on a report made at the conference CTCrypt'2018. The paper contains an overview of the author's results related to the synthesis of pseudorandom sequence generators. For arbitrary $m$ and for Galois ring $R$ the maximum length $L_m(R)$ of cycles of bijective polynomial transformations of module $R^m$ is calculated. An algorithm is proposed that constructs polynomial transformations with a cycle of length $L_m(R)$. Some estimates of the periods and ranks of the output sequences of self-controlled $2$-dimensional linear shift registers ($2$-LFSR) are obtained. The frequencies of occurrence of signs on the cycles of the output sequences of $2$-LFSR are investigated. A new result is announced in the article, consisting of the fact that over Galois ring $R$ there are polynomial shift registers of length $m$, the state transition graph of which contains a cycle of length $L_m(R)$.

Bibliographie

[1] Viktorenkov V. E., “Orgraf polinomialnogo preobrazovaniya nad kommutativnym lokalnym koltsom”, Obozr. prikl. prom. matem., 7:2 (2000), 327

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

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

[4] Ermilov D. M., Kozlitin O. A., “Tsiklovaya struktura polinomialnogo generatora nad koltsom Galua”, Matematicheskie voprosy kriptografii, 4:1 (2013), 27–57 | DOI

[5] Ermilov D. M., Kozlitin O. A., “O stroenii grafa polinomialnogo preobrazovaniya koltsa Galua”, Matematicheskie voprosy kriptografii, 6:3 (2015), 47–73 | DOI | MR

[6] Kozlitin O. A., “Ispolzovanie 2-lineinogo registra sdviga dlya vyrabotki psevdosluchainykh posledovatelnostei”, Matematicheskie voprosy kriptografii, 5:1 (2014), 39–72 | DOI

[7] Kozlitin O. A., “O periodicheskikh svoistvakh polilineinykh registrov sdviga”, Diskretnaya matematika, 29:1 (2017), 27–50 | DOI | MR

[8] Kozlitin O. A., “Otsenka dliny maksimalnogo tsikla v grafe polinomialnogo preobrazovaniya koltsa Galua–Eizenshteina”, Diskretnaya matematika, 29:4 (2017), 41–58 | DOI

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

[10] Kozlitin O. A., “2-lineinyi registr sdviga nad koltsom Galua chetnoi kharakteristiki”, Matematicheskie voprosy kriptografii, 3:2 (2012), 27–61 | DOI

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

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

[13] Nechaev A. A., “Mnogomernye registry sdviga i slozhnost multiposledovatelnostei”, Trudy po diskretnoi matematike, 6 (2003), 150–165

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

[15] Nomura T., Fukuda A., “Linear recurring planes and two-dimensional cyclic codes”, Electr. Commun. Japan, 54:3 (1971), 23–30 | MR