On the structure of digraphs of polynomial transformations over finite commutative rings with unity

V. E. Viktorenkov

Diskretnaya Matematika, Tome 29 (2017) no. 3, pp. 3-23.

Résumé

The paper describes structural characteristics of the digraph of an arbitrary polynomial transformation of a finite commutative ring with unity. A classification of vertices of the digraph is proposed: cyclic elements, initial elements, and branch points are described. Quantitative results on such objects and heights of vertices are given. Besides, polynomial transformations are shown to have cycles whose lengths coincide with the lengths of cycles of the induced polynomial transformation over the field $R/\Re$, where $\Re$ is the radical of the finite commutative local ring $R$.

Détail

Keywords: digraph, polynomial transformation, finite commutative ring.

Bibliographie

[1] Anashin V. S., “Ravnomerno raspredelennye posledovatelnosti tselykh $p$-adicheskikh chisel”, Matem. zametki, 55:2 (1994), 3–46 | MR | Zbl

[2] Knut D., Iskusstvo programmirovaniya, Nauka, M., 1977, 728 pp.; Knuth D., The Art of Computer Programming, Addison Wesley, 1969, 624 pp. | MR | Zbl

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

[4] Blum L., Blum M., Shub M., “Comparison of Two Pseudo-Random Number Generators”, Advances in Cryptology, eds. Chaum D., Rivest R.L., Sherman A.T., Springer, Boston, 1983, 61–78 | DOI

[5] Eichenauer J., Lehn J., “A non-linear congruential pseudo random number generator”, Stat. Hefte, 27:1 (1986), 315–326 | DOI | MR | Zbl

[6] Eichenauer J., Lehn J., “On the structure of quadratic congruential sequences”, Manuscripta Math, 58:1–2 (1987), 129–140 | DOI | MR | Zbl

[7] Eichenauer J., Lehn J., Topuzoglu A., “A nonlinear congruential pseudorandom number generator with power of two modulus”, Math. Comput., 51:184 (1988), 757–759 | DOI | MR | Zbl

[8] Eichenauer J., Topuzoglu A., “On the period length of congruential pseudorandom number sequences generated by inversions”, J. Comput. Appl. Math., 31:1 (1990), 87–96 | DOI | MR | Zbl

[9] Eichenauer J., “Inversive congruential pseudorandom numbers: a tutorial”, Int. Statist. Rev., 60 (1992), 167–176 | DOI | Zbl

[10] Eichenauer J., “On generalized inversive congruential pseudorandom numbers”, Math. Comp., 63:207 (1994), 293–299 | DOI | MR | Zbl

[11] Heat D., Sanchez P., “On the adequacy of pseudorandom number generators (or: how big a period do we need?)”, Oper. Res. Lett., 5:1 (1986), 3–6 | DOI | MR | Zbl

[12] Hill G. W., “Cyclic properties of pseudo-random sequences of Mersenne prime residues”, Comp. J., 22:1 (1979), 80–85 | DOI | MR

[13] Kato T., Wu L.-M., Yanagihara N., “On a nonlinear congruential pseudorandom number generator”, Math. Comput., 65:213 (1996), 227–233 | DOI | Zbl

[14] Keller G., Olson F. R., “Counting polynomial functions $\!\!\!\pmod{p^n}$”, Duke Math. J., 35:4 (1968), 835–838 | DOI | MR | Zbl

[15] Niederreiter H., “Nonlinear Methods for Pseudorandom Number and Vector Generation”, Simulation and Optimization. Lecture Notes in Economics and Mathematical Systems, v. 374, eds. Pflug G., Dieter U., Springer, Berlin, 1992, 145–153 | DOI

[16] Niederreiter H., Random number generation and quasi-Monte Carlo methods, SIM, Philadelphia, USA, 1992, 242 pp. | MR

[17] Singmaster D., “On polynomial functions $\!\!\!\pmod{m}$”, J. Num. Theory, 6:5 (1974), 345–352 | DOI | Zbl

[18] Sachkov V. N., Vvedenie v kombinatornye metody diskretnoi matematiki, Nauka, M., 1982, 384 pp. | MR

[19] McDonald B. R., Finite rings with identity, Marcel Dekker Inc., 1974, 448 pp. | MR | Zbl

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

[21] Melikhov A. N., Orientirovannye grafy i konechnye avtomaty, Nauka, M., 1971, 416 pp. | MR

[22] Gill A., Lineinye posledovatelnye mashiny, Nauka, M., 1974, 288 pp.; Gill A., Linear Sequential Circuits, McGraw-Hill, N.-Y., 1967, 215 pp. | MR

[23] Wang K. C., “Transition graphs of affine transformation on vector spaces over finite fields”, J. Franklin Inst., 283:1 (1967), 55–72 | DOI | MR | Zbl

[24] Nechaev A. A., “Cycle types of linear substitutions over finite commutative rings”, Russian Acad. Sci. Sb. Math., 78:2 (1994), 283–311 | DOI | MR | Zbl

[25] Lidl R., Niderraiter G., Konechnye polya, v. 2, Mir, M., 1988, 820 pp. ; Lidl R., Niederreiter H., Finite Fields, CUP, Cambridge, 1997, 755 pp. | MR | MR

[26] Kostrikin A. I., Vvedenie v algebru, Nauka, M., 1977, 496 pp. ; Kostrikin A. I., Introduction to algebra, Springer-Verlag, 1982, 575 pp. | MR | MR | Zbl

[27] Ermilov D. M., Kozlitin O. A., “Tsiklovaya struktura polinomialnogo generatora nad koltsom Galua”, Matem. vopr. kriptogr., 4:1 (2013), 27–57

[28] Nechaev A. A., “Polinomialnye preobrazovaniya konechnykh kommutativnykh lokalnykh kolets glavnykh idealov”, Matem. zametki, 27:6 (1980), 885–897 | MR | Zbl