nathanoschmidt / latin-square-toolbox Goto Github PK

************************************************************************
********************** LATIN SQUARE TOOLBOX v1.10 **********************
************************************************************************
***************** By Nathan O. Schmidt and Will Unger ******************
************************************************************************
 
 
************************************************************************
*** SUMMARY ************************************************************
************************************************************************
Welcome to the Latin Square Toolbox! This version contains three tools: 
    0) Latin Square Generator (LSG)
    1) Latin Square Transversal Counter (LSTC)
    2) Latin Square Property Checker (LSPC)
    
[Latin Square Generator Tool]
First, let's summarize the LSG. The LSG contains three Latin square 
generation modes:
    0) Data Set (DS) - The DS mode uses a recursive, selection-based 
    algorithm to generate a data set with a specific number of order-n 
    Latin squares. In theory, the algorithm is capable of generating the
    set of all Latin squares for a given order, but in practice this is 
    only possible for relatively small orders and depends on hardware 
    limitations. To date of writing, the total number of Latin squares
    for a given order-n are only known up for 1 <= n <= 11; for example,
    there are 61,479,419,904,000 order-7 Latin squares and 
    776,966,836,171,770,144,107,444,346,734,230,682,311,065,600,000
    order-11 Latin squares; see OEIS sequence A002860. On a laptop 
    computer, we've used the DS mode to generate proper subsets of 
    Latin squares up to order-30 and beyond. The DS mode requires that
    the user specify the size of the data set and the order of the Latin 
    squares to be generated.
    
    1) Data Set Preloading (DSP) - The DSP mode's algorithm is nearly 
    identical to the DS algorithm, but there is a difference in 
    performance: the DSP mode is capable of generating data sets of Latin 
    squares of higher orders faster than the DS mode, but the DSP mode 
    may skip some of the Latin squares in the process. Therefore, if you 
    want to generate larger data sets of higher order Latin squares 
    faster and don't care if some of the Latin squares may be skipped, 
    then the DSP mode may be more useful. Similarly to the DS mode, the 
    DSP mode requires that the user specify the size of the data set and 
    the order of the Latin squares to be generated.
    
    2) Super-Symmetric (SS) - The SS mode uses a recursive, lifting-and
    -merging algorithm to generate a single prime power order-p^d 
    super-symmetric Latin square, where p is prime and d > 1. If d = 1, 
    then a single prime order-p cyclic Latin square is generated. In short, 
    our new lifting-and-merging algorithm uses prime order-p cyclic Latin 
    squares as "building blocks" to recursively construct order-p^d 
    super-symmetric Latin squares that exhibit a self-similar structure; 
    see [0] for details. In [0] we correctly predicted that this algorithm
    (also termed the "SS-LS-GA" in [0]) generates Latin squares that have 
    the confirmed maximum transversal counts for 3 <= p^d <= 9, and we used 
    this evidence to conjecture that any prime power order-p^d Latin square
    that is generated by this algorithm *may* have the maximum transversal 
    counts for all any prime p with d >= 1. So if you wish to investigate
    this, then we invite you to experiment! Let’s see if our conjecture 
    can stand the test of time! Can one prove or disprove this? In any case, 
    the SS mode requires that the user specify the prime base p and the 
    prime power d of the order-p^d of the Latin square to be generated.

We'll note that the DS and DSP modes contain are our latest and fastest
algorithms for generating Latin square data sets; these were our personal
records that we achieved given the allocated time and resources. The DS
and DSP modes evolved from several prior pre-release versions. Some of
these details are discussed in [0] with benchmark comparisons.
 
[Latin Square Transversal Counter Tool]
Second, let's discuss the LSTC. The LSTC contains one mode for counting the 
number of transversals in a set of Latin squares. The LSTC requires that 
the user specify two parameters: the input file containing a set of order-n 
Latin squares (encoded in the ordered-triple format) and the order of the 
Latin squares in the file. In this current LSTC implementation, all Latin 
squares in the input file must have the same order, which must match the 
user-specified order (a constraint that we may remove in the near future, 
but for now this works well for speed and efficiency purposes). In any case, 
we'll also note that this LSTC mode implements our latest and fastest 
algorithm for counting transversals; through benchmark comparisons we 
discovered that this algorithm set our personal record; see [0] for some 
additional details.

