|
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.
Citation:
V. M. Fomichev, “On the largest order of substitutions of a given degree”, Prikl. Diskr. Mat. Suppl., 2021, no. 14, 32–36
Linking options:
https://www.mathnet.ru/eng/pdma523 https://www.mathnet.ru/eng/pdma/y2021/i14/p32
|
Statistics & downloads: |
Abstract page: | 120 | Full-text PDF : | 32 | References: | 23 |
|