<p>The order of the substitution, equal to the least common multiple of the lengths of its cycles, determines the period length of the sequence of substitution iterations, which is important for cryptographic analysis of systems that use substitution iterations, in particular for data encryption. In this paper, we study the Landau function—the highest order <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mu \left( n \right)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>μ</mi> <mfenced close=")" open="("> <mi>n</mi> </mfenced> </mrow> </math></EquationSource> </InlineEquation> of substitution of degree <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$n>1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>></mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, where the maximum is reached among all partitions of the number <i>n</i> into cycle lengths. The lengths of substitution cycles are partially ordered with respect to the binary floor division relation, and the set of maximal (in this sense) lengths of substitution cycles uniquely determines its order. It is shown that the value <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\mu \left( n \right)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>μ</mi> <mfenced close=")" open="("> <mi>n</mi> </mfenced> </mrow> </math></EquationSource> </InlineEquation>, which does not decrease with increasing <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$n$</EquationSource> <EquationSource Format="MATHML"><math> <mi>n</mi> </math></EquationSource> </InlineEquation>, is achieved on substitutions whose set of maximal cycle lengths is uniquely determined and consists of pairwise coprime primal numbers. For <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$n = \sigma^{\left( k \right)} ,k = 1, \ldots ,8$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>=</mo> <msup> <mi>σ</mi> <mfenced close=")" open="("> <mi>k</mi> </mfenced> </msup> <mo>,</mo> <mi>k</mi> <mo>=</mo> <mn>1</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <mn>8</mn> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\sigma^{\left( k \right)}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>σ</mi> <mfenced close=")" open="("> <mi>k</mi> </mfenced> </msup> </math></EquationSource> </InlineEquation> is the sum of the <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$k$</EquationSource> <EquationSource Format="MATHML"><math> <mi>k</mi> </math></EquationSource> </InlineEquation> smallest prime numbers, the exact values of <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\mu \left( n \right)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>μ</mi> <mfenced close=")" open="("> <mi>n</mi> </mfenced> </mrow> </math></EquationSource> </InlineEquation>, equal to the product of the <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$k$</EquationSource> <EquationSource Format="MATHML"><math> <mi>k</mi> </math></EquationSource> </InlineEquation> smallest prime numbers, are obtained. For the remaining <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$n$</EquationSource> <EquationSource Format="MATHML"><math> <mi>n</mi> </math></EquationSource> </InlineEquation>, formulas for estimating upper and lower bounds of <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$\mu \left( n \right)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>μ</mi> <mfenced close=")" open="("> <mi>n</mi> </mfenced> </mrow> </math></EquationSource> </InlineEquation> are obtained. Numerical values of upper and lower bounds of <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$\mu \left( n \right)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>μ</mi> <mfenced close=")" open="("> <mi>n</mi> </mfenced> </mrow> </math></EquationSource> </InlineEquation> for some <InlineEquation ID="IEq13"> <EquationSource Format="TEX">$n \le \sigma^{{\left( {17} \right)}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≤</mo> <msup> <mi>σ</mi> <mfenced close=")" open="("> <mn>17</mn> </mfenced> </msup> </mrow> </math></EquationSource> </InlineEquation> are given.</p>

Estimation of the maximum order of substitutions

期刊论文
发表日期：

2025年5月25日

查看全文

Vladimir Fomichev

摘要

The order of the substitution, equal to the least common multiple of the lengths of its cycles, determines the period length of the sequence of substitution iterations, which is important for cryptographic analysis of systems that use substitution iterations, in particular for data encryption. In this paper, we study the Landau function—the highest order $\mu \left( n \right)$ $μ (n)$ of substitution of degree $n>1$ $n > 1$ , where the maximum is reached among all partitions of the number n into cycle lengths. The lengths of substitution cycles are partially ordered with respect to the binary floor division relation, and the set of maximal (in this sense) lengths of substitution cycles uniquely determines its order. It is shown that the value $\mu \left( n \right)$ $μ (n)$ , which does not decrease with increasing $n$ $n$ , is achieved on substitutions whose set of maximal cycle lengths is uniquely determined and consists of pairwise coprime primal numbers. For $n = \sigma^{\left( k \right)} ,k = 1, \ldots ,8$ $n = σ^{(k)}, k = 1, \dots, 8$ , where $\sigma^{\left( k \right)}$ $σ^{(k)}$ is the sum of the $k$ $k$ smallest prime numbers, the exact values of $\mu \left( n \right)$ $μ (n)$ , equal to the product of the $k$ $k$ smallest prime numbers, are obtained. For the remaining $n$ $n$ , formulas for estimating upper and lower bounds of $\mu \left( n \right)$ $μ (n)$ are obtained. Numerical values of upper and lower bounds of $\mu \left( n \right)$ $μ (n)$ for some $n \le \sigma^{{\left( {17} \right)}}$ $n \leq σ^{(17)}$ are given.