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 31 scientific papers (total in 31 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 $n\ge 2$ over arbitrary commutative ring $K$, i.e. a family $F$ of nonlinear polynomial maps $f_\alpha\colon K^n\to K^n$ depending on “time” $\alpha\in\{K-0\}$ such that $f_\alpha^{-1}=f_{-\alpha}$, $f_{\alpha_1}(x)=f_{\alpha_2}(x)$ for some $x\in K^n$ implies $\alpha_1=\alpha_2$, and each map $f_\alpha$ has no invariant points.
The neighbourhood $\{f_\alpha(v)|\alpha\in K-\{0\}\}$ of an element $v$ defines the graph $\Gamma(F)$ of a dynamical system on the vertex set $K^n$.
We shall refer to $F$ as a linguistic dynamical system of rank $d\ge 1$ if for each string $\mathrm{a}=(\alpha_1,\dots,\alpha_s)$, $s\le d$, where $\alpha_i+\alpha_{i+1}$ is a nonzero divisor for $i=1,\dots,d-1$, the vertices $v$ and $v_{\mathrm{a}}=f_{\alpha_1}\times\dots\times f_{\alpha_s}(v)$ in the graph are connected by a unique pass.
For each commutative ring $K$ and even integer number $n\ne 0$ mod 3 there is a family of linguistic dynamical systems $L_n(K)$ of rank $d\ge 1/3n$. Let $L(n, K)$ be the graph of a dynamical system $L_n(q)$.
If $K=F_q$, the graphs $L(n, F_q)$ form a new family of graphs of large girth. The projective limit $L(K)$ of $L(n,K)$, $n\to\infty$, 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 $L_n(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 $\ge 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 31 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Записки научных семинаров ПОМИ
    Statistics & downloads:
    Abstract page:1043
    Full-text PDF :91
    References:33
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024