Now let's recall that the three previously mentioned LSG generation modes, 
the LSG requires the user to specify two parameters via command-line 
interface (no GUI... yet!). In this case, the LSG will generate and print 
the resulting Latin square(s) to standard output. Thus, the LSG output 
can simply be redirected to a file, where each square is separated by a 
blank line and represented as an n-by-n array of cells such that each cell 
is encoded as a 3D coordinate in the ordered-triple format (row,column,symbol) 
where each line of cells corresponds to a row of the Latin square. 
Thereafter, a tool such as the LSTC can post-process the Latin squares in 
an LSG output file to count and print the number of transversals in each. 
On the other hand, if the user supplies LSG with any optional parameters, 
then additional meta-data may be included in the output, which currently 
cannot be parsed and ignored by LSTC (a feature that we may add in the near 
future). So in short, if you want LSG's output to be LSTC's input, then 
just specify LSG's two required parameters for a given mode.

[Latin Square Property Checker Tool]
Finally, let's discuss the LSPC. The LSPC is the simplest tool in the
toolbox: it checks a set of order-n *squares* to determine which ones
are actually *Latin squares*; that is, it reports which squares in the 
set (if any) satisfy the Latin Square Property; in other words, it 
reports which order-n squares encode the Cayley table of an order-n 
quasi-group. Thus, for instance, if you have one or more squares in a file
and you want to determine if any of your squares are Latin squares, then
you may use the LSPC. You'll need to make sure that your squares are
encoded in the ordered-triple format that is identical to the default LSG
output because the LSPC requires this input file format (just like the
LSTC). The LSPC requires that the user specify two parameters: the input 
file containing a set of order-n Latin squares (encoded as ordered-triples) 
and the order of the Latin squares in the file. In this current LSPC 
implementation, all Latin squares in the input file must have the same 
order, which must match the user-specified order.
    
We hope that you find our Latin Square Toolbox to be educational and
useful! Remember, this is released under the MIT License, so have fun, 
experiment, build, and learn!

    
************************************************************************
*** LATIN SQUARE BACKGROUND AND MOTIVATION *****************************
************************************************************************
If you don't know what a Latin square or a transversal is, then you
may find this section to be a helpful introduction. For more detailed 
information on Latin squares, we recommend [0] and the numerous rich 
references therein.

Definition: A "Latin square" of order-n is an n-by-n array over a set of 
n symbols, where every symbol appears exactly once in each row and each 
column.

Definition: A "quasi-group" of order-n is a set S of n symbols equipped
a binary operation + that obeys the "Latin Square Property"; that is,
for each a and b in S, there exist unique elements x and y in S such 
that
                a + x = b      and     y + a = b.
Basically, this is an algebraic way to say that every element in S is 
a symbol that appears exactly once in each row and each column of S's 
Cayley table (which is a Latin square).

So an order-n Latin square encodes the Cayley table of an order-n
quasi-group. Thus, for every Latin square, there exists a corresponding
quasi-group, and for every quasi-group, there exists a corresponding
Latin square; so in this sense Latin squares and quasi-groups are 
equivalent! Therefore, a Latin square encodes features of its
representative quasi-group, which is a fundamental algebraic structure
for disciplines such as computing, cryptography, and cyber security.

Certain quasi-groups, such as groups and finite fields, are used to 
construct cryptographic systems such as hash functions or encryption 
algorithms. For example, such cryptographic systems may be used to protect 
your passwords, web traffic, and privacy, etc. Certain features of such 
algebraic structures can impact the computational security of systems. 
In today's world, it is no secret that cryptography and cyber security 
are super important! Thus, to create and maintain strong cryptographic 
systems, it is essential for folks to use the scientific method and the 
mathematical method to construct and evaluate cryptographic systems and 
the underlying algebraic structures used to build these systems. It turns 
out that analyzing a Latin square is equivalent to analyzing its 
representative quasi-group (and vice-versa). In terms of security 
applications, a paramount feature of a Latin square is the following...

