|
Теоретические основы прикладной дискретной математики
О наибольшем порядке подстановок заданной степени
В. М. Фомичёв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$.
Ключевые слова:
порядок подстановки, цикловая структура подстановки, простое число.
Образец цитирования:
В. М. Фомичёв, “О наибольшем порядке подстановок заданной степени”, ПДМ. Приложение, 2021, № 14, 32–36
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdma523 https://www.mathnet.ru/rus/pdma/y2021/i14/p32
|
|