Geodesic
An algorithm for checking the existence of subquasigroups
Čebyševskij sbornik, Tome 22 (2021) no. 2, pp. 76-89

Voir la notice de l'article provenant de la source Math-Net.Ru

Quasigroup-based cryptoalgorithms are being actively studied in the framework of theoretic projects; besides that, a number of quasigroup-based algorithms took part in NIST contests for selection of cryptographic standards. From the viewpoint of security it is highly desirable to use quasigroups without proper subquasigroups (otherwise transformations can degrade). We propose algorithms that take a quasigroup specified by the Cayley table as the input and decide whether there exist proper subquasigroups or subquasigroups of the order at least 2. Temporal complexity of the algorithms is optimized at the cost of increased spatial complexity. We prove bounds on time and memory and analyze the efficiency of software implementations applied to quasigroups of a large order. The results were reported at the XVIII International Conference «Algebra, Number Theory and Discrete Geometry: modern problems, applications and problems of history».
Keywords: quasigroup, subquasigroup, Cayley table. 
@article{CHEB_2021_22_2_a4,
     author = {A. V. Galatenko and A. E. Pankratiev and V. M. Staroverov},
     title = {An algorithm for checking the existence of subquasigroups},
     journal = {\v{C}eby\v{s}evskij sbornik},
     pages = {76--89},
     publisher = {mathdoc},
     volume = {22},
     number = {2},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/CHEB_2021_22_2_a4/}
}
TY  - JOUR
AU  - A. V. Galatenko
AU  - A. E. Pankratiev
AU  - V. M. Staroverov
TI  - An algorithm for checking the existence of subquasigroups
JO  - Čebyševskij sbornik
PY  - 2021
SP  - 76
EP  - 89
VL  - 22
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CHEB_2021_22_2_a4/
LA  - ru
ID  - CHEB_2021_22_2_a4
ER  - 
%0 Journal Article
%A A. V. Galatenko
%A A. E. Pankratiev
%A V. M. Staroverov
%T An algorithm for checking the existence of subquasigroups
%J Čebyševskij sbornik
%D 2021
%P 76-89
%V 22
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CHEB_2021_22_2_a4/
%G ru
%F CHEB_2021_22_2_a4
A. V. Galatenko; A. E. Pankratiev; V. M. Staroverov. An algorithm for checking the existence of subquasigroups. Čebyševskij sbornik, Tome 22 (2021) no. 2, pp. 76-89. http://geodesic.mathdoc.fr/item/CHEB_2021_22_2_a4/