We investigate sets of mutually orthogonal latin squares (MOLS) generated by cellular automata (CA) over finite fields. After introducing how a CA defined by a bipermutive local rule of diameter d over an alphabet of q elements generates a Latin square of order qd-1, we study the conditions under which two CA generate a pair of orthogonal Latin squares. In particular, we prove that the Latin squares induced by two Linear Bipermutive CA (LBCA) over the finite field Fq are orthogonal if and only if the polynomials associated to their local rules are relatively prime. Next, we enumerate all such pairs of orthogonal Latin squares by counting the pairs of coprime monic polynomials with nonzero constant term and degree n over Fq. Finally, we present a construction for families of MOLS based on LBCA, and prove that their cardinality corresponds to the maximum number of pairwise coprime polynomials with nonzero constant term. Although our construction does not yield all such families of MOLS, we show that the resulting lower bound is asymptotically close to their actual number.

Mariot, L., Gadouleau, M., Formenti, E., Leporati, A. (2020). Mutually orthogonal latin squares based on cellular automata. DESIGNS, CODES AND CRYPTOGRAPHY, 88(2), 391-411 [10.1007/s10623-019-00689-8].

Mutually orthogonal latin squares based on cellular automata

Mariot, L.
;
Formenti, E.;Leporati, A
2020

Abstract

We investigate sets of mutually orthogonal latin squares (MOLS) generated by cellular automata (CA) over finite fields. After introducing how a CA defined by a bipermutive local rule of diameter d over an alphabet of q elements generates a Latin square of order qd-1, we study the conditions under which two CA generate a pair of orthogonal Latin squares. In particular, we prove that the Latin squares induced by two Linear Bipermutive CA (LBCA) over the finite field Fq are orthogonal if and only if the polynomials associated to their local rules are relatively prime. Next, we enumerate all such pairs of orthogonal Latin squares by counting the pairs of coprime monic polynomials with nonzero constant term and degree n over Fq. Finally, we present a construction for families of MOLS based on LBCA, and prove that their cardinality corresponds to the maximum number of pairwise coprime polynomials with nonzero constant term. Although our construction does not yield all such families of MOLS, we show that the resulting lower bound is asymptotically close to their actual number.
Articolo in rivista - Articolo scientifico
Cellular automata; Mutually orthogonal latin squares; Polynomials; Sylvester matrices
English
2020
391
411
21
Mariot, L., Gadouleau, M., Formenti, E., Leporati, A. (2020). Mutually orthogonal latin squares based on cellular automata. DESIGNS, CODES AND CRYPTOGRAPHY, 88(2), 391-411 [10.1007/s10623-019-00689-8].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/255398
Citazioni
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 6
Social impact