Prikladnaya Diskretnaya Matematika. Supplement
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Prikl. Diskr. Mat. Suppl.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Prikladnaya Diskretnaya Matematika. Supplement, 2021, Issue 14, Pages 32–36
DOI: https://doi.org/10.17223/2226308X/14/3
(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
References:
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.
Document Type: Article
UDC: 519.1
Language: Russian
Citation: V. M. Fomichev, “On the largest order of substitutions of a given degree”, Prikl. Diskr. Mat. Suppl., 2021, no. 14, 32–36
Citation in format AMSBIB
\Bibitem{Fom21}
\by V.~M.~Fomichev
\paper On the largest order of substitutions of a given degree
\jour Prikl. Diskr. Mat. Suppl.
\yr 2021
\issue 14
\pages 32--36
\mathnet{http://mi.mathnet.ru/pdma523}
\crossref{https://doi.org/10.17223/2226308X/14/3}
Linking options:
  • https://www.mathnet.ru/eng/pdma523
  • https://www.mathnet.ru/eng/pdma/y2021/i14/p32
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Prikladnaya Diskretnaya Matematika. Supplement
    Statistics & downloads:
    Abstract page:120
    Full-text PDF :32
    References:23
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024