Definition: A transversal of a Latin square is a set of entries which 
includes exactly one entry from each row and column, and one of each 
symbol.

More specifically, the number of transversals in a Latin square is a key
feature of interest when evaluating the computational security of a 
cryptographic system. The question regarding the existence of transversals
in Latin squares that encode the Cayley tables of algebraic structures
is far from being resolved and is an area of active investigation.
It is known that counting the pairs of permutations over a finite field
whose point-wise sum is also a permutation is equivalent to counting
the transversals of a Latin square that encodes the Cayley table of the 
finite field's addition group. Therefore, in order to build strong
cryptographic systems, it is desirable to find Latin squares with
*maximum transversal counts* and then use those to build such systems;
in other words, when an algebraic structure passes certain "Latin square
tests", it is a candidate for use in the construction of cryptographic
systems that can be applied to this modern digital age. Indeed, Latin 
squares are elemental to cryptography and cyber security!


************************************************************************
*** INSTALLATION *******************************************************
************************************************************************
The Latin Square Toolbox is written in the Java programming language,
so it should be compatible with systems that are equipped with the Java 
platform. We're using Apache Maven (https://maven.apache.org/) to manage 
the dependencies.

Note: for this version of the release, the install and clean scripts
have only been implemented and tested on Linux with Bash; they are 
currently not available for Mac OSX and Windows.

    [STEP 0] Install the Java Runtime Environment (JRE) and the Java 
    Development Kit (JDK). 
    
    [STEP 1] Install Apache Maven.

    [STEP 2] Download the Latin Square Toolbox from one of the following 
    locations:
        0) SourceForge (https://sourceforge.net/projects/latin-square-toolbox/) 
        1) GitHub (https://github.com/nathanoschmidt/latin-square-toolbox)
    
    [STEP 3] Once the download is complete, then use the command-line
    interface to nagivate to the Latin Square Toolbox's base directory.
    Note: If the toolbox is zipped and/or tarballed, then unzip and/or
    untar it first. :)

    [STEP 4] To compile the Latin Square Toolbox, execute the build script 
    for your operating system via the command-line interface.
        0) For Linux execute: ./linux_build.sh
        1) For Mac OS X execute: <not yet implemented>
        2) For Windows execute: <not yet implemented>
    If all goes well, then the toolbox should be compiled and and ready 
    to go! :D

    [UNINSTALL] To clean/remove the Latin Square Toolbox's compiled binaries,
    Javadocs, and scripts, execute the clean script for your operating system
    via the command-line interface.
        0) For Linux execute: ./linux_clean.sh
        1) For Mac OS X execute: <not yet implemented>
        2) For Windows execute: <not yet implemented>


************************************************************************
*** USAGE ************************************************************** 
************************************************************************

[Latin Square Generator Tool]
In order to generate Latin squares, the general usage for the LSG is:
    $ ./lsg -m <mode> <mode specific arg 1> <mode specific arg 2> [optional args]
The user must specify one of the following generation mode algorithms for 
the "-m <mode>":
        -m ds           # Generate an order-n Latin square data set of size s
        -m dsp          # Generate an order-n Latin square data set of size s 
                        # with preloading
        -m ss           # Generate one order-p^d super-symmetric Latin square
The specifically required arguments for the data set generation modes "-m ds" 
and "-m dsp" are:
        -n <order>      # The Latin square order-n (a positive integer)
        -s <size>       # The data set size s (a non-negative integer); "-s 0" 
                        # generates all
The specifically required arguments for the super-symmetric generation mode 
"-m ss" are:
        -p <base>       # The base p of the order-p^d super-symmetric Latin 
                        # square (a prime integer)
        -d <power>      # The power d of the order-p^d super-symmetric Latin 
                        # square (a positive integer)
