On the largest order of substitutions of a given degree

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 ^(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 ^(n), defined as the dependence of the largest order value among all permutations of degree n, is poorly studied. The monotonicity of function ^(n) is shown, and a two-sided estimate of its values is obtained: IL (n) < Ж M \\/²( ⁿ I) | ^!, where Пц_п) 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: ^(n) > 224k!(1,665)^k(ln k)^(k-15)/2 for any n > 1000 and k = ^^2n/ln nJ.

Keywords

Authors

References