On the largest order of substitutions of a given degree

V. M. Fomichev

Prikladnaya Diskretnaya Matematika. Supplement, no. 14 (2021), pp. 32-36.

Résumé

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$.

Détail

Keywords: order of a substitution, prime number.
Mots-clés : cycle structure

Bibliographie

[1] Rosser B., “The $n$-th prime is greater than $n \log n$”, Proc. London Math. Soc., 45 (1939), 21–44 | DOI | MR