The optional arguments for any mode are:
        -t              # Count and print the number of transversals for each 
                        # Latin square
        -T              # Print the transversals for each Latin square (includes 
                        # "-t")
        -h              # Print the transversal heat map for each Latin square 
                        # (also counts transversals)
        -r              # Print each Latin square in human-readable (non-ordered
                        # -triple) form
        -j              # Print the job report summary upon completion

We note that the LSG and LSTC both have the ability to count the 
transversals of Latin squares, but they differ in that the LSG can only 
count transversals "on the fly" as it generates each Latin square, whereas
the LSTC counts the transversals of Latin squares that stored in an input 
file (with an ordered-triple format) containing the default redirected
output of the LSG.
        
(LSG Example 0) To generate a data set with *all* order-5 Latin squares 
use:
    $ ./lsg -m ds -n 5 -s 0        
        
(LSG Example 1) To generate a data set with 1 order-5 Latin square use:
    $ ./lsg -m ds -n 5 -s 1        
        
(LSG Example 2) To generate a data set with 60 order-5 Latin squares use:
    $ ./lsg -m ds -n 5 -s 60

(LSG Example 3) To generate a data set with 60 order-5 Latin squares via
preloading use:
    $ ./lsg -m dsp -n 5 -s 60
    
(LSG Example 4) To generate a single prime order-5 cyclic Latin square 
use:
    $ ./lsg -m ss -p 5 -d 1
    
(LSG Example 5) To generate a single prime power order-3^2 super-symmetric
Latin square use:
    $ ./lsg -m ss -p 3 -d 2
 
(LSG Example 6) To generate a single prime power order-3^2 super-symmetric
Latin square and count its transversals use:
    $ ./lsg -m ss -p 3 -d 2 -t
 
(LSG Example 7) To generate a single prime power order-3^2 super-symmetric
Latin square, count its transversals, and print its transversal list use:
    $ ./lsg -m ss -p 3 -d 2 -T 

(LSG Example 8) To generate a data set with 60 order-5 Latin squares and
count the transversals for each use:
    $ ./lsg -m ds -n 5 -s 60 -t
  
(LSG Example 9) To generate a data set with 60 order-5 Latin squares,
count the transversals for each, and print the transversal list for each
use:
    $ ./lsg -m ds -n 5 -s 60 -T
    
(LSG Example 10) To generate a data set with 60 order-5 Latin squares,
count the transversals for each, print the transversal list for each,
and print the job report summary use:
    $ ./lsg -m ds -n 5 -s 60 -T -j
    
(LSG Example 11) To generate a data set with 60 order-5 Latin squares,
count the transversals for each, print the transversal list for each,
print each square in human-readable form (non-ordered-triple form), and
print the job report summary use:
    $ ./lsg -m ds -n 5 -s 60 -T -j -r
    
(LSG Example 12) To generate a data set with 60 order-5 Latin squares,
count the transversals for each, print the transversal list for each,
print the transversal heat maps for each, and print the job report 
summary use:
    $ ./lsg -m ds -n 5 -s 60 -T -j -h
    
[Latin Square Transversal Counter Tool]
In order to count the number of transversals in Latin squares stored in
an input file (with the ordered-triple format), the general usage for 
the LSTC is:
    $ ./lstc -f <file> -n <order> [optional args]
The required arguments are:
        -f <file>       # The input file containing a set of order-n 
                        # Latin squares in ordered-triple format
        -n <order>      # The Latin square order (a positive integer 
                        # that must match the input file squares)
The optional arguments are:
        -q              # Be quiet! (Don't print anything during the job)
        -T              # Print the transversals for each Latin square
        -h              # Print the transversal heat map for each Latin 
                        # square (also counts transversals)
        -r              # Print each Latin square in human-readable 
                        # (non-ordered-triple) form
        -j              # Print the job report summary upon completion   
    
(LSTC Example 0) To generate a data set with *all* order-5 Latin squares 
with LSG and then count their transversals with LSTC use:
    $ ./lsg -m ds -n 5 -s 0 > output.txt
    $ ./lstc -f output.txt -n 5
    
