Loading [MathJax]/jax/output/CommonHTML/jax.js
Zapiski Nauchnykh Seminarov POMI
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Zap. Nauchn. Sem. POMI:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Zapiski Nauchnykh Seminarov POMI, 2005, Volume 326, Pages 214–234 (Mi znsl344)  

This article is cited in 32 scientific papers (total in 32 papers)

On linguistic dynamical systems, families of graphs of large girth, and cryptography

V. A. Ustimenkoab

a Universidade de São Paulo, Instituto de Matemática e Estatística
b National University of Kiev-Mohyla Academy
References:
Abstract: The paper is devoted to the study of a linguistic dynamical system of dimension n2 over arbitrary commutative ring K, i.e. a family F of nonlinear polynomial maps fα:KnKn depending on “time” α{K0} such that f1α=fα, fα1(x)=fα2(x) for some xKn 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 d1 if for each string a=(α1,,αs), sd, where αi+αi+1 is a nonzero divisor for i=1,,d1, 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 n0 mod 3 there is a family of linguistic dynamical systems Ln(K) of rank d1/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.
Received: 15.04.2005
English version:
Journal of Mathematical Sciences (New York), 2007, Volume 140, Issue 3, Pages 461–471
DOI: https://doi.org/10.1007/s10958-007-0453-2
Bibliographic databases:
UDC: 519.17, 519.729
Language: English
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
Citation in format AMSBIB
\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:
    1. 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)  crossref
    2. Vladislav Taranchuk, “A simple proof for the lower bound of the girth of graphs D(n,q)”, Discrete Mathematics, 347:1 (2024), 113705  crossref
    3. Vasyl Ustimenko, Tymoteusz Chojecki, Michal Klisowski, Lecture Notes in Networks and Systems, 921, Advances in Information and Communication, 2024, 21  crossref
    4. Vasyl Ustimenko, Tymoteusz Chojecki, Lecture Notes in Networks and Systems, 1067, Intelligent Systems and Applications, 2024, 525  crossref
    5. Vasyl Ustimenko, Lecture Notes in Networks and Systems, 1155, Proceedings of the Future Technologies Conference (FTC) 2024, Volume 2, 2024, 99  crossref
    6. Ming Xu, Xiaoyan Cheng, Yuansheng Tang, “On the girth cycles of the bipartite graph D(k,q)”, Discrete Mathematics, 346:9 (2023), 113500  crossref
    7. Aeryn Dunmore, Juliet Samandari, Julian Jang-Jaccard, “Matrix Encryption Walks for Lightweight Cryptography”, Cryptography, 7:3 (2023), 41  crossref
    8. Ming Xu, Xiaoyan Cheng, Yuansheng Tang, “Girth of the algebraic bipartite graph D(k,q)”, Finite Fields and Their Applications, 92 (2023), 102296  crossref
    9. Vasyl Ustimenko, Tymoteusz Chojecki, Lecture Notes in Networks and Systems, 739, Intelligent Computing, 2023, 1409  crossref
    10. Vasyl Ustimenko, Michał Klisowski, “On new protocols of Noncommutative Cryptography in terms of homomorphism of stable multivariate transformation groups”, ADM, 35:2 (2023), 220  crossref
    11. 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  crossref
    12. Vasyl Ustimenko, “On the Families of Stable Multivariate Transformations of Large Order and Their Cryptographical Applications”, Tatra Mountains Mathematical Publications, 70:1 (2017), 107  crossref
    13. 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  crossref
    14. Urszula Romańczuk-Polubiec, Vasyl Ustimenko, “On two windows multivariate cryptosystem depending on random parameters”, Algebra Discrete Math., 19:1 (2015), 101–129  mathnet  mathscinet
    15. Vasyl Ustimenko, “On algebraic graph theory and non-bijective multivariate maps in cryptography”, Algebra Discrete Math., 20:1 (2015), 152–170  mathnet  mathscinet
    16. Xiaoyan Cheng, Wenbing Chen, Yuansheng Tang, “On the girth of the bipartite graph D(k,q)”, Discrete Mathematics, 335 (2014), 25  crossref
    17. Vasyl Ustimenko, Urszula Romańczuk, Studies in Computational Intelligence, 427, Artificial Intelligence, Evolutionary Computing and Metaheuristics, 2013, 257  crossref
    18. P. L. K. Priyadarsini, Ramakalyan Ayyagari, 2013 International Conference on Advances in Computing, Communications and Informatics (ICACCI), 2013, 460  crossref
    19. 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  crossref
    20. Vasyl Ustimenko, Aneta Wróblewska, “On the key expansion of D(n, K)-based cryptographical algorithm”, Annales UMCS, Informatica, 11:2 (2011)  crossref
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Записки научных семинаров ПОМИ
    Statistics & downloads:
    Abstract page:1070
    Full-text PDF :105
    References:38
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025