|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Математические методы криптографии
О примитивности некоторых множеств перемешивающих орграфов регистровых преобразований
Я. Э. Авезова Национальный исследовательский ядерный университет "МИФИ", г. Москва
Аннотация:
Получены условия примитивности и оценки экспонентов для нескольких множеств орграфов $\hat\Gamma=\{\Gamma_0,\dots,\Gamma_{n-1}\}$ с вершинами $0,\dots,n-1$.
Критерий: если $\Gamma_i$ имеет гамильтонов контур $(0,\dots,n-1)$ и дугу $(i, (i+l)\mod n)$, $n\geq l>1$, $i=0,\dots,n-1$, то множество $\hat\Gamma$ примитивное, если и только если $\text{НОД}(n,l-1)=1$, при этом $n-1\leq\exp\hat\Gamma\leq 2n-2$; если $\Gamma_i$ имеет также дугу $(i,(i+\lambda)\mod n)$, $n\geq\lambda>l>1$, $i=0,\dots,n-1$, то множество $\hat\Gamma$ примитивное, если и только если $\text{НОД}(n,l-1,\lambda-1)=1$, $\exp\hat\Gamma\geq(\sqrt{8n+1}-3)/2$. При этом если $\text{НОД}(n,l-1)=1$, то $\exp\hat\Gamma\leq n-1+\max\{b,n-b+1\}$, где $b=(\lambda-1)(l-1)^{\varphi(n)-1}\mod n$ и $\varphi(n)$ – функция Эйлера.
Пусть $n$ чётное, орграф $\Gamma_i$ при чётных $i$ имеет контур $(0,\dots,n\!-1)$ и дугу $(i,(i+l)\mod n)$ и при нечётных $i$ имеет контур $(n-1,\dots,0)$ и дугу $(i,(i+\lambda)\mod n)$. Тогда если $\text{НОД}(n,l-1)=1$ или $\text{НОД}(n,\lambda+1)=1$, то множество $\hat\Gamma$ примитивное и $\exp\hat\Gamma\leq 2n-2$.
Ключевые слова:
примитивность множества графов, экспонент орграфа, экспонент множества орграфов.
Образец цитирования:
Я. Э. Авезова, “О примитивности некоторых множеств перемешивающих орграфов регистровых преобразований”, ПДМ. Приложение, 2017, № 10, 60–62
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdma311 https://www.mathnet.ru/rus/pdma/y2017/i10/p60
|
Статистика просмотров: |
Страница аннотации: | 122 | PDF полного текста: | 71 | Список литературы: | 29 |
|