(LSTC Example 1) To generate a data set with *all* order-5 Latin squares 
with LSG and then count their transversals and print their transversal
lists with LSTC use:
    $ ./lsg -m ds -n 5 -s 0 > output.txt
    $ ./lstc -f output.txt -n 5 -T
    
(LSTC Example 2) To generate a data set with *all* order-5 Latin squares 
with LSG and then count their transversals and print each square in
human-readable form (non-ordered-triple form) use:
    $ ./lsg -m ds -n 5 -s 0 > output.txt
    $ ./lstc -f output.txt -n 5 -T -r
    
(LSTC Example 3) To generate a data set with *all* order-5 Latin squares 
with LSG and then count their transversals and print a job report summary
with LSTC use:
    $ ./lsg -m ds -n 5 -s 0 > output.txt
    $ ./lstc -f output.txt -n 5 -j

(LSTC Example 4) To generate a data set with *all* order-5 Latin squares 
with LSG and then count their transversals, print their transversal heat
maps, and print a job report summary with LSTC use:
    $ ./lsg -m ds -n 5 -s 0 > output.txt
    $ ./lstc -f output.txt -n 5 -j -h  
    
(LSTC Example 5) To generate a data set with *all* order-5 Latin squares 
with LSG and then count their transversals (but be "quiet" and not print 
each individual square along with its transversal count) and print a job 
report summary with LSTC use:
    $ ./lsg -m ds -n 5 -s 0 > output.txt
    $ ./lstc -f output.txt -n 5 -j -q
    
[Latin Square Property Checker Tool]
In order to determine which squares stored in an input file (with the 
ordered-triple format) satisfy the Latin Square Property, the general
usage for the LSPC is:
    $ ./lspc -f <file> -n <order> [optional args]
The required arguments are:
        -f <file>       # The input file containing a set of order-n 
                        # squares in ordered-triple format
        -n <order>      # The square order (a positive integer that must 
                        # match the input file squares)
The optional arguments are:
        -r              # Print each Latin square in human-readable 
                        # (non-ordered-triple) form
        -j              # Print the job report summary upon completion
    
(LSPC Example 0) To determine which order-5 squares in a file named 
"squares.txt" are actually Latin squares use:
    $ ./lspc -f squares.txt -n 5 

(LSPC Example 1) To determine which order-5 squares in a file named 
"squares.txt" are actually Latin squares and print the job report
summary use:
    $ ./lspc -f squares.txt -n 5 -j
    
(LSPC Example 2) To determine which order-5 squares in a file named 
"squares.txt" are actually Latin squares, print the squares in human-
readable form, and print the job report summary use:
    $ ./lspc -f squares.txt -n 5 -j -r

    
************************************************************************
*** HISTORY / REFERENCE ************************************************
************************************************************************
The Latin Square Toolbox was built for the M.S. Mathematics graduate
thesis:

    [0] Schmidt, Nathan O., "Latin Squares and Their Applications to 
        Cryptography" (2016). Boise State University Theses and 
        Dissertations. 1223. http://scholarworks.boisestate.edu/td/1223

Nathan's thesis adviser was Dr. Liljana Babinkostova at the Department
of Mathematics at Boise State University in Boise, Idaho, USA.

In the beginning of the fall semester of 2015, Dr. Babinkostova discussed 
some of her new, cutting-edge research with Nathan, which involved applying
Latin squares to cryptography. Nathan was interested in the idea and 
decided to pursue it as his thesis topic. This topic involved a thorough 
mathematical and computational investigation of Latin squares and their 
transversals for intended cryptographic application. To summarize, the 
primary objectives of the thesis were to:
    0) Efficiently generate Latin squares.
    1) Efficiently count Latin square transversals.
    2) Predict which Latin squares have maximum (and minimum) transversal
    counts.
    3) Apply the above results to build a new cryptographic system.

Thereafter, Nathan began to learn about Latin squares and cryptography
under the guidance of Dr. Babinkostova. In October of 2015, Nathan began
to work on an abstract algebra project involving preliminary research
on finite fields and Latin squares with fellow graduate students 
Will Unger, Sam Dworetzky, and Zeke Mihelcic. Nathan and Will began
developing some preliminary software algorithms for generating Latin 
squares and counting their transversals. In December of 2015, the team
presented the "Square Bandits" project's preliminary mathematical and 
computational Latin square results at the BoiseCrypt 2015 cryptography 
conference.

