A computational algebraic geometry approach to analyze pseudo-random sequences based on Latin squares

Ra´ul M. Falc´ on [email protected] V´ ıctor ´ Alvarez valv[email protected] F´ elix Gudiel [email protected] 1Department Applied Mathematics I, University of Seville, Seville, Spain A computational algebraic geometry approach to analyze pseudo-random sequences based on Latin squares Raúl M. Falcón1 V´ıctor ´ Alvarez1 F´elix Gudiel1 Abstract Latin squares are used as scramblers on symmetric-key algorithms that generate pseudo-random sequences of the same length. The robustness and effectiveness of these algorithms are respectively based on the extremely large key space and the appropriate choice of the Latin square under consideration. It is also known the importance that isomorphism classes of Latin squares have to design an effective algorithm. In order to delve into this last aspect, we improve in this paper the efficiency of the known methods on computational algebraic geometry to enumerate and classify partial Latin squares. Particularly, we introduce the notion of affine algebraic set of a partial Latin square L = (lij ) of order n over a field K as the set of zeros of the binomial ideal  xi xj − xlij : (i, j) is a non-empty cell inL ⊆K[x1,..., xn]. Since isomorphic partial Latin squares give rise to isomorphic affine algebraic sets, every isomorphism invariant of the latter constitutes an isomorphism invariant of the former. In particular, we deal computationally with the problem of deciding whether two given partial Latin squares have either the same or isomorphic affine algebraic sets. To this end, we introduce a new pair of equivalence relations among partial Latin squares: being partial transpose and being partial isotopic. Keywords Symmetric-key algorithm · Image pattern · Partial Latin square · Affine algebraic set · Isomorphism 1 Introduction Apartial Latin square of order nis an n×narray in which each cell is either empty or contains an element of a finite set Sof nsymbols so that each symbol occurs at most once in each row and in each column. This is a Latin square if all its cells are non-empty. Every Latin square constitutes the multiplication table of a quasigroup Q=(S, ·)endowed with a binary operation ·so that the equations a·x=band y·a=bhave unique solutions for xand yin S,foralla,b ∈S. Equivalently, Q has left- and right-division, which we denote respectively \and /.Thatis,x=a\b in the first equation, and y=b/a in the second one. Currently, it is only known the number of Latin squares of order n≤11 [24,31,37] and that of partial Latin squares of order n≤7[13–15]. Quasigroups and Latin squares are commonly used in cryptography [38,39,41]. In symmetric cryptography, Latin squares are used as scramblers that generate ciphered pseudo-random strings with the same length than a given plaintext, but with a remarkable period growth [26,27,33]. That is, they increase considerably the maximum number of consecutive distinct bits within the plaintext. More specifically, given a quasigroup Q=(S, ·),aleader symbol s∈Sand a plaintext T=t1t2...t m,the former enables one to generate the encrypted string Es(T ) =e1e2...e m,where e1=s·t1and ei=ei−1·ti,forall1<i≤m. The sequences of the ciphered text follow a uniform distribution [34,36]. The decryption map Ds(Es(T )) is, in turn, based on the left-division within Q. In particular, t1=s\e1and ti=ei−1\ei,forall 1<i≤m. This encryption-decryption process acts, therefore, as a symmetric-key algorithm having the underlying Latin square related to the quasigroup as its cryptographic key. The latter can in turn be decomposed into disjoint partial Latin squares as shares describing a secret sharing scheme [4,5,12,44]. The huge number of Latin squares ensures the robustness of this algorithm against brute force and statistical attacks, even if the ciphered text and the leader symbol are known. In any case, an appropriate choice of the Latin square under consideration is especially relevant to design effective symmetric-key algorithms producing high period growths [9]. In order to optimize this choice, the distribution of Latin squares into isomorphism classes play a fundamental role. This is due to the fact that any two isomorphic Latin squares always generate the same number of consecutive distinct bits starting from a same plaintext. Reciprocally, the analysis of pseudo-random sequences derived from non-isomorphic Latin squares enables one to discover certain algebraic and even geometrical properties that they have in common [32,35]. Remark in this last regard how Dimitrova and Markovski [10,11] introduced the distribution of quasigroups into fractals and non-fractals, depending on the image patterns that result after disposing as rows of a rectangular array the ciphered texts derived from an iterative application of the described encryption process. Let us remark that counting, enumerating, and analyzing isomorphism classes constitute indeed main problems in the theory of (partial) Latin squares. Currently, it is known the number of isomorphism classes of Latin squares of order n≤11 [24,31,37] and that of partial Latin squares of order n≤6[17,19]. Computational algebraic geometry has revealed to be a good alternative to deal with the enumeration and classification of (partial) Latin squares of small order [1,2, 13–17,19], but further work is necessary to deal with higher orders. This is mainly due to the cost of computation that is required to determine the reduced Gr¨ obner basis of the ideal associated to each partial Latin square. Such a computation is extremely sensitive to the number of involved variables, and the length and degree of the generators [20–22,28]. In order to reduce the mentioned cost, we introduce in this paper the notion of affine algebraic set of a partial Latin square. Within the framework of the character theory of finite quasigroups, Johnson [30] introduced the determinant of a Latin square L=(lij )as that one of the square matrix XL=(xlij ). We deal with the analogous matrix that is related to a partial Latin square, but focus on the affine algebraic set of the zero-dimensional binomial ideal whose generators are of the form xixj−xlij , for all non-empty cell (i, j). We expose how the isomorphism invariants of such an affine algebraic set reduce the cost of computation that is required to distribute partial Latin squares into isomorphism classes. The study of new invariants to facilitate the classification of partial Latin squares is currently an active research area [6,18,43]. The paper is organized as follows. Section 2deals with some preliminary concepts and results on partial Latin squares and computational algebraic geometry that are used throughout the paper. Sections 3and 4focus on those conditions under which two given partial Latin squares have, respectively, the same or isomorphic affine algebraic sets. In particular, we prove that isomorphic Latin squares give rise to isomorphic affine algebraic sets, but the reciprocal is not true in general. As an illustrative example, we enumerate the isomorphism classes of the affine algebraic sets of all partial Latin squares of order up to three. In Section 5, we expose how the computation of affine algebraic sets of partial Latin squares lowers the computational cost that is required to determine their distribution into isomorphism classes. Due to the high dependence on notation, a glossary of symbols is shown in Appendix. 2 Preliminaries Let us review some basic concepts and results on partial Latin squares and Computational Algebraic Geometry that are used throughout the paper. We refer the reader to the monographs [8,25] for more details on both topics. 2.1 Partial Latin squares Let Lndenote the set of partial Latin squares of order nhaving the set [n]:={1,...,n} as set of symbols. Every partial Latin square L=(lij )∈Lnis determined by its set of entries E(L) := {(i,j,l ij ):i, j, lij ∈[n]}. The cardinality of this set constitutes the weight of L, which coincides with the number of its non-empty cells. Thus, for instance, the partial Latin square L1≡ 2 3 1 1 ∈L3 has set of entries E(L1)={(1,2,2), (1,3,3), (2,1,1), (3,2,1)}and weight four. A partial Latin square is said to be trivial if its weight is zero. Let Sndenote the symmetric group on nelements. Permutations of rows, columns, and symbols of partial Latin squares preserve the set Ln. Thus, two partial Latin squares L=(lij )and L=(l ij )in Lnare called isotopic if there exists a triple =(f,g,h) ∈Sn×Sn×Snsuch that E(L)={(f (i), g(j), h(lij )):(i,j,l ij )∈ E(L)}. In such a case, we denote L=L. The triple (f,g,h)is an isotopism from Lto L. This constitutes an isomorphism if f=g=h, in which case, the partial Latin squares under consideration are called isomorphic. In such a case, we denote Lf=L. Thus, for instance, the previously mentioned partial Latin square L1is isotopic to the partial Latin square L2≡ 3 2 1 3 ∈L3 by means of the isotopism ((123), (12)(3), (13)(2)) ∈S3×S3×S3.Further,two partial Latin squares Land Lof the same order are said to be conjugate if there exists a permutation π∈S3such that E(L)={(iπ(1),i π(2),i π(3)):(i1,i 2,i 3)∈E(L)}. Every partial Latin square has, therefore, six conjugates (not necessarily distinct from each other). Thus, for instance, the partial Latin square L3≡ 3 1 1 2 ∈L3 is conjugate of the previously mentioned partial Latin square L2by means of the permutation (123)∈S3. Finally, two partial Latin squares are said to be paratopic if one of them is isotopic to a conjugate of the other. Thus, for instance, the previously mentioned partial Latin squares L1and L3are paratopic. Remark that to be isotopic, isomorphic, conjugate, or paratopic are equivalence relations among partial Latin squares. We deal now with the use of Latin squares as scramblers within the context of the encryption-decryption process described in the introductory section. Particularly, we focus on the construction of the mentioned image patterns introduced by Dimitrova and Markovski [10,11]. To this end, let us consider a Latin square L=(lij )∈Ln, a pair of positive integers m, r ∈N, a sequence S=(s1,...,s r−1), and a plaintext T=t1...t m, with si,t j∈[n],forall1≤i<rand 1 ≤j≤m. Let us denote T1=Tand Ti=Esi−1(Ti−1),forall1<i≤r. Then, the r×mimage pattern derived from L,S,andTis the r×marray satisfying that, for each i∈[r], the entries of its ith row coincide sequentially with the characters of Ti. We denote IS,T (L) this array. Example 1 Let us consider the Latin square L≡ 1 2 3 2 3 1 3 1 2 ∈L3, the sequence S=(1,2,2,3,3,3)and the plaintext T=123123. Then, IS,T (L) ≡ 1 2 3 1 2 3 1 2 1 1 2 1 2 3 3 3 1 1 3 2 1 3 3 3 2 3 3 2 1 3 1 3 2 3 3 2 3 2 3 2 1 2 .  The following result implies that, in order to analyze the set of image patterns of the set Ln, it is enough to focus on a representative Latin square of each one of its isomorphism classes. It follows straightforwardly from the notion of isomorphism of Latin squares and the described encryption process. Lemma 1 Let fbe an isomorphism between two Latin squares L, Lf∈Ln, and let us consider a sequence S=(s1,...,s r−1)and a plaintext T=t1...t m, with si,t j∈[n], for all i<rand j≤m.Letf(S)=(f (s1),...,f(s r−1)) and f(T)= f(t 1)...f(t m). Then, the image patterns IS,T (L) and If (S),f (T )(Lf)coincide up to a permutation of their symbols. More specifically, a cell (i, j) in Ir,m S,T (L) contains a symbol αij ∈[n]if and only if the corresponding cell (i, j) in If (S),f (T )(Lf) contains the symbol f(α ij ). In practice, image patterns based on Latin squares of order nare represented as pixel arrays so that each symbol in the pattern under consideration is uniquely replaced by a color within a given palette of ncolors. In order to illustrate this fact, let us consider the following Latin squares. 1 2 3 2 3 1 3 1 2 1 2 3 3 1 2 2 3 1 1 3 2 2 1 3 3 2 1 1 3 2 3 2 1 2 1 3 2 1 3 1 3 2 3 2 1 L3,1L3,2L3,3L3,4L3,5 They are respective representatives of the five isomorphism classes of the set L3. Each pixel array I3,i in Fig. 1, where 1 ≤i≤5, represents a 120×120 image pattern derived from the Latin square L3,i, the constant sequence S=(2,...,2),andthe constant plaintext T=1...1. Lemma 1, together with the fractal character of all the pixel arrays in Fig. 1, implies that every quasigroup of order three is fractal [10]. Observe also from Lemma 1 that all these pixel arrays make easy to distinguish visually all the isomorphism classes of the set L3except for the first two arrays, I3,1and I3,2, which require a more trained eye to distinguish them. Fig. 1 Image patterns based on the five isomorphism classes of L3 We introduce here a general approach to make easier this distinction. This consists of representing separately the contribution of each cell within the Latin square Lunder consideration on the construction of the corresponding image pattern I= (αij ). To this end, we consider the quasigroup Q=([n],·)having Las its multiplication table. Then, for each pair (k, l) ∈[n]×[n],wedefinether×marray Ak,l(I)=(ak,l ij )so that ak,l ij =αij if and only if the encrypted symbol αij has been obtained as the product k·l. Otherwise, ak,l ij =0. Example 2 In the context of Example 1, we have that A3,1(IS,T (L)) ≡ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 3 0 0 0 0 0 0 3 3 0 0 3 0 0 0 0 0 0 0 3 0 3 0 0 0 0 0 .  We define the atomic decomposition of an image pattern Ibased on a Latin square of order nas the n×narray A(I)so that, for each i, j ∈[n], its cell (i, j) contains the array Ai,j (I), which we call an atom of A(I). Thus, for instance, Fig. 2shows the atomic decomposition of both image patterns I3,1and I3,2in Fig. 1. The zero symbols of each atom is colored in black. The following result ensures that the set of atoms within the atomic decompositions of two isomorphic Latin squares coincide up to permutation of their non-zero symbols. It follows straightforwardly from Lemma 1. Proposition 1 Under the assumptions of Lemma 1, the atoms Ai,j (IS,T (L)) and Af (i),f (j)(If (S),f (T )(Lf)) coincide up to their non-zero symbols. More specifically, the non-zero symbol of the former is α∈[n]if and only if that one of the latter is f(α). Proposition 1 makes possible to establish certain conditions that should be satisfied by any possible isomorphism between two given Latin squares. Thus, for instance, we can observe in Fig. 2that any possible isomorphism fbetween the Latin squares L3,1and L3,2should map the atom A1,1(I3,1)into the atom A1,1(I3,2), because the latter is the only atom within the atomic decomposition A(I3,2)that coincides with Fig. 2 Atomic decompositions of the image patterns I(L3,1)and I(L3,2) the former, even regardless of the color. As a consequence, it should be f(1)=1. Nevertheless, a detailed inspection of Fig. 2enables us to ensure that no such an isomorphism exists. Observe to this end that, again even regardless of the color, there are no coincidence among any of the rest of atoms within the atomic decompositions A(I3,1)and A(I3,2). Since visual inspections are very difficult to be done in general, alternative approaches are, therefore, required. In this paper, we propose to make use of computational algebraic geometry in this regard. 2.2 Computational algebraic geometry Let K[Xn]be the multivariate polynomial ring over a given field Kthat is defined on the finite set of variables Xn:= {x1,...,x n}.Azero of a set of polynomials S⊆K[Xn]is any point P∈Knsuch that f(P) =0, for all f∈S.Anaffine algebraic set in the affine space Knis any subset V⊆Knformed by all the zeros of a set of polynomials in K[Xn].Thisisirreducible if it is not the union of two non-empty proper affine algebraic subsets. Every affine algebraic set is uniquely decomposed into a finite union of irreducible components so that none of them is a proper subset of another one. The dimension of an affine algebraic set Vis the maximal length of any chain of irreducible components of Vminus one. This is denoted dim(V ). Amorphism between two affine algebraic sets V1and V2in Knis any map φ:V1→V2such that there exist npolynomial functions, f1,...,f n∈K[Xn],satisfying that φ(P) =(f1(P),...,f n(P )), for all P∈V1.Thisisanisomorphism if φis a bijection whose inverse is a morphism from V2to V1. In this case, both affine algebraic sets are said to be isomorphic. Any property of affine algebraic sets that ispreservedbyisomorphismsissaidtobeanisomorphism invariant.Examplesof isomorphism invariants of an affine algebraic set are its dimension, its cardinality in case of being zero-dimensional, and the number of irreducible components. An ideal is a subset I⊆K[Xn]satisfying that 0 ∈I;p+q∈I,forallp, q ∈I; and p·q∈I,forallp∈Iand q∈K[Xn]. The ideal generated by a finite set of polynomials {p1,...,p k}⊆K[Xn]is defined as p1,...,p k:= k  i=1 qi·pi:qi∈K[Xn]. It is binomial if all its generators are. Further, it is radical if every polynomial p∈ K[Xn]belongs to Iwhenever there exists a positive integer m∈Nsuch that pm∈I. The affine algebraic set that is formed by all the zeros of the polynomials within Iis denoted V(I). The ideal Iis zero-dimensional if dim(V(I)) =0. The leading monomial of a polynomial in K[Xn]is its largest monomial with respect to a given multiplicative well-ordering whose smallest element is the constant monomial 1. A Gr¨ obner basis of an ideal I⊆K[X]is any subset G⊆Iwhose leading monomials generate the same ideal that is generated in turn by all the leading monomials of the non-zero polynomials of I. This is reduced if all its polynomials are monic and no monomial of a polynomial in Gis generated by the leading monomials of the rest of polynomials in the basis. The reduced Gr¨ obner basis of Iis unique and can always be computed from Buchberger’s algorithm [3]. Its decomposition into finitely disjoint subsets enables one to determine the irreducible components of V(I) [23,29,40]. The computation of a reduced Gr¨ obner basis is extremely sensitive to the number of variables, and the length and degree of polynomials in the ideal [20–22,28]. The following two results illustrate this fact in case of dealing with the field Qof rational numbers or a finite field Fq, with qa power prime. Theorem 1 ([28]) The complexity to compute the reduced Gr¨ obner basis of a zerodimensional radical ideal over the field Qof rational numbers is dO(n),wheredis the maximal degree of the polynomials of the ideal, and nis the number of variables. Theorem 2 ([20]) The complexity time that is required to compute the reduced Gr¨ obner basis of an ideal p1,...,p m,p q 1−p1,...,p q m−pmover a polynomial ring Fq[Xn],wherep1,...,p mare polynomials given in sparse form and have longest length l,isqO(n)+O(m2l). Here, sparsity refers to the number of monomials. 3 The affine algebraic set of a partial Latin square Let Kbe a field and let L=(lij )be a partial Latin square in Ln.Wedefinetheaffine algebraic set of Lover Kas the affine algebraic set VK(L) ⊆Knof the binomial ideal I(L):=  xixj−xlij :(i,j,l ij )∈E(L).(1) Particularly, if Lis the trivial partial Latin square of order n,thenI(L) ={0}and hence, VK(L) =Kn. Throughout this paper, we consider the first three variables x1, x2,andx3to be, respectively, x,y,andz. Example 3 Let us consider the Latin square L3,2∈L3described in Section 2,and let Kbe a field. According to (1), each entry of the Latin square L3,2maps into a binomial in K[x,y,z]. Thus, for instance, the triples (1,1,1)and (1,2,2)in the set of entries E(L3,2)map, respectively, into the binomials x2−xand xy −y.The complete map is schematically represented as follows, where we take into account that the product of variables is commutative. 123 312 231 → x2−xxy −y z −z xy −z y2−xyz −y xz −yyz −z z2−x The nine binomials appearing as entries within the last array constitute the generators of the binomial ideal I(L 3,2). Observe in particular that the binomial y−zbelongs to such an ideal, because y−z=(xy −z) −(xy −y). Then, the binomial x−zalso belongs to the ideal, because x−z=y(y −z) +(yz −z) −(y2−x). As a consequence, x=y=zin the coordinate ring K[x,y,z]/I (L3,2). Thus, we have, for instance, that I(L 3,2)=x−z, y −z, z2−z. The set {x−z, y −z, z2−z}constitutes indeed a reduced Gr¨ obner basis of the ideal I(L 3,2)with respect to the lexicographical ordering. Further, the affine algebraic set of the Latin square L3,2over the Kis, therefore, the set VK(L3,2)={(0,0,0), (1,1,1)}. A similar study can be made for the rest of representative classes of the set L3, which we showed in Section 2. In particular, VK(L3,1)={(0,0,0)}∪{(a3,a2,a):a∈Ksuch that a3=1} and VK(L3,3)=VK(L3,4)=VK(L3,5)={(0,0,0), (1,1,1)}. Thus, it seems that there is not a clear relationship among affine algebraic sets and isomorphism classes of Latin squares. The goal of the rest of the paper consists of establishing this relationship, together with the characterization and analysis of these new algebraic structures. Let us start our analysis by illustrating in the following example the dependence that affine algebraic sets of Latin squares have on the base field. 4.1 The set VK(L2) For n=2, it is known [17] the distribution of L2into 20 isomorphism classes, for which the following partial Latin squares are class representatives. 1 2 1 2 1 2 2 1 1 2 L1L2L3L4L5L6L7L8 2 1 1 1 1 2 2 1 1 1 1 2 2 1 1 2 2 L9L10 L11 L12 L13 L14 L15 L16 2 1 1 1 2 1 1 2 1 1 2 2 1 L17 L18 L19 L20 In order to determine the isomorphism classes of the set VK(L2), we discard the partial Latin squares L13,L16,L17,andL20, because their related affine algebraic sets coincide, from Lemma 5, with those of L4,L6,L7,andL19, respectively. Further, we discard from Lemma 8 the partial Latin squares L8,L9,L15,andL19,which are respective transposes of L6,L7,L14,andL18. Finally, from Lemmas 8 and 9, we discard the partial Latin square L5, which is isomorphic to the transpose of L4. Table 1shows the affine algebraic sets of those isomorphism classes that have not been discarded. Table 1enables us to ensure that the reciprocal of Lemma 9 is not true in general, because the partial Latin squares L7,L10,andL18 give rise to isomorphic affine algebraic sets. The following result also holds from the table. Theorem 3 Let Kbe a field. If its characteristic is two, then the set VK(L2)is distributed into seven isomorphism classes, which correspond to the affine algebraic sets Table 1 Algebraic sets of the set VK(L2)dim(VK(L)) L VK(L) 2L1K2 1L2{x=0}∪{x=1} L3{y=x2} L4{x=0}∪{y=1} L6{x=1}∪{(0,0)} 0L7{(0,0), (1,1), (−1,1)} L10 {(0,0), (1,1), (1,−1)} L11 {(0,0), (0,1), (1,0), (1,1)} L12 {x=y2,y2+y+1=0}∪{(0,0), (1,1)} L14 {(0,0), (1,1)} L18 {(0,0), (1,1), (1,−1)} of L1,L2,L3,L4,L6,L11, and L14. Otherwise, there exists an eighth isomorphism class associated to L7. Proof From Table 1, the affine algebraic sets of the partial Latin squares L7and L14 coincide if and only if the base field has characteristic two. It is then enough to focus on the affine algebraic set of the partial Latin square L12. Depending on the base field K, this consists of two, three, or four different points. Then, a bivariate polynomial interpolation determines an isomorphism between such an affine algebraic set and that one associated, respectively, to the partial Latin square L14,L7, or L11. 4.2 The set VK(L3) The following results are useful to study the distribution of the set VK(Ln)into isomorphism classes, for n>2. Lemma 10 Let n>2.LetL∈Lnbe such that there exist three different positive integers i, j, k ≤nsatisfying that (a) {(i,j,i),(j,i,k)}⊆E(L),(b) C(L) ∩{(j, k), (k, j)}=∅, and (c) there does not exist i,j∈[n]such that {(j, i, i), (k, j,k)}⊂E(L). Then, VK(L) coincides with the affine algebraic set of the partial Latin square that is obtained by replacing the entry (j,i,k) ∈E(L) by both entries (j,k,i)and (k,j,k). Proof Let L∈Lnbe the new partial Latin square. By the hypothesis, this is welldefined. Observe also that the set of generators of the binomial ideal I(L )coincides with that of I(L)after replacing the generator xjxi−xkin the latter by both binomials xjxk−xiand xkxj−xk. All of them are equivalent, because xi−xk∈I(L) ∩ I(L ). Proposition 5 Let n>2.LetL∈Lnbe such that there exist three different positive integers i, j, k ≤nsuch that {(i,j,i),(j,k,i)}⊆E(L). Then, VK(L) is isomorphic to an affine algebraic set contained in VK(L),whereL∈Lnis such that E(L)= {(1,2,1), (2,3,1)}. Proof Let fbe any permutation on the set [n]that maps, respectively, the elements i, j,andkinto 1,2, and 3. This leads to an isomorphism between Land a partial Latin square L ∈Lnsuch that E(L)⊆E(L). The result follows then from Lemma 4. Example 12 Let us consider the following three partial Latin squares. L1≡ 3 2L2≡ 2 2 3 L3≡ 1 1 3 From Lemma 10, the affine algebraic sets of L1and L2coincide, whatever the base field is. Further, from the proof of Proposition 5, both affine algebraic sets are isomorphic to the affine algebraic set of L3. In the context of both results, we consider here (i,j,k) =(2,1,3). In particular, for any given field K,wehave that VK(L1)=VK(L2)={(a, 0,0):a∈K}∪{(1,a,a):a∈K} and VK(L3)=VK(L2)={(0,a,0):a∈K}∪{(a, 1,a):a∈K}. The next result holds from a simple study of cases based on Proposition 5. Proposition 6 Let L∈L3be such that there exist three different positive integers i, j, k ≤nsuch that {(i,j,i),(j,k,i)}⊆E(L). Then, VK(L) is isomorphic to one of the following affine algebraic sets in K[x,y,z], whatever the base field Kis. a) If dim(VK(L)) =1: – Two non-concurrent straight lines and a common concurrent line to both of them: {x=y=0}∪{x=z=0}∪{x=z, y =1}. – Two concurrent straight lines: {x=z=0}∪{x=z, y =1}. – Two non-concurrent straight lines: {x=y=0}∪{x=z, y =1}. – Two concurrent straight lines and an external point: {x=y=0}∪{x= z=0}∪{(1,1,1)}. – A straight line and two external points: {x=z=0}∪{(0,0,1), (1,1,1)}. –Astraight line and an external point: {x=y=0}∪{(1,1,1)}. b) If dim(VK(L)) =0: – Two points: {(0,0,0), (1,1,1)}. – Three points: {(0,0,0), (0,1,0), (1,1,1)}. – Four points: {(0,0,0), (0,1,0), (0,0,1), (1,1,1)}. It is known [17] the distribution of the set L3into 2029 isomorphism classes. The results exposed throughout the paper enable us to discard the most of them and focus on only 124 classes. The distribution of their respective affine algebraic sets into 30 isomorphism classes is exposed in Table 2, where we also indicate a partial Latin square from which each one of these classes derives. Each one of them is written row after row in a single line, with empty cells represented by zeros. They are labeled from M1to M30. The following result holds straightforwardly from Table 2. Theorem 4 Let Kbe a field. If its characteristic is two, then the set VK(L3)is distributed into 32 isomorphism classes, which correspond to those affine algebraic sets of the partial Latin squares M1–M28 and M33–M36. Otherwise, it is distributed into the 38 isomorphism classes exposed in Table 2. Table 2 Distribution of the set VK(L3)into isomorphism classes dim LVK(L) 3M1≡000 000 000 K3 2M2≡100 000 000 {x=0}∪{x=1} M3≡010 000 000 {x=0}∪{y=1} M4≡120 000 000 {x=1}∪{x=y=0} M5≡023 000 000 {x=1}∪{y=z=0} M6≡123 000 000 {x=1}∪{(0,0,0)} M7≡200 000 000 {y=x2} M8≡030 000 000 {z=xy} 1M9≡120 030 000 {x=1,z=y2}∪{(0,0,0)} M10 ≡100 020 000 {x=y=0}∪{x=y=1}∪{x=0,y =1}∪{x=1,y =0} M11 ≡010 200 000 {x=y=0}∪{x=y=1} M12 ≡010 300 000 {x=z=0}∪{x=z, y =1} M13 ≡013 000 000 {x=z=0}∪{x=1,y =z} M14 ≡010 001 000 {x=y=0}∪{x=z=0}∪{x=z, y =1} M15 ≡100 001 000 {x=y=0}∪{x=z=0}∪{x=1,yz=1} M16 ≡013 000 000 {x=z=0}∪{x=y=1}∪{y=1,z=0} M17 ≡100 002 000 {x=y=0}∪{x=z=1}∪{x=1,y =0}∪{x=0,z=1} M18 ≡010 001 020 {x=y=0}∪{(1,1,1)} M19 ≡130 003 000 {x=z=0}∪{(1,0,0), (1,1,1)} M20 ≡120 003 000 {x=y=1}∪{x=1,z=0}∪{(0,0,0)} M21 ≡012 000 000 {xz =1,y =1}∪{x=y=0} M22 ≡012 003 000 {xz =1,y =1}∪{(0,0,0)} M23 ≡200 002 000 {y=x2,z=1}∪{x=y=0} M24 ≡123 030 000 {x=1,z=y2}∪{(0,0,0)} M25 ≡200 001 000 {xz =1,yz 2=1}∪{x=y=0} M26 ≡100 030 000 {x=0,z=y2}∪{x=1,z=y2} M27 ≡230 000 000 {y=x2,z=x3} M28 ≡200 030 000 {y=x2,z=x4} M29 ≡210 000 000 {x=y=0}∪{x=y=1}∪{x=−1,y =1} M30 ≡210 003 000 {x=y=1}∪{x=y=−1}∪{(0,0,0)} M31 ≡200 003 000 {y=x2,z=0}∪{x=y=1}∪{x=y=−1} M32 ≡300 030 000 {y=−x,z =x2}∪{y=x,z =x2} 0M33 ≡012 200 300 {(0,0,0), (1,1,1)} M34 ≡130 002 000 {(0,0,0), (1,1,1), (1,0,0)} M35 ≡100 002 030 {(0,0,0), (1,1,1), (1,0,0), (0,1,1)} M36 ≡100 020 003 {(0,0,0), (1,1,1), (1,0,0), (0,1,1), (0,1,0), (0,0,1), (1,0,1), (1,1,0)} M37 ≡032 001 000 {(0,0,0), (1,1,1), (1,−1,−1), (−1,1,−1), (−1,−1,1)} M38 ≡100 023 002 {(0,0,0), (1,1,1), (1,0,0), (0,1,1), (0,1,−1), (1,1,−1)} 5 Effectiveness of the method Let F={fij :i, j ∈[n]} and K[F]respectively denote the set of n2variables {fij :i, j ∈[n]} and the related multivariate polynomial ring over a field K. Lemma 11 Two partial Latin squares L, L∈Lnare isomorphic if and only if the affine algebraic set of the following ideal in K[F]is non-empty I(L,L ):=  f2 ij −fij :i, j ∈[n] + 1−i∈[n]fij :j∈[n]+1−j∈[n]fij :i∈[n] + fiifjj(fkk−1):(i,j,k)∈E(L),(i,j,k)∈E(L). Proof Let P=(p11,...,p nn)be a zero of the ideal I(L,L ). The first subideal of I(L,L )involves Pto belong to the set {0,1}n2. The second and third ones imply that the map f:[n]→[n]that is defined so that f(i) =jif pij =1isa well-defined permutation of the symmetric group Sn. Finally, the fourth one involves fto be an isomorphism between the partial Latin squares Land L. To see it, let (f (i), f (j), k)∈E(L)be such that (i,j,k) ∈E(L),forsomek∈[n].Since pif (i) =pjf (j) =1, the fourth subideal of I(L,L )implies that pkk=1 and hence, k=f(k). Lemma 11 enables one to make use of computational algebraic geometry in order to distribute a given set of partial Latin squares into isomorphism classes. In particular, the affine algebraic set V(I (L, L)) can be computed by means of the reduced Gr¨ obner basis of the ideal I(L,L )[23,29,40]. The following result shows how the cost of computation that is required to this end is, however, extremely sensitive to the number of variables and the length and degree of the generators of I(L,L ). Proposition 7 The complexity to compute the reduced Gr¨ obner basis of the ideal I(L,L )in Lemma 11 is a) 3O(n2),ifK=Q, the field of rational numbers. b) qO(n2)+O(n5),ifK=Fq, the finite field of order a prime power q. Proof The result holds from Theorems 1 and 2 once we prove that the ideal I(L,L ) in Lemma 11 is zero-dimensional and radical. The first condition derives from the fact of being V(I (L, L)) ⊂{0,1}n2, whereas the second one follows from Seidenberg’s Lemma (see Proposition 3.7.15 in [25]), once we observe that, for any three positive integers i, j, k ≤n, the unique monic generator of I(L,L )∩K[F]is the square-free polynomial f2 ij −fij . Algebraic sets of partial Latin squares constitute an efficient alternative to lower this computational cost. Particularly, Lemma 9 implies that, under the assumptions of Lemma 11, none computation is required to ensure that V(I (L, L)) =∅whenever the affine algebraic sets VK(L) and VK(L)are not isomorphic. Isomorphism invariants of affine algebraic sets can, therefore, be considered as new isomorphism invariants of partial Latin squares. Further, the computational cost that is required to determine the affine algebraic set V(I (L, L)) is much lower than that one exposed in Proposition 7. More specifically, a similar proof to that one exposed in the mentioned result enables us to ensure that the complexity to compute the reduced Gr¨ obner basis of the ideal defined in (1)is 2O(n) over the field Qand qO(n) +O(n4)over the finite field Fq, with qaprime power. We have implemented all the previous results in the open computer algebra system for polynomial computations SINGULAR [7] and we have checked the efficiency of using affine algebraic sets of partial Latin squares to lower the cost of computation exposed in Proposition 7. Figure 3shows the average run time that both methods (with and without using affine algebraic sets) require, in a system with an Intel Core i7-2600, with a 3.4-GHz processor and 16 GB of RAM, to distribute into isomorphism classes a set of 1000 partial Latin squares of order n≤3 and weight m≤n2that are randomly generated in the next way: 1. We begin with a trivial partial Latin square of order nand attempt xtimes to add an entry (i,j,k)chosen randomly uniform from [n]×[n]×[n]. 2. If the random entry does not give rise to a partial Latin square (that is, if the pair (i, j) is already in the domain, or adding the entry introduces a repeated symbol in a row or a column of the array), we do nothing. This way for generating random partial Latin squares has already been used in [42,43]. Fig. 3 Computational cost required to distribute the set Lninto isomorphism classes 6 Conclusion and further studies In this paper, we have introduced the affine algebraic set of a finite partial Latin square and several results have been exposed to study when two such affine algebraic sets are equal or isomorphic. We have also introduced two new concepts that enable us to deal with new ways of classifying partial Latin squares according to whether they are partial transpose or partial isotopic. Further work is required to delve into both classifications. Particularly, we have determined the isomorphism classes of the set of affine algebraic sets of partial Latin squares of order n≤3. The following question is also established as further work. Problem 4 Let Vbe an affine algebraic set in the set VK(Ln). Which is the smallest weight of a partial Latin square L∈Lnsuch that VK(L) =V? Finally, remark the fact that Lemmas 1 and 9 enable us to ensure that the common use of image patterns and affine algebraic sets of Latin squares constitutes a good alternative to determine isomorphism classes of Latin squares, with a particular interest to be implemented into the encryption process described into the introductory section. Thus, for instance, the common use of Fig. 1together with the fact that VK(L3,1)= VK(L3,2)(as we showed at the beginning of Section 3) implies in an easy way that the five Latin squares L3,1to L3,5really correspond to different isomorphism classes. Of course, further work dealing with Latin squares of higher orders is required to delve into this implementation. Appendix: Glossary of symbols C(L) The set of non-empty cells of a partial Latin square L. E(L) The set of entries of a partial Latin square L. I(L) The binomial ideal related to a partial Latin square L. LnThe set of partial Latin squares of order n. LSThe partial Latin square that results after eliminating a subset S⊆C(L). P(L) The partition of [n]described in Proposition 2. V(I) The affine algebraic set of an ideal of polynomials I. VK(L) The affine algebraic set of a partial Latin square Lover a field K. VK(Ln)The set of affine algebraic sets over a field Kof partial Latin squares of order n. Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. References 1. Adams, W., Loustaunau, P.: An Introduction to Gr¨ obner Bases Graduate Studies in Mathematics, vol. 3. American Mathematical Society, Providence (1994) 2. Bayer, D.: The Division Algorithm and the Hilbert Scheme. PhD Thesis, Harvard University (1982) 3. Buchberger, B.: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. J. Symbolic Comput. 41, 475–511 (2006) 4. Chum, C.S., Zhang, X.: The Latin squares and the secret sharing schemes. Groups Complex Cryptol. 2, 175–202 (2010) 5. Cooper, J., Donovan, D., Seberry, J.: Secret sharing schemes arising from Latin squares. Bull. Inst. Combin. Appl. 12, 33–43 (1994) 6. Danan, E., Falcon, R.M., Kotlar, D., Marbach, T.G., Stones, R.J.: Refining invariants for computing autotopism groups of partial Latin rectangles. Submitted (2018) 7. Decker, W., Greuel, G.M., Pfister, G., Sch¨ onemann, H.: Singular 4-1-1. A computer algebra system for polynomial computations. http://www.singular.uni-kl.de (2018). Accessed 30 September 2018 8. D´ enes, J., Keedwell, A.D.: Latin Squares and Their Applications. Academic Press, New York-London (1974) 9. Dimitrova, V., Markovski, J.: On Quasigroup Pseudo Random Sequence Generator. In: Manolopoulos, Y., Spirakis, P. (eds.) Proceedings of the First Balkan Conference in Informatics, pp. 393–401, Thessaloniki (2004) 10. Dimitrova, V., Markovski, S.: Classification of quasigroups by image patterns. In: Proceedings of the Fifth International Conference for Informatics and Information Technology, pp. 152–160. Bitola, Macedonia (2007) 11. Dimitrova, V., Markovski, S., Mileva, A.: Periodic Quasigroup String Transformations. Quasigroups Related Systems 17, 191–204 (2009) On Quasigroup Pseudo Random Sequence Generator. In: Manolopoulos, Y., Spirakis, P. (eds.) Proceedings of the First Balkan Conference in Informatics, pp. 393–401, Thessaloniki (2004) 12. Falc´ on, R.M.: Latin squares associated to principal autotopisms of long cycles. Application in Cryptography. In: Dumas, J. (ed.) Proceedings of Transgressive Computing 2006, a conference in honor of Jean Della Dora, pp. 213–230. Universidad de Granada, Granada (2006) 13. Falc´ on, R.M.: The set of autotopisms of partial Latin squares. Discret. Math. 313, 1150–1161 (2013) 14. Falc´ on, R.M.: Enumeration and classification of self-orthogonal partial Latin rectangles by using the polynomial method. Eur. J. Combin. 48, 215–223 (2015) 15. Falc´ on, R.M., Falc´ on, O.J., N´u˜ nez, J.: Counting and enumerating partial Latin rectangles by means of computer algebra systems and CSP solvers. Math. Methods Appl. Sci. https://doi.org/10.1002/mma. 4820 (2018). Accessed 30 September 2018 16. Falc´ on, R.M., Mart´ ın-Morales, J.: Gr¨ obner bases and the number of Latin squares related to autotopisms of order 7. J. Symbolic Comput. 42, 1142–1154 (2007) 17. Falc´ on, R.M., Stones, R.J.: Classifying partial Latin rectangles. Electron. Notes Discret. Math. 49, 765–771 (2015) 18. Falc´ on, R.M., Stones, R.J.: Partial Latin rectangle graphs and autoparatopism groups of partial Latin rectangles with trivial autotopism groups. Discret. Math. 340, 1242–1260 (2017) 19. Falc´ on, R.M., Stones, R.J.: Enumerating partial Latin rectangles. Submitted (2018) 20. Gao, S.: Counting Zeros over Finite Fields Using Gr¨ obner Bases. Carnegie Mellon University (2009) 21. Hashemi, A.: Nullstellens¨ atze for zero-dimensional Gr¨ obner bases. Comput. Complex. 18, 155–168 (2009) 22. Hashemi, A., Lazard, D.: Sharper complexity bounds for zero-dimensional Gr¨ obner bases and polynomial system solving. Internat. J. Algebra Comput. 21,703–713 (2011) 23. Hillebrand, D.: Triangulierung Nulldimensionaler Ideale - Implementierung Und Vergleich Zweier Algorithmen. Universitaet Dortmund, Fachbereich Mathematik (1999) 24. Hulpke, A., Kaski, P., ¨ OSterg˚ ard, P.R.J.: The number of Latin squares of order 11. Math. Comp. 80, 1197–1219 (2011) 25. Kreuzer, M., Robbiano, L.: Computational commutative algebra 1. Springer, Berlin (2000) 26. Koscielny, C.: A method of constructing quasigroup-based stream-ciphers. Int. J. Appl. Math. Comput. Sci. 6, 109–121 (1996) 27. Koscielny, C., Mullen, G.L.: A quasigroup-based public-key cryptosystem. Int. J. Appl. Math. Comput. Sci. 9, 955–963 (1999) 28. Lakshman, Y.N.: On the complexity of computing a Gr¨ obner basis for the radical of a zero dimensional ideal. In: Ortiz, H. (ed.) Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, STOC’90, pp. 555–563. ACM, New York (1990) 29. Lazard, D.: Solving zero-dimensional algebraic systems. J. Symbolic Comput. 13, 117–131 (1992) 30. Johnson, K.W.: Latin Square Determinants. In: Algebraic, Extremal and Metric Combinatorics 1986, pp. 146–154. London Math. Soc. Lecture Note Ser. 131 (1988) 31. Kolesova, G., Lam, C.W.H., Thiel, L.: On the number of 88 Latin squares. J. Combin. Theory Ser. A 54, 143–148 (1990) 32. Markovski, S., Dimitrova, V., Samardjiska, S.: Identity sieves for quasigroups. Quasigroups Relat. Syst. 18, 149–163 (2010) 33. Markovski, S., Gligoroski, D., Andova, S.: Using quasigroups for one-one secure encoding. In: Proceedings of Eight Conference Logic and Computer Science (LIRA), pp. 157–162. Novi Sad (1997) 34. Markovski, S., Gligoroski, D., Bakeva, V.: Quasigroup string processing: Part 1. In: Proceedings of Macedonian Academy of Sciences and Arts for Mathematical and Technical Sciences XX, 1-2, pp. 13–28 (1999) 35. Markovski, S., Gligoroski Markovski, J.: Classification of quasigroups by random walk on torus. J. Appl. Math. Comput. 19, 57–75 (2005) 36. Markovski, S., Kusakatov, V.: Quasigroup string processing: Part 2. In: Proceedings of Macedonian Academy of Sciences and Arts for Mathematical and Technical Sciences XXI, 1-2, pp. 15–32 (2000) 37. McKay, B.D., Meynert, A., Myrvold, W.: Small Latin squares, quasigroups, and loops. J. Combin. Des. 15, 98–119 (2007) 38. Moldovyan, N.A., Shcherbacov, A.V., Shcherbacov, V.: On Some Applications of Quasigroups in Cryptography. In: Workshop on Foundations of Informatics, pp. 331–340. Acad. Sci. Moldova, Inst. Math. Comput. Sci., Chis¸in˘ au (2015) 39. Moldovyan, N.A., Shcherbacov, A.V., Shcherbacov, V.A.: Some applications of quasigroups in cryptology. Comput. Sci. J. Moldova 24, 55–67 (2016) 40. M¨ oller, H.M.: On decomposing systems of polynomial equations with finitely many solutions. Appl. Algebra Engrg. Comm. Comput. 4, 217–230 (1993) 41. Shcherbacov, V.: Elements of quasigroup theory and applications. Monographs and Research Notes in Mathematics. CRC Press, Boca Raton (2017) 42. Stones, D.S.: Symmetries of partial Latin squares. Eur. J. Combin. 34, 1092–1107 (2013) 43. Stones, R.J., Falc´ on, R.M., Kotlar, D., Marbach, T.G.: Computing autotopism groups of partial Latin rectangles: a pilot study. Submitted (2018) 44. Stones, R.J., Su, M., Liu, X., Wang, G., Lin, S.: A Latin square autotopism secret sharing scheme. Des. Codes Cryptogr. 80, 635–650 (2015)