Θ-critical sets of Latin squares having Θ as a principal autotopism

Abstract

Any principal autotopism Θ of a Latin square L ∈ LS(n), whose elements are in a set N of n symbols, gives a significant information about the symmetry of L. Although Θ-critical sets of L can be then used in Cryptography to get the access structure of a secret sharing scheme [1, 3, 7], the size of the smallest one is still an open problem. Because Θ can be decomposed into triples of a partial Latin square [6], we propose in this paper an algorithm depending on the order of L allowing to give an upper bound of the previous size. This algorithm reduces the previous problem to the calculus of the size of the smallest critical set of a Latin subrectangle of L of order k × n, which can be decomposed at the same time into k regions, each of them having all the symbols of N.