RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika. Supplement // Archive

Prikl. Diskr. Mat. Suppl., 2021 Issue 14, Pages 32–36 (Mi pdma523)

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



© Steklov Math. Inst. of RAS, 2024