• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Articles
  • Polynomial completeness and completeness of finite n-quasigroups
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2028
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
September 22, 2026
Personal Interest in Doctoral Thesis Topic Most Important for Confidence in Successful Defence
A researcher at HSE University analysed data on 1,539 doctoral students from 161 Russian universities to identify which features of a thesis topic are associated with academic success and engagement. The most important factor was found to be personal interest in the research topic, which was associated with almost all key aspects of doctoral programme experience—from engaging with the academic supervisor to research activity and confidence about successfully defending the thesis. The findings have been published in Higher Education.
September 21, 2026
Researchers Develop Methodology to Assess the Quality of Legal Representation in Criminal Proceedings
Having a good defence attorney in criminal proceedings can largely determine whether a defendant retains their freedom, health and good name. Researchers at HSE University propose a method for predicting an attorney’s performance based on the outcomes of their previous cases. The methodology takes into account the severity of the charges, the complexity of the cases, and the most likely outcome, drawing on judicial statistics.
September 21, 2026
Algebra, Geometry, and AI: Russian and Vietnamese Mathematicians Discuss Current Research
A delegation of scientists from Hanoi visited the HSE Faculty of Computer Science and then took part in a Russian-Vietnamese conference in St Petersburg. The events were part of the three-year project ‘Flexibility and Computational Methods.’ Over the course of the project, the researchers have prepared joint publications and obtained new mathematical results.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

Polynomial completeness and completeness of finite n-quasigroups

Quasigroups and Related Systems. 2024. Vol. 32. No. 2. P. 207–223.
Chaplygina S., Alexy V. Galatenko

Finite quasigroups and n-quasigroups are currently extensively utilized to implement various cryptographic functions. Cryptographic requirements lead to constraints imposed on quasigroups and n-quasigroups. In particular, V. A. Artamonov proposed using polynomially complete quasigroups. Polynomial completeness can be decided with the help of a criterion of J. Hagemann and C. Herrmann: a quasigroup is polynomially complete if and only if it is simple and non-affine. In our paper we generalize this result to the case of n-quasigroups and give a proof based on I. G. Rosenberg’s description of maximal classes in k-valued logics. We also obtain a completeness criterion and show that completeness is a cryptographically reasonable requirement.

