RUS  ENG
Полная версия
ЖУРНАЛЫ // Прикладная дискретная математика. Приложение // Архив

ПДМ. Приложение, 2017, выпуск 10, страницы 60–62 (Mi pdma311)

Эта публикация цитируется в 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$.

Ключевые слова: примитивность множества графов, экспонент орграфа, экспонент множества орграфов.

УДК: 519.1

DOI: 10.17223/2226308X/10/25



© МИАН, 2024