Encyclopaedia of DesignTheory: Latin squares
|Experimental||Other designs||Math properties||Stat properties|
Accordingly, they tabulated all Latin squares up to n=6 (up to isotopy) and recommended choosing a random square from the tables and randomly permuting rows, columns and symbols.
Nowdays, this is no longer regarded as necessary for valid randomization. The row, column and symbol permutations suffice; any Latin square, however structured, will do.
On the other hand, now we do have a general method! In the paper
M. T. Jacobson and P. Matthews, Generating uniformly distributed random Latin squares, J. Combinatorial Design 4 (1996), 405-437there is a Markov chain method for generating a random Latin square of given order. The limiting distribution of the Markov chain makes all Latin squares equally likely. However, little is known about the rate of convergence.
Here is a picture of the R. A. Fisher window in Gonville and Caius College, Cambridge (designed by Maria McClafferty, based on a Latin square used by Fisher; photograph by A. W. F. Edwards).
Dartmouth College Mathematics Department have an order-10 Graeco-Latin square as a logo. Their site includes a remarkable picture of the square projected onto a rotating sphere.
(Note: Of course, no cipher is completely secure in the real world! A one-time pad can be broken if the key is stolen, or if the sender uses it incorrectly, or if the key is not a random string. The above assertion refers to Shannon's theorem, which states that, if the keystring is random, then an interceptor's posterior probabilities on messages after intercepting a ciphertext are the same as the prior probabilities; that is, no information even of a statistical kind is leaked by the cipher.)
Terry Ritter's page Latin Squares in Cryptography gives pointers to this and other applications of Latin squares and orthogonal arrays. See also his Crypto Glossary. I am grateful to Terry Ritter for his comments on this item.
Table of contents | Glossary | Topics | Bibliography | History
Peter J. Cameron
16 September 2004