|
Записки научных семинаров ПОМИ, 2005, том 326, страницы 214–234
(Mi znsl344)
|
|
|
|
Эта публикация цитируется в 29 научных статьях (всего в 29 статьях)
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
Аннотация:
Статья посвящена изучению лингвистических динамических систем размерности $n\ge 2$ над произвольным коммутативным кольцом $K$, т.е. семейство $F$ нелинейных полиномиальных отображений $f_\alpha\colon K^n\to K^n$, зависящих от “времени” $\alpha\in\{K-0\}$, таких что
$f_\alpha^{-1}=f_{-\alpha}$ and $f_{\alpha_1}(x)=f_{\alpha_2}(x)$ для некоторых $x\in K^n$ implies $\alpha_1=\alpha_2$, причем каждое отображение $f_\alpha$ не имеет инвариантных точек.
Окрестность $\{f_\alpha(v)|\alpha\in K-\{0\}\}$ элемента $v$ определяет граф $\Gamma(F)$ динамической системы на множестве вершин $K^n$.
Мы будем называть $F$ лингвистической динамической системой ранга $d\ge 1$, если для каждой строки
$\mathrm{a}=(\alpha_1,\dots,\alpha_s)$, $s\le d$, где $\alpha_i+\alpha_{i+1}$ – ненулевой дивизор для
$i=1,\dots,d-1$, вершины $v$ и $v_{\mathrm{a}}=f_{\alpha_1}\times\dots\times f_{\alpha_s}(v)$
графа соединимы единственным путем.
Для каждого коммутативного кольца $K$ и четного целого $n\ne 0$ mod 3 существует семейство лингвистических динамических систем $L_n(K)$ ранга $d\ge 1/3n$. Пусть $L(n, K)$ – граф динамической системы $L_n(q)$.
Если $K=F_q$, графы $L(n,F_q)$ образуют семейство графов большого
обхвата. Проективный предел $L(K)$ графов $L(n,K)$, $n\to\infty$, определен для каждого коммутативного кольца $K$. Если $K$ – область целостности, то граф $L(K)$ является деревом, если $K$
имеет делители нуля, то обхват $K$ падает до 4.
Мы вводим в рассмотрение некоторые другие семейства графов большого
обхвата, связанных с динамическими системами $L_n(q)$ в случае
четного $q$. Динамические системы и связанные с ними графы можно
использовать для разработки симметричных или асимметричных
криптографических алгоритмов. Эти графы позволяют наилучшие из
известных верхние границы для минимального порядка регулярных
графов без циклов длины $4n$, $n\ge 3$.
Библ. – 42 назв.
Поступило: 15.04.2005
Образец цитирования:
V. A. Ustimenko, “On linguistic dynamical systems, families of graphs of large girth, and
cryptography”, Теория представлений, динамические системы, комбинаторные и алгоритмические методы. XIII, Зап. научн. сем. ПОМИ, 326, ПОМИ, СПб., 2005, 214–234; J. Math. Sci. (N. Y.), 140:3 (2007), 461–471
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl344 https://www.mathnet.ru/rus/znsl/v326/p214
|
Статистика просмотров: |
Страница аннотации: | 1032 | PDF полного текста: | 84 | Список литературы: | 30 |
|