Polynomially complete quasigroups of prime order
A quasigroup \((Q,*)\) is said to be polynomially complete if the closure under Menger superposition of the binary operation \(*\) together with all the nullary operations on \(Q\) constitutes the set of all finitary operations on \(Q\). This paper establishes that a quasigroup \((Q,*)\) of prime order \(p\geq 5\) is not polynomially complete if and only if there exists a bijection from \((Q,*)\) to the finite field \((\mathbb{Z}_p,+,\times)\) so that any of the following two equivalent conditions holds: {\parindent=0.7cm \begin{itemize}\item[1.] The binary operation \(*\) maps to a linear function. \item[2.] All rows and columns of the Latin square defining \(Q\) constitute linear permutations on the set \(\mathbb{Z}_p\). \end{itemize}} It is also shown that the problem of checking the polynomial completeness of a quasigroup of prime order is decided in time polynomial in the order of the quasigroup under consideration. Both results are naturally generalized to \(n\)-quasigroups of prime order. Further, simple corollaries are given concerning the number of non-polynomially complete quasigroups of prime order, and the number of quasigroups that are isotopic to the former. In this last regard, any non-polynomially complete quasigroup of prime order is isotopic to a polynomially complete quasigroup.
- An assertion concerning functionally complete algebras and NP-completeness
- Characterization of polynomially complete quasigroups based on Latin squares for cryptographic transformations
- Characterization of polynomially complete quasigroups based on Latin squares for cryptographic transformations.
- Communication Theory of Secrecy Systems*
- Function Algebras on Finite Sets
- scientific article; zbMATH DE number 3771592 (Why is no real title available?)
- scientific article; zbMATH DE number 1033192 (Why is no real title available?)
- scientific article; zbMATH DE number 6761101 (Why is no real title available?)
- scientific article; zbMATH DE number 6288955 (Why is no real title available?)
- scientific article; zbMATH DE number 3340244 (Why is no real title available?)
- Completing partial commutative quasigroups constructed from partial Steiner triple systems is NP-complete
- Strong polynomial completeness of almost all quasigroups
- Algorithms for checking some properties of \(n\)-quasigroups
- Efficient verification of polynomial completeness of quasigroups
- Latin squares over quasigroups
- Automorphisms of finite quasi-groups without sub-quasi-groups
- scientific article; zbMATH DE number 2097987 (Why is no real title available?)
- Polynomial n-ary quasigroups.
- Constructions of polynomially complete quasigroups of arbitrary order
- Quasigroups and their applications
- On n-ary polynomially complete quasigroups
- Prime injections and quasipolarities
- Algebraic properties of subquasigroups and construction of finite quasigroups
- The complexity of checking the polynomial completeness of finite quasigroups
This page was built for publication: Polynomially complete quasigroups of prime order
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1731318)
