Abstract:
The paper is devoted to the study of a linguistic dynamical system of
dimension n⩾2 over arbitrary commutative ring K, i.e. a family F of nonlinear polynomial maps fα:Kn→Kn depending on “time” α∈{K−0} such that
f−1α=f−α, fα1(x)=fα2(x) for some x∈Kn implies α1=α2, and each map fα has no invariant points.
The neighbourhood {fα(v)|α∈K−{0}} of an element v defines the graph Γ(F) of a dynamical system on the vertex set Kn.
We shall refer to F as a linguistic dynamical system of rank d⩾1 if for each string a=(α1,…,αs), s⩽d, where αi+αi+1 is a nonzero divisor for i=1,…,d−1, the vertices v and va=fα1×⋯×fαs(v) in the graph are connected by a unique pass.
For each commutative ring K and even integer number n≠0 mod 3 there is a family of linguistic dynamical systems Ln(K) of rank d⩾1/3n. Let L(n,K) be the graph of a dynamical system
Ln(q).
If K=Fq, the graphs L(n,Fq) form a new family of graphs of large girth. The projective limit L(K) of L(n,K), n→∞, is well defined for each commutative ring K, in the case of integral domain K the graph L(K) is a forest. If K has zero divisors, then the girth of K is dropping to 4.
We introduce some other families of graphs of large girth related to the dynamical systems Ln(q) in the case of even q. The dynamical systems and related graphs can be used for the development of symmetric or
asymmetric cryptographical algorithms. These graphs allow us establish the best known upper bounds on the minimal order of regular graphs without cycles of length 4n, with n odd ⩾3.
Citation:
V. A. Ustimenko, “On linguistic dynamical systems, families of graphs of large girth, and
cryptography”, Representation theory, dynamical systems, combinatorial and algoritmic methods. Part XIII, Zap. Nauchn. Sem. POMI, 326, POMI, St. Petersburg, 2005, 214–234; J. Math. Sci. (N. Y.), 140:3 (2007), 461–471
\Bibitem{Ust05}
\by V.~A.~Ustimenko
\paper On linguistic dynamical systems, families of graphs of large girth, and
cryptography
\inbook Representation theory, dynamical systems, combinatorial and algoritmic methods. Part~XIII
\serial Zap. Nauchn. Sem. POMI
\yr 2005
\vol 326
\pages 214--234
\publ POMI
\publaddr St.~Petersburg
\mathnet{http://mi.mathnet.ru/znsl344}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2183222}
\zmath{https://zbmath.org/?q=an:1094.37008}
\transl
\jour J. Math. Sci. (N. Y.)
\yr 2007
\vol 140
\issue 3
\pages 461--471
\crossref{https://doi.org/10.1007/s10958-007-0453-2}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-33845800436}
Linking options:
https://www.mathnet.ru/eng/znsl344
https://www.mathnet.ru/eng/znsl/v326/p214
This publication is cited in the following 32 articles:
Tymoteusz Chojecki, Grahame Erskine, James Tuite, Vasyl Ustimenko, “On affine forestry over integral domains and families of deep Jordan–Gauss graphs”, European Journal of Mathematics, 11:1 (2025)
Vladislav Taranchuk, “A simple proof for the lower bound of the girth of graphs D(n,q)”, Discrete Mathematics, 347:1 (2024), 113705
Vasyl Ustimenko, Tymoteusz Chojecki, Michal Klisowski, Lecture Notes in Networks and Systems, 921, Advances in Information and Communication, 2024, 21
Vasyl Ustimenko, Tymoteusz Chojecki, Lecture Notes in Networks and Systems, 1067, Intelligent Systems and Applications, 2024, 525
Vasyl Ustimenko, Lecture Notes in Networks and Systems, 1155, Proceedings of the Future Technologies Conference (FTC) 2024, Volume 2, 2024, 99
Ming Xu, Xiaoyan Cheng, Yuansheng Tang, “On the girth cycles of the bipartite graph D(k,q)”, Discrete Mathematics, 346:9 (2023), 113500
Ming Xu, Xiaoyan Cheng, Yuansheng Tang, “Girth of the algebraic bipartite graph D(k,q)”, Finite Fields and Their Applications, 92 (2023), 102296
Vasyl Ustimenko, Tymoteusz Chojecki, Lecture Notes in Networks and Systems, 739, Intelligent Computing, 2023, 1409
Vasyl Ustimenko, Michał Klisowski, “On new protocols of Noncommutative Cryptography in terms of homomorphism of stable multivariate transformation groups”, ADM, 35:2 (2023), 220
V.O. Ustimenko, “On new results on extremal graph theory, theory of algebraic graphs, and their applications”, Dopov. Nac. akad. nauk Ukr., 2022, no. 4, 25
Vasyl Ustimenko, “On the Families of Stable Multivariate Transformations of Large Order and Their Cryptographical Applications”, Tatra Mountains Mathematical Publications, 70:1 (2017), 107
Xiaoyan Cheng, Wenbing Chen, Yuansheng Tang, “On the conjecture for the girth of the bipartite graph D(k,q)”, Discrete Mathematics, 339:9 (2016), 2384
Urszula Romańczuk-Polubiec, Vasyl Ustimenko, “On two windows multivariate cryptosystem depending on random parameters”, Algebra Discrete Math., 19:1 (2015), 101–129
Vasyl Ustimenko, “On algebraic graph theory and non-bijective multivariate maps in cryptography”, Algebra Discrete Math., 20:1 (2015), 152–170
Xiaoyan Cheng, Wenbing Chen, Yuansheng Tang, “On the girth of the bipartite graph D(k,q)”, Discrete Mathematics, 335 (2014), 25
Vasyl Ustimenko, Urszula Romańczuk, Studies in Computational Intelligence, 427, Artificial Intelligence, Evolutionary Computing and Metaheuristics, 2013, 257
P. L. K. Priyadarsini, Ramakalyan Ayyagari, 2013 International Conference on Advances in Computing, Communications and Informatics (ICACCI), 2013, 460
Urszula Romańczuk, Vasyl Ustimenko, “On Families of Graphs of Large Cycle Indicator, Matrices of Large Order and Key Exchange Protocols With Nonlinear Polynomial Maps of Small Degree”, Math.Comput.Sci., 6:2 (2012), 167
Vasyl Ustimenko, Aneta Wróblewska, “On the key expansion of D(n, K)-based cryptographical algorithm”, Annales UMCS, Informatica, 11:2 (2011)