Nathan needed to generate lots of Latin square data in order help direct 
the thesis research. In the spring semester of 2016, Nathan, along with his 
friend Will who volunteered to help with the research, continued to develop 
and upgrade their software algorithms for generating and analyzing Latin 
squares and transversals; they created, analyzed, and benchmarked numerous 
versions of the various implementations to achieve this data that would
serve as evidence for supporting arguments and making decisions. This joint
research operation primarily consisted of eating pizza, drinking coffee,
programming computers, and solving math problems. 

They continued to search for Latin square features that might predict
maximum transversal counts. This collaboration led to the construction 
of their new "lifting-and-merging" algorithm that uses prime order-p 
cyclic Latin squares (with maximum transversal counts) as "building blocks" 
to build larger prime power order-p^d Latin squares with a self-similar 
structure; this is the algorithm used in the SS mode of the LSG tool 
(termed the "SS-LS-GA" in [0]). Nathan and Will conjectured that these 
self-similar order-p^d Latin squares may have maximum transversal counts 
because the underlying, appropriately arranged prime order-p cyclic 
Latin square have confirmed maximum transversal counts for 2 <= p <= 9.
Note: the order-2 Latin square both have transversal counts of zero,
so the minimum and maximum counts are zero, but for 2^d with d > 1 the 
minimum no longer seems to apply! They generated several self-similar 
Latin squares and compared those transversal counts for 3 <= p^d <= 9 
with the known confirmed maximum transversal counts in the literature 
(see the references cited in [0]) and discovered that their prediction 
was correct! The self-similar prime power order-p^d Latin squares
have confirmed maximum transversal counts for 3 <= p^d <= 9.
This ultimately led to Conjecture 2.100 of [0].

Upon further investigation, they realized that these self-similar 
Latin squares for prime power order-p^d were a generalization of a 
recent algorithm for generating order-2^d "super-symmetric" Latin 
squares created by a separate team (see reference [60] in [0]). Thus,
Nathan and Will realized that the their order-p^d Latin squares
were also "super-symmetric".

Now while they had been viewing finite fields through an algebraic 
lense, they hadn't yet realized that one can apparently view finite 
fields geometrically! They had constructed the lifting-and-merging
algorithm of the LSG's SS mode by viewing the Latin squares as 
geometric objects, but there was still some missing connection.
Then, on one shocking Saturday, they realized that the addition
Cayley tables of prime power order-p^d finite fields are actually
prime power order-p^d super-symmetric Latin squares with a self-similar 
geometric construction! 

Therefore, Nathan used super-symmetric Latin squares to construct
a new generalized and simplified version of the version of Grøstl
hash function (an SHA-3 candidate), which operates over prime power
order-p^d finite fields given some prime p and some d > 1.

And this is the story of the Latin Square Toolbox.
  
************************************************************************
*** CREDIT / ACKNOWLEDGEMENTS ******************************************
************************************************************************
Nathan wishes to thank:

    His adviser Dr. Liljana Babinkostova for her invaluable
    knowledge, insight, and guidance on this great subject.
    
    Will Unger for helping design and implement this Latin Square
    Toolbox, which ultimately led to Conjecture 2.100 of [0].

    Dr. Samuel Coskey, Dr. Marion Scheepers, and Dr. Jyh-Haw Yeh for
    their helpful comments that improved the thesis.

    Sam Dworetzky for his collaboration during the "Square Bandits"
    project.

    Dr. Ian Wanless for answering his questions on Latin square 
    transversals.

    His wife Marissa, for everything

    
************************************************************************
*** LICENSE ************************************************************
************************************************************************
Copyright (C) 2017 Nathan O. Schmidt <[email protected]>
Copyright (C) 2017 Will Unger <[email protected]>
************************************************************************
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
************************************************************************