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

ПДМ. Приложение, 2021, выпуск 14, страницы 32–36 (Mi pdma523)

Теоретические основы прикладной дискретной математики

О наибольшем порядке подстановок заданной степени

В. М. Фомичёвabc

a ООО «Код Безопасности», г. Москва
b Финансовый университет при Правительстве РФ, г. Москва
c ФИЦ ИУ РАН, г. Москва

Аннотация: Необходимым требованием к системе шифрования является достаточно большой порядок группы, которая ассоциируется с шифром (то есть порождается подстановками шифра). В связи с этим представляет интерес величина $\mu(n)$, оценивающая порядки циклических групп подстановок степени $n$, в том числе циклических групп, порождённых шифрующими подстановками. Известно, что порядок подстановки равен наименьшему общему кратному длин её циклов. Однако мало изучена функция $\mu(n)$, принимающая значения, равные наибольшему порядку подстановки степени $n$. Показана монотонность функции $\mu(n)$, получена двухсторонняя оценка её значений: $\prod_{\omega(n)} \le \mu(n) \le \big \lceil{ \sqrt{2(n-1)} \big \rceil} !$, где $\Pi_{\omega(n)}$  — произведение всех первых (в порядке возрастания) простых чисел, сумма которых не больше $n$. Получена асимптотическая оценка нижней границы при больших $n$:
$$ \mu(n) > 224k!(1{,}665)^k(\ln k)^{(k-15)/{2}} $$
при любом $n \ge 1000$ и $k=\left \lfloor \sqrt{{2n}/{\ln n}} \right \rfloor$.

Ключевые слова: порядок подстановки, цикловая структура подстановки, простое число.

УДК: 519.1

DOI: 10.17223/2226308X/14/3



© МИАН, 2024