A quadratic algorithm for deciding non-affinity of finite quasigroups

A. V. Galatenko

Lomonosov Moscow State University

Abstract: Finite quasigroups are actively used to construct cryptographic algirothms. In order to ensure cryptographic strength of algorithm authors impose various requirements on quasigroups. Non-affinity is one of such requirements. A. V. Galatenko and A. E. Pankratiev proposed an algorithm that decides quasigroup non-affinity with time complexity $O \left ( k^3 \right )$, where $k$ is the quasigoup order. In our paper we descibe a modification of this algorithm that makes the complexity quadratic and show that in the general case this bound can not be improved.

Keywords: finite quasigroup, non-affinity.

UDC: 512.548.7+519.716.2

Received: 10.05.2025

DOI: 10.4213/dm1877