Theoretical Foundations of Applied Discrete Mathematics
On the largest order of substitutions of a given degree
V. M. Fomichevabc a "Security Code", Moscow
b Financial University under the Government of the Russian Federation, Moscow
c Federal Research Center "Computer Science and Control" of Russian Academy of Sciences, Moscow
Abstract:
A necessary requirement for an encryption system is a sufficiently large order of the group associated with the cipher (i.e., generated by the cipher substitution). In this regard, the value of
$\mu(n)$ that estimates the orders of cyclic substitution groups of degree
$n$, including cyclic groups generated by cipher substitutions, is of interest. It is known that the order of a substitution is equal to the lowest common multiple of its cycle lengths. However, function
$\mu(n)$, defined as the dependence of the largest order value among all permutations of degree
$n$, is poorly studied. The monotonicity of function
$\mu(n)$ is shown, and a two-sided estimate of its values is obtained: $\Pi_{\omega(n)} \le \mu(n) \le \big \lceil{ \sqrt{2(n-1)} \big \rceil} !$, where
$\Pi_{\omega(n)}$ is the greatest value of the product of prime numbers, the sum of which is not greater than
$n$. An asymptotic estimate of the lower bound for large
$n$ is obtained: $ \mu(n) > 224k!(1{,}665)^k(\ln k)^{(k-15)/{2}} $ for any
$n \ge 1000$ and
$k=\big \lfloor \sqrt{{2n}/{\ln n}} \big \rfloor$.
Keywords:
order of a substitution, cycle structure, prime number.
UDC:
519.1
DOI:
10.17223/2226308X/14/3