On non-polynomial Latin squares (Q1877356)

Let \(\mathbb{Z}_n\) be the ring of integers modulo \(n\), let \(L=[l_{ij}]\) be a Latin square of order \(n\) with entries from \(\mathbb{Z}_n\), and let \({\mathcal F}(n)\) denote the set of all polynomial functions \(f:\mathbb{Z}_n\times\mathbb{Z}_n \to\mathbb{Z}_n\). The Latin square \(L\) is called polynomial if there is an \(f\in {\mathcal F}(n)\) such that \(l_{ij}=f(i,j)\) for all \(i,j\in\mathbb{Z}_n\), otherwise \(L\) is non-polynomial, and an \(L\) is most nonpolynomial if the maximum number of pairs \((i,j)\) for which \(l_{i,j}=f(i,j)\) for all \(f\in{\mathcal F}(n)\) is the smallest for all Latin squares of order \(n\). The authors show that nearly all nonprime power order Latin squares are nonpolynomial (those of prime power order are all polynomial). The authors also provide constructions of totally non-polynomial Latin squares (ones in which each row and column is non-polynomial) and briefly discuss why such Latin squares are useful in the design of block cipher algorithms.