Language: English
Text on another site
Keywords: completenessAffinityquasigrouppolynomial completenessn-quasigroupsimplicityk-valued logicsmaximal class
Similar publications
Отмеченное субординатное натуральное исчисление для базовой интуиционистской кондициональной логики
Zaitsev I., Логические исследования 2025 Т. 31 № 2 С. 143–168
This article presents a labeled Fitch-style natural deduction system, 𝓕IntCK, for the basic propositional intuitionistic conditional logic IntCK introduced by G.K. Olkhovikov. The logic IntCK serves as a correct intuitionistic counterpart to Chellas' minimal conditional logic CK, designed to accommodate Lewis' strong and weak counterfactual conditionals within a single framework. In order to do this, IntCK features two independent logical connectives, namely □→ and ◇→, ...
Added: November 23, 2025
Некоторые свойства почти всех n-квазигрупп
Galatenko A. V., Галатенко В. В., Панкратьев А. Е., Математика и теоретические компьютерные науки 2024 Т. 2 № 4 С. 35–50
Изучается “типичность” свойств простоты, неаффинности и полиномиальной полноты конечных n-квазигрупп. Показано, что при фиксированном n почти все n-квазигруппы сильно неаффинны, т.е. не изотопны аффинным. Найдено точное значение числа простых, аффинных и одновременно простых и аффинных n-квазигрупп порядка 4. Как следствие, показано, что почти все n-квазигруппы порядка 4 полиномиально полны и сильно неаффинны. ...
Added: April 21, 2025
Тема народности в визуальной репрезентации Н. С. Хрущева в советской прессе (1957–1964 годов)
Petrova T., В кн.: Апрельские тезисы: материалы межлисциплинарной научно-исследовательской конференции (г. Пермь, 8-9 апреля 2022 г.).: Пермь: Пермский государственный национальный исследовательский университет, 2022. С. 197–206.
The article considers to identifying the features of simplicity in the visual image of N. S. Khrushchev in the late 1950s–early 1960s. Based on the visual materials of newspapers and ego-documents, au- thor identifies the features of simplicity and patterns of their display in Khrushchev’s representation. Author characterizes the personal myth of the Soviet leader, which based ...
Added: April 9, 2023
Алгоритмы проверки некоторых свойств n-квазигрупп
Galatenko A. V., Панкратьев А. Е., Staroverov V., Программирование 2022 № 1 С. 40–53
В работе описываются эффективные алгоритмы для проверки некоторых существенных с криптографической точки зрения свойств n-квазигрупп: полиномиальной полноты (которая сводится к проверке простоты и неаффинности) и существования n-подквазигрупп. Доказываются теоремы об оценках времени работы предложенных алгоритмов и их пространственной сложности, а также приводятся результаты численных экспериментов для оценки практической эффективности программной реализации. ...
Added: October 24, 2022
Generation of Proper Families of Functions
Galatenko A. V., Pankratiev A. E., Staroverov V., Lobachevskii Journal of Mathematics 2022 Vol. 43 No. 3 P. 571–581
Proper families of functions are a convenient framework for specification of large parametric families of quasigroups and 𝑛-quasigroups. We propose two methods for generation of proper families. The first method uses proper families of the order 𝑚 to construct proper families of the order 𝑚+1. The second method allows generating uniform distribution on the set ...
Added: October 24, 2022
О сильной полиномиальной полноте почти всех квазигрупп
Galatenko A. V., Galatenko V. V., Панкратьев А. Е., Математические заметки 2022 Т. 111 № 1 С. 8–14
In the paper, it is proved that almost all quasigroups are strongly polynomially complete, i.e., are not isotopic to quasigroups that are not polynomially complete. ...
Added: October 24, 2022
Раскрытие и предоставление информации эмитентами ценных бумаг в условиях санкций
Якушева Е. Е., Lex Russica (Русский закон) 2021 № 8 С. 110–117
The paper is devoted to the transformation of information transparency of Russian securities issuers after the implementation of sanctions by foreign states and international organizations against a significant number of Russian companies. In response to foreign policy pressure, the Russian state quite naturally took a number of steps to protect domestic companies affected by sanctions, ...
Added: October 29, 2021
On Necessary Conditions of Probability Limit Theorems in Finite Algebras
Yashunsky A., Doklady Mathematics 2020 Vol. 102 No. 1 P. 301–303
We consider the conditions for a finite set with a given system of operations (a finite algebra) to be subject to a probability limit theorem, i.e., arbitrary computations with mutually independent random variables have value distributions that tend to a certain limit (limit law) as the number of random variables used in the computation grows. ...
Added: July 6, 2021
О необходимых условиях предельных вероятностных теорем в конечных алгебрах
Yashunsky A., Доклады Российской Академии наук. Математика, информатика, процессы управления 2020 Т. 493 № 1 С. 47–50
Рассматриваются условия, при которых в конечном множестве с заданной системой операций (конечной алгебре) выполняется предельная вероятностная теорема, а именно, произвольные вычисления с независимыми случайными величинами имеют распределения значений, стремящиеся к некоторому предельному распределению (предельному закону) с ростом количества случайных величин, участвующих в вычислении. Подобное поведение можно рассматривать как одно из обобщений центральной предельной теоремы, имеющей ...
Added: June 29, 2021
Об одном алгоритме проверки существования подквазигрупп
Galatenko A. V., Панкратьев А. Е., Староверов В. М. et al., Чебышевский сборник 2021 Т. 22 № 2 С. 76–89
Quasigroup-based cryptoalgorithms are being actively studied in the framework of theoreticprojects; besides that, a number of quasigroup-based algorithms took part in NIST contestsfor selection of cryptographic standards. From the viewpoint of security it is highly desirableto use quasigroups without proper subquasigroups (otherwise transformations can degrade).We propose algorithms that take a quasigroup specified by the Cayley ...
Added: June 16, 2021
Efficient verification of polynomial completeness of quasigroups
A.V. Galatenko, Pankratiev A. E., Staroverov V. M., Lobachevskii Journal of Mathematics 2020 Vol. 41 No. 8 P. 1444–1453
Polynomial completeness of an operation guarantees that deciding solvability of equations over this operation is an NP-complete problem. Thus this property is beneficial from the viewpoint of cryptographic applications. We propose an algorithm for verification of polynomial completeness of quasigroups and analyse efficiency of its serial and parallel implementations. ...
Added: October 23, 2020
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit