Теоретические основы прикладной дискретной математики
О наибольшем порядке подстановок заданной степени
В. М. Фомичёв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