Geodesic
Polynomially complete quasigroups of prime order
Algebra i logika, Tome 57 (2018) no. 5, pp. 509-521.

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

We formulate a polynomial completeness criterion for quasigroups of prime order, and show that verification of polynomial completeness may require time polynomial in order. The obtained results are generalized to $n$-quasigroups for any $n\ge3$. In conclusion, simple corollaries are given on the share of polynomially complete quasigroups among all quasigroups, and on the cycle structure of row and column permutations in Cayley tables for quasigroups that are not polynomially complete.
Mots-clés : quasigroup, $n$-quasigroup, permutation.
Keywords: Latin square, polynomially complete quasigroup 
@article{AL_2018_57_5_a0,
     author = {A. V. Galatenko and A. E. Pankratiev and S. B. Rodin},
     title = {Polynomially complete quasigroups of prime order},
     journal = {Algebra i logika},
     pages = {509--521},
     publisher = {mathdoc},
     volume = {57},
     number = {5},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2018_57_5_a0/}
}
TY  - JOUR
AU  - A. V. Galatenko
AU  - A. E. Pankratiev
AU  - S. B. Rodin
TI  - Polynomially complete quasigroups of prime order
JO  - Algebra i logika
PY  - 2018
SP  - 509
EP  - 521
VL  - 57
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2018_57_5_a0/
LA  - ru
ID  - AL_2018_57_5_a0
ER  - 
%0 Journal Article
%A A. V. Galatenko
%A A. E. Pankratiev
%A S. B. Rodin
%T Polynomially complete quasigroups of prime order
%J Algebra i logika
%D 2018
%P 509-521
%V 57
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2018_57_5_a0/
%G ru
%F AL_2018_57_5_a0
A. V. Galatenko; A. E. Pankratiev; S. B. Rodin. Polynomially complete quasigroups of prime order. Algebra i logika, Tome 57 (2018) no. 5, pp. 509-521. http://geodesic.mathdoc.fr/item/AL_2018_57_5_a0/

[1] C. Shannon, “Communication theory of secrecy systems”, Bell Syst. Techn. J., 28:4 (1949), 656–715 ; K. Shennon, “Teoriya svyazi v sekretnykh sistemakh”, Raboty po teorii informatsii i kibernetike, IL, M., 1963, 333–369 | DOI | MR | Zbl

[2] M. M. Glukhov, “O primeneniyakh kvazigrupp v kriptografii”, PDM, 2008, no. 2(2), 28–32

[3] S. Markovski, D. Gligoroski, V. Bakeva, “Quasigroup string processing: Part 1”, Proc. Maked. Acad. Sci. Arts Math. Tech. Sci., 20:1/2 (1999), 13–28 | MR

[4] S. Markovski, V. Kusacatov, “Quasigroup string processing: Part 2”, Proc. Maked. Acad. Sci. Arts Math. Tech. Sci., 21:1/2 (2000), 15–32 | MR

[5] V. Shcherbacov, Quasigroup based crypto-algorithms, arXiv: 1201.3016[math.GR]

[6] G. Horváth, C. L. Nehaniv, Cs. Szabó, “An assertion concerning functionally complete algebras and NP-completeness”, Theor. Comput. Sci., 407:1–3 (2008), 591–595 | DOI | MR | Zbl

[7] V. A. Artamonov, S. Chakrabarti, S. Gangopadhyay, S. K. Pal, “On Latin squares of polynomially complete quasigroups and quasigroups generated by shifts”, Quasigroups Relat. Syst., 21:2 (2013), 117–130 | MR | Zbl

[8] V. A. Artamonov, S. Chakrabarti, S. K. Pal, “Characterization of polynomially complete quasigroups based on Latin squares for cryptographic transformations”, Discrete Appl. Math., 200 (2016), 5–17 | DOI | MR | Zbl

[9] V. A. Artamonov, S. Chakrabarti, S. K. Pal, “Characterizations of highly nonassociative quasigroups and associative triples”, Quasigroups Relat. Syst., 25:1 (2017), 1–19 | MR | Zbl

[10] A. V. Galatenko, A. E. Pankratev, S. B. Rodin, “O polinomialno polnykh kvazigruppakh prostogo poryadka”, Intellekt. sist. Teor. prilozh., 20:3 (2016), 194–198 | MR

[11] S. V. Yablonskii, Vvedenie v diskretnuyu matematiku, Dlya vysshikh ucheb. zaved., 6-e izd., Vysshaya shkola, M., 2010

[12] D. Lau, Function algebras on finite sets, A basic course on many-valued logic and clone theory, Springer Monogr. Math., Springer, Berlin, 2006 | MR | Zbl

[13] V. B. Kudryavtsev, Funktsionalnye sistemy, Izd-vo MGU, M., 1982

[14] D. E. Knuth, The art of computer programming, v. 2, Seminumerical algorithms, 3rd ed., Addison-Wesley, Bonn, 1998 | MR | Zbl

[15] H. J. Ryser, “Permanents and systems of distinct representatives”, Combin. Math. Appl., Proc. Conf. (Univ. North Carolina, 1967), 1969, 55–70 | MR | Zbl