Tao R. Finite Automata and Application to Cryptography
Подождите немного. Документ загружается.
8.2 Latin Arrays 285
is an a ∈ I, such that the multiplicity of b in A(i, j, a)isr}.LetT (i, j)=
(T
1
(i, j), T
2
(i, j), T
3
(i, j)); T
2
(i, j)andT
3
(i, j) may be undefined. The set
consisting of T (i, j), i, j =1,...,n,i = j (repetition allowable) is called the
row characteristic set of A.LetGR
A
be a (directed) graph with vertex set N
and arc set (N × N ) \{(i, i),i∈ N }, of which each arc, say (i, j), is labelled
by T (i, j); GR
A
is called the row characteristic graph of A. GR
A
is said to
be symmetric,ifT (i, j)=T(j, i) holds for any i = j; it is considered as
undirected, that is, the two arcs (i, j)and(j, i) are merged into an edge with
endpoints i and j, which is also denoted by (i, j)or(j, i).
Theorem 8.2.3. Let A and B be two (n, k)-Latin arrays. If A and B are
isotopic, then (a) the column characteristic values of A and B are the same,
(b) the row characteristic graphs of A and B are isomorphic, and (c) the row
characteristic sets of A and B are the same.
Proof. (a) Since the identity between two columns keeps unchanged under
row arrangings and renamings and the column characteristic value keeps
unchanged under column arrangings, the column characteristic values of A
and B are the same.
(b)Sincethetypeofasequence(x
1
,...,x
k
) keeps unchanged under col-
umn arrangings and renamings, for any two rows i and j of an (n, k)-Latin
array, T
1
(i, j) keeps unchanged under column arrangings and renamings.
Clearly, π(i, j) keeps unchanged under column arrangings, and a renaming
for A yields the same renaming for π(i, j). Thus T
2
(i, j) keeps unchanged un-
der column arrangings and renamings. It is easy from the definition to prove
that T
3
(i, j) keeps unchanged under column arrangings and renamings. Let
α, β, γ be an isotopism from A to B.LetA
be the result of transforming
A by renaming β and column arranging γ. From the above results, GR
A
and
GR
A
are the same. Since row arranging α transforms A
to B, α transforms
GR
A
(= GR
A
)toGR
B
. It follows that the row characteristic graphs of A
and B are isomorphic.
(c) Immediately obtained from (b).
Corollary 8.2.1. For any two (n, k)-Latin arrays, if the column character-
istic values or the row characteristic sets of them are distinct, then they are
not isotopic.
Theorem 8.2.4. For n =4, 2 k 4, the row characteristic graph of any
(n, k)-Latin array is symmetric.
Proof.LetA be a (4,k)-Latin array. For any i, j,1 i, j 4, i = j,we
use A
ij
to denote the submatrix of A consisting of its rows i, j.
Case k = 2: For any i, j,1 i, j 4, i = j,letc be the number of
different columns of A
ij
with column multiplicity > 1. It is easy to see that
286 8. One Key Cryptosystems and Latin Arrays
T
1
(i, j)=T
1
(j, i)=1· c +0· (4 − c). Whenever c =4,π(i, j)andπ(j, i) exist
and π(j, i)istheinversepermutationofπ(i, j); therefore T
2
(i, j)=T
2
(j, i).
Whenever c<4, π(i, j)andπ(j, i) do not exist. In the case of 0 <c<4,
it is easy to see that T
3
(i, j) is equal to the number of the elements in the
intersection of the elements in the two rows of the submatrix of A
ij
consisting
of columns with column multiplicity 2. Thus T
3
(i, j)=T
3
(j, i). To sum up,
we obtain T (i, j)=T (j, i).
Case k = 3: For any i, j,1 i, j 4, i = j, it is easy to see that the
number of different columns of A
ij
with column multiplicity 3 is equal to
the the number of A
ija
, a =1,...,4 with type trio and that the number of
different columns of A
ij
with column multiplicity 2 is equal to the number of
A
ija
,a =1,...,4 with type twins. Since A
ij
and A
ji
arethesame,wehave
T
1
(i, j)=T
1
(j, i). Let c
3
(respectively c
2
)bethenumbersofA
ija
,a=1,...,4
with type trio (respectively twins). Clearly, π(i, j) is existent if and only if
c
3
+ c
2
=4.Thusπ(i, j) is existent if and only if π(j, i) is existent, and π(j, i)
is the inverse permutation of π(i, j) whenever they are existent. It follows that
T
2
(i, j)=T
2
(j, i) whenever c
3
+ c
2
= 4. In the case of 0 <c
3
+ c
2
< 4, let A
ij
be the submatrix of A
ij
consisting of its columns with column multiplicity
3ifc
3
= 0, with column multiplicity 2 if c
3
=0.Itiseasytoseethat
T
3
(i, j) is equal to the number of the elements in the intersection of the
elements in the two rows of A
ij
.ThusT
3
(i, j)=T
3
(j, i). To sum up, we
obtain T (i, j)=T (j, i).
Case k = 4: For any i, j,1 i, j 4, i = j, it is easy to see that the
number of different columns of A
ij
with column multiplicity 4 (respectively 3)
is equal to the the number of A
ija
, a =1,...,4 with type quad (respectively
trio). Since A
ij
and A
ji
are the same, the number of A
ija
, a =1,...,4with
type quad (respectively trio) and the number of A
jia
, a =1,...,4 with type
quad (respectively trio) are the same. We prove the following proposition.
If A
ija
hastypedoubletwinsandconsistsofb, b, c, c,andifA
jib
and A
jic
have no type double twins, then A
jib
and A
jic
have type twins and one of the
following conditions holds: (a) A
ijb
and A
ijd
have type twins, A
ijc
has type
trio, A
jia
has type double twins, and A
jid
hastypetrio;(b)A
ijb
hastypetrio,
A
ijc
and A
ijd
have type twins, A
jia
has type double twins, and A
jid
has type
trio; (c) A
ijb
, A
ijc
, A
ijd
and A
jia
have type twins, and A
jid
has type double
twins, where {a, b, c, d} = {1, 2, 3, 4}. In fact, since A
ija
consists of b, b, c, c
and A
jib
(respectively A
jic
) has no type double twins, A
jib
(respectively A
jic
)
consists of a, a, c, d (respectively a, a, b, d). Since d does not occur in A
jid
and
occurs 4 times in each row of A, A
jia
consists of d, d, b, b,ord, d, c, c,or
d, d, b, c. In the case where A
jia
consists of d, d, b, b, A
jid
consists of b, c, c, c;
therefore, the condition (a) holds. In the case where A
jia
consists of d, d, c, c,
A
jid
consists of b, b, b, c; therefore, the condition (b) holds. In the case where
8.2 Latin Arrays 287
A
jia
consists of d, d, b, c, A
jid
consists of b, b, c, c; therefore, the condition
(c) holds. Let S
2
(i, j)={a| A
ija
has type double twins,a =1,...,4} and
n
2
(i, j)=|S
2
(i, j)|. From the proposition, for any i, j,1 i, j 4, i = j,
if n
2
(i, j)=1,thenn
2
(j, i) 1. We prove that for any i, j,1 i, j 4,
i = j,ifn
2
(i, j)=2,thenn
2
(j, i) 2. In fact, suppose that A
ija
has type
double twins and consists of b, b, c, c and that A
ije
has type double twins and
consists of f,f, g,g,where{a, b, c, d} = {1, 2, 3, 4} and e ∈{b, c, d}. Consider
the intersection set S = {b, c}∩{f,g}. In the case of |S| =2,wehave{b, c} =
{f,g}.ThusA
jib
and A
jic
have type double twins. Therefore, n
2
(j, i) 2.
In the case of |S| = 1, without loss of generality, we suppose that S = {b}.It
follows that {f,g} = {a, b} or {f,g} = {b, d}. Whenever {f,g} = {a, b},we
have e = c or e = d.Weprovee = c by reduction to absurdity. Suppose to
the contrary that e = c.SinceA
ijd
does not contain d and b, A
ijd
consists of
a, a, c, c.Thusn
2
(i, j) 3. This contradicts n
2
(i, j) = 2. Thus we have e = d.
Since A
ijc
contains no c, A
ijb
has two occurrences of c. Therefore, A
jib
and
A
jic
have type double twins; that is, n
2
(j, i) 2. Whenever {f,g} = {b, d},
we have e = c.SinceA
ijd
contains no d, A
ijb
has two occurrences of d.
Therefore, A
jib
and A
jid
have type double twins; that is, n
2
(j, i) 2. In the
case of |S| =0,wehave{f, g} = {a, d}. It follows that e = b or e = c.
Without loss of generality, we suppose that e = b.SinceA
ijc
contains no
c, A
ijd
has two occurrences of c;sinceA
ijd
contains no d, A
ijc
has two
occurrences of d. Therefore, A
jic
and A
jid
have type double twins; that is,
n
2
(j, i) 2. This completes the proof of that n
2
(i, j) = 2 implies n
2
(j, i) 2.
It is easy to prove that for any i, j,1 i, j 4, i = j,ifn
2
(i, j)=3and
{1, 2, 3, 4}\S
2
(i, j)={a
},thenA
ija
has type quad; therefore, n
2
(j, i)=3.
Clearly, for any i, j,1 i, j 4, i = j,ifn
2
(i, j)=4,thenn
2
(j, i)=4.
To sum up, for any i, j,1 i, j 4, i = j,wehaven
2
(i, j) n
2
(j, i). This
yields that n
2
(j, i) n
2
(i, j). Thus n
2
(i, j)=n
2
(j, i). Noticing that for k =4
types of any A
ija
are quad, trio, double twins, and twins, from results proven
above, we conclude that T
1
(i, j)=T
1
(j, i).
We prove T
2
(i, j)=T
2
(j, i). From the definition, if π(i, j) exists, then the
type of A
ija
is not double twins, a =1,...,4. For any i, j,1 i, j 4, i = j,
suppose that π(i, j) exists. We prove that π(j, i)istheinversepermutation
of π(i, j); since types of a permutation and its inverse permutation are the
same, from the definition, this yields T
2
(i, j)=T
2
(j, i). Let r be the number
of a such that A
ija
hastypequadortypetrio,a =1,...,4. In the case
of r =4,itisevidentthatπ(j, i)istheinversepermutationofπ(i, j). In
the case of r = 3, suppose that A
ija
, A
ijb
and A
ijc
have type quad or type
trio, where {a, b, c, d} = {1, 2, 3, 4}.ThenA
ijd
has type twins. Without loss
of generality, A
ijd
consists of a, b, c, c. It follows that A
ija
and A
ijb
contain
one c. It reduces to two cases: (a) A
ijc
consists of d, d, d, d, A
ija
consists of
288 8. One Key Cryptosystems and Latin Arrays
b, b, b, c,andA
ijb
consists of a, a, a, c;or(b)A
ija
consists of d, d, d, c, A
ijb
consists of a, a, a, c,andA
ijc
consists of b, b, b, d.Itiseasytoverifythat
π(i, j)=π(j, i)=(ab)(cd) in case (a) and that π(i, j)=(dcba)andπ(j, i)=
(abcd) in case (b). Thus π(j, i) is the inverse permutation of π(i, j). In the
case of r = 2, suppose that A
ija
and A
ijb
have type quad or type trio,
where {a, b, c, d} = {1, 2, 3, 4}.ThenA
ijc
and A
ijd
have type twins. Thus
A
ijc
contains a, b, d and A
ijd
contains a, b, c. This yields that A
ija
and A
ijb
have type trio; therefore, without loss of generality, A
ija
consists of c, c, c, b
and A
ijb
consists of d, d, d, a. Then two cases are possible: (a) A
ijc
consists
of a, a, b, d,andA
ijd
consists of a, b, b, c;or(b)A
ijc
consists of a, b, b, d,and
A
ijd
consists of a, a, b, c.Itiseasytoverifythatπ(i, j)=π(j, i)=(ac)(bd)in
case (a) and that π(i, j)=(acbd)andπ(j, i)=(dbca)incase(b).Thusπ(j, i)
is the inverse permutation of π(i, j). In the case of r = 1, suppose that A
ija
has type quad or type trio, where {a, b, c, d} = {1, 2, 3, 4}.ThenA
ijb
, A
ijc
and A
ijd
have type twins. Thus A
ijb
contains a, c, d, A
ijc
contains a, b, d,
and A
ijd
contains a, b, c. Since the number of occurrences of each element
in a row of A is 4, the number of occurrences of any element in A
ija
is at
most 2; this contradicts that A
ija
has type quad or type trio. Thus, the case
r = 1 should not happen. In the case of r =0,A
ije
, e =1, 2, 3, 4havetype
twins. Let π(e) be the element which occurs two times in A
ije
, e =1,...,4.
Then A
ije
consists of π(e) and elements in {1, 2, 3, 4}\{e}, e =1,...,4.
Since the number of occurrences of each element in a row of A is 4, we have
{π(e) | e =1, 2, 3, 4} = {1, 2, 3, 4}. Clearly, π(i, j)=π. It is easy to verify
that π(j, i)=π
−1
.Thusπ(j, i)istheinversepermutationofπ(i, j). To sum
up, we conclude T
2
(i, j)=T
2
(j, i).
In final, from the definition of T
3
(i, j), it is easy to see that for any i, j,
1 i, j 4, i = j, T
3
(i, j)=T
3
(j, i) holds. Since for any i, j,1 i, j 4,
i = j, T
a
(i, j)=T
a
(j, i) holds for a =1, 2, 3, we obtain T (i, j)=T (j, i)for
any i, j,1 i, j 4, i = j.
8.2.4 Autotopism Group
For any n and any k, the group consisting of all isotopisms of (n, k)-Latin
arrays equipped with the composition operation is called the isotopism group
of (n, k)-Latin arrays, denoted by G. Clearly, G can be represented as S
n
×
S
n
× S
nk
,whereS
r
stands for the symmetric group of degree r for any
positive integer r.WedenoteanelementofG by α, β, γ,whereα (the row
arranging), β (the renaming) and γ (the column arranging) are permutations
of the first n, n and nk positive integers, respectively.
For any (n, k)-Latin array A, an isotopism from A to itself is called an
autotopism on A. All autotopisms on A constitute a subgroup of G, denoted
by G
A
, which is referred to as the autotopism group of A.
8.2 Latin Arrays 289
Using a result in group theory, see Theorem 3.2 in [142] for exam-
ple, we have |G
A
||A
G
| = |G|,whereA
G
stands for the isotopy class con-
taining A. Since the order of the isotopism group G of (n, k)-Latin ar-
rays is (n!)
2
(nk)!, the cardinal number of the isotopy class containing A is
|A
G
| =(n!)
2
(nk)!/|G
A
|. Therefore, for enumeration of (n, k)-Latin arrays, we
may first find out all isotopy classes of (n, k)-Latin arrays, then evaluate the
cardinal number of each isotopy class by means of computing the autotopism
group of any Latin array in the isotopy class. The following results are useful
in computing autotopism groups.
We use e to denote the identity element of G,and(i
1
i
2
...i
k
) to denote
the cyclic permutation which carries i
j
into i
j+1
for j<kand i
k
into i
1
.
Therefore, (1) denotes the identity permutation.
Given an arbitrary (n, k)-Latin array A,let
G
A
= {α, β, γ∈G
A
| α =(1),β =(1)},
G
A
= {α, β, γ∈G
A
| α =(1)},
G
A
= {α, β, γ∈G
A
| α(1) = 1}.
It is easy to see that G
A
G
A
G
A
G
A
,wherethesymbol in group
theory stands for “is a subgroup of”. Similarly, let
G
= {α, β, γ∈G | α =(1),β =(1)},
G
= {α, β, γ∈G | α =(1)},
G
= {α, β, γ∈G | α(1) = 1}.
Clearly, we have G
G
G
G,andG
A
G
, G
A
G
, G
A
G
.
G
A
can be obtained by computing G
A
, G
A
, G
A
and G
A
in turn. The
subgroup G
A
can be determined as follows. Partition the column labels of
A into equivalence classes according to the identity relation of columns, i.e.,
i and j belong to the same equivalence class if and only if the i-th column
and the j-thcolumnofA are the same. Denote the equivalence classes with
cardinal number > 1byI
1
,...,I
r
.WeuseS
I
j
to denote the symmetric group
on I
j
.ItiseasytoshowthatG
A
is isomorphic to S
I
1
× S
I
2
× ...× S
I
r
.Let
c
k
...c
2
be the column characteristic value of A.Thenc
i
= |{j | 1 j r,
|I
j
| = i}|. It follows that the order of G
A
is
k
i=2
(i!)
c
i
.
For any subgroup H of a group H
, and any elements h
1
and h
2
in H
,
we use h
1
≡ h
2
(mod H) to denote the condition h
1
h
−1
2
∈ H.
Similar to the case of Latin square, we can prove the following.
Theorem 8.2.5. Let α
i
,β
i
,γ
i
∈G
A
, i =1, 2.
(a) If α
1
= α
2
and β
1
= β
2
,thenγ
1
≡ γ
2
(mod S
I
1
× S
I
2
×···×S
I
r
).
(b) If α
1
= α
2
and γ
1
≡ γ
2
(mod S
I
1
× S
I
2
×···×S
I
r
),thenβ
1
= β
2
.
290 8. One Key Cryptosystems and Latin Arrays
(c) If rows of A are distinct from each other, β
1
= β
2
and γ
1
≡ γ
2
(mod S
I
1
× S
I
2
×···×S
I
r
),thenα
1
= α
2
.
Proof.Letα, β, γ = α
1
α
−1
2
,β
1
β
−1
2
,γ
1
γ
−1
2
.Thenα, β, γ∈G
A
.
(a) Since α
1
= α
2
and β
1
= β
2
,wehaveα = (1) and β = (1). It follows
that α, β, γ∈G
A
. Therefore, we have γ ∈ S
I
1
× S
I
2
×···×S
I
r
.Thatis,
γ
1
≡ γ
2
(mod S
I
1
× S
I
2
×···×S
I
r
).
(b) Since α
1
= α
2
and γ
1
≡ γ
2
(mod S
I
1
× S
I
2
×···×S
I
r
), we have
α = (1) and γ ∈ S
I
1
× S
I
2
×···×S
I
r
.ThusA keeps unchanged under row
arranging α and column arranging γ.Fromα, β, γ∈G
A
, this yields that A
keeps unchanged under renaming β. Since each column of A is a permutation
of elements in N,wehaveβ = (1). This yields β
1
= β
2
.
(c) Since β
1
= β
2
and γ
1
≡ γ
2
(mod S
I
1
× S
I
2
×···×S
I
r
), we have
β = (1) and γ ∈ S
I
1
× S
I
2
×···×S
I
r
.ThusA keeps unchanged under
renaming β and column arranging γ.Fromα, β, γ∈G
A
, this yields that A
keeps unchanged under row arranging α.SincerowsofA are distinct from
each other, we have α =(1).Thusα
1
= α
2
.
Theorem 8.2.6. (a) Let G
1
be a subgroup of G
2
and of G
A
. For any g in
G
2
,the(right) coset gG
1
⊆ G
A
if and only if g ∈ G
A
.
(b) Let g
i
= α
i
,β
i
,γ
i
,i =1, 2.Ifg
1
,g
2
∈ G
A
,theng
1
G
A
= g
2
G
A
if
and only if β
1
= β
2
.
(c) If g
1
,g
2
∈ G
A
,theng
1
G
A
= g
2
G
A
if and only if α
1
= α
2
.
(d) If g
1
,g
2
∈ G
A
,theng
1
G
A
= g
2
G
A
if and only if α
1
(1) = α
2
(1).
Proof. (a) Evident from the definition.
(b) Suppose g
1
,g
2
∈ G
A
.Thenα
1
= α
2
=(1).Thusg
−1
2
g
1
= (1),
β
−1
2
β
1
, γ
−1
2
γ
1
. Therefore, β
1
= β
2
if and only if g
−1
2
g
1
∈ G
A
, if and only if
g
1
G
A
= g
2
G
A
.
(c) Suppose g
1
,g
2
∈ G
A
.Sinceg
−1
2
g
1
= α
−1
2
α
1
,β
−1
2
β
1
,γ
−1
2
γ
1
, α
1
= α
2
if and only if g
−1
2
g
1
∈ G
A
, if and only if g
1
G
A
= g
2
G
A
.
(d) Suppose g
1
,g
2
∈ G
A
. Clearly, α
1
(1) = α
2
(1) if and only if α
−1
2
α
1
(1) =
1 (i.e., α
−1
2
(α
1
(1)) = 1), if and only if g
−1
2
g
1
∈ G
A
, if and only if g
1
G
A
=
g
2
G
A
.
Although parallel results for left coset hold, in this section, it is enough
to use right coset; hereafter, “coset” means “right coset”.
An (n, k)-Latin array A is said to be canonical, if the first row of A is 1 ...1
2 ...2 ...n...n. Partition a canonical (n, k)-Latin array A into n blocks such
that all the elements in the first row of the h-th block of A, denoted by A
h
,are
h, h =1,...,n. For any block A
h
,letc
i
be the number of distinct columns of
A
h
which occur exactly i times in A
h
; c
k
c
k−1
...c
2
is called the column type
of A
h
.Letp
i
be the type of the i-th row of A
h
; the sequence (p
2
,p
3
,...,p
n
)
is called the row type of A
h
.
8.2 Latin Arrays 291
Theorem 8.2.7. Assume that (n, k)-Latin arrays A and B are canonical
and that A can be transformed into B by an isotopism (1),β,γ.Thenfor
any i, 1 i n,columntypes(row types) of blocks A
i
and B
β(i)
are the
same. Moreover, if there is a block of A,sayA
h
, such that the pair of the
rowtypeandthecolumntypeofA
h
is distinct from the ones of other blocks
and that for some positive integer r there is only one column of A
h
with
multiplicity r,thenβ canbedeterminedbysuchacolumn.
Proof. Clearly, for any i, 1 i n, the block A
i
can be transformed into
the block B
β(i)
by some renaming and some column arranging within block.
Since the column type and the row type of a block keep unchanged under
renamings and column arrangings within block, the column type and the row
type of A
i
are the same with ones of B
β(i)
, respectively.
Suppose that A
h
satisfies the conditions mentioned in the theorem. For
any isotopism (1),β,γ which transforms A into B,usingthefirstpartof
the theorem, there is only one block of B of which the column type and the
rowtypearethesamewithonesofA
h
, respectively, and such a block is
the block B
β(h)
. Clearly, there is only one column in the block B
β(h)
with
column multiplicity r, and such a column can be obtained from transforming
the column of A
h
with multiplicity r by renaming β. Since each column of A
is a permutation, such two corresponding columns determine β.
8.2.5 The Case n =2, 3
From the definitions, it is easy to see that any (2,k)-Latin array is a (2,k,k)-
Latin array. Therefore, if A is a (2,k,r)-Latin array, then r = k holds.
Theorem 8.2.8. For any positive integer k, we have I(2,k)=1, U (2,k)=
2k
k
.
Proof.LetA be a canonical (2,k)-Latin array. Since each column of A is
a permutation of 1 and 2, elements in the second row of A are 2 at the first k
columns and 1 at the last k columns. Such a Latin array is denoted by A12k.
Clearly, any (2,k)-Latin array can be transformed into A12k by some column
arranging. Consequently, (2,k)-Latin arrays have a unique isotopy class.
Since a (2,k)-Latin array can be uniquely determined by any row and the
multiplicity of 1 and of 2 in any row are k, the number of distinct (2,k)-Latin
arrays is
2k
k
.
Theorem 8.2.9. For any positive integer k, we have
I(3,k)=
(k +1)/2, if k is odd,
k/2+1, otherwise,
292 8. One Key Cryptosystems and Latin Arrays
U(3,k)=
k
h=(k+1)/2
2(3k)!/(h!(k − h)!)
3
, if k is odd,
k
h=k/2+1
2(3k)!/(h!(k − h)!)
3
+(3k)!/((k/2)!)
6
, otherwise,
and I(3,k,1) = U(3,k,1) = 0 if k>2, I(3, 2, 1) = 1, U (3, 2, 1) = 6!,
I(3, 1, 1) = 1, U(3, 1, 1) = 3!2!.
Proof. For any h, 1 h k,letA(k − h +1)3k be a canonical (3,k)-Latin
array of the form
⎡
⎣
1 ...1
2 ...2
3 ...3
!
"# $
h
1 ...1
3 ...3
2 ...2
!
"# $
k−h
2 ...2
3 ...3
1 ...1
!
"# $
h
2 ...2
1 ...1
3 ...3
!
"# $
k−h
3 ...3
1 ...1
2 ...2
!
"# $
h
3 ...3
2 ...2
1 ...1
⎤
⎦
!
"# $
k−h
.
We first prove that for any (3,k)-Latin array A there exists h, 1 h k,such
that A and A(k − h +1)3k are isotopic. We transform A into its canonical
form, say A
, by some column arranging. Then using column arranging within
block we transform the second row of A
in the form 2 ...23...33...31...1
1 ...12...2 and denote the result by A
.Leth be the number of 2 in block
1row2ofA
. Then the number of 3 in block 1 row 2 of A
is k − h.Since
each row of a (3,k)-Latin array contains exactly k elements i,1 i 3, the
numberof3inblock2row2ofA
is h andthenumberof2inblock3row2of
A
is k −h. Consequently, the number of 1 in block 2 row 2 of A
is k −h,and
the number of 1 in block 3 row 2 of A
is h. Therefore, the first two rows of A
and of A(k − h +1)3k are the same. Since each column of a (3,k)-Latin array
is a permutation of 1, 2 and 3, row 3 is uniquely determined by rows 1 and 2.
Thus A
is equal to A(k − h +1)3k. We conclude that A and A(k − h +1)3k
are isotopic. Notice that A(h +1)3k and A(k − h +1)3k can be mutually
obtained by applying renaming (23) and some column arranging. From the
above results, any (3,k)-Latin array A is isotopic to A(k−h+1)3k,forsomeh,
k h k/2.WenextprovethatA(k −h+1)3k, h = k, k−1,...,k/2 are
not isotopic to each other. Whenever h = k/2andk is even, in the column
characteristic value of A(k − h +1)3k,namely,c
k
...c
2
,wehavec
h
=6,
and c
i
=0fori = h. Whenever h = k, in the column characteristic value
c
k
...c
2
of A(k − h +1)3k,wehavec
h
=3,andc
i
=0fori = h. Whenever
h = k − 1,...,k/2 and h>k/2, in the column characteristic value c
k
...c
2
of A(k−h+1)3k,wehavec
h
= c
k−h
=3,andc
i
=0fori = h, k−h. Therefore,
column characteristic values of A(k − h +1)3k, h = k, k − 1,...,k/2 are
different from each other. From Corollary 8.2.1, they are not isotopic to each
other. To sum up, I(3,k)=(k +1)/2ifk is odd, and k/2 + 1 otherwise.
For U(3,k), we compute the order of the autotopism group of A(k − h +
1)3k. Clearly, the order of G
A(k−h+1)3k
is (h!(k−h)!)
3
. We now compute coset
representatives of G
A(k−h+1)3k
in G
A(k−h+1)3k
. In the case of h>k− h,
8.2 Latin Arrays 293
it is easy to see that there is a column arranging γ =(3k, 3k − 1,...,1)
k
such that the isotopism g = (1), (321),γ keeps A(k − h +1)3k unchanged.
Consequently, g
2
and g
3
= e also keep A(k − h +1)3k unchanged, where e
stands for the identity isotopism. Since h = k − h, for any transposition β
and any column arranging γ the isotopism (1),β,γ is not an autotopism of
A(k − h +1)3k. From Theorem 8.2.6 (b), the coset representatives are g, g
2
and e. It follows that the order of G
A(k−h+1)3k
is equal to 3|G
A(k−h+1)3k
| =
3(h!(k−h)!)
3
. In the case of h = k−h,wehaveh = k/2. It is easy to prove that
there exist column arrangings γ
1
,γ
2
such that (1), (23),γ
1
and (1), (12),γ
2
are autotopisms of A(k−h+1)3k. Since transpositions (23) and (12) can gen-
erate all permutations of 1, 2 and 3, for any renaming β there exists a column
arranging γ such that (1),β,γ is an autotopism of A(k−h+1)3k. Using The-
orem 8.2.6 (b), we have |G
A(k−h+1)3k
| =3!|G
A(k−h+1)3k
| =6(h!)
6
.Weturn
to computing coset representatives of G
A(k−h+1)3k
in G
A(k−h+1)3k
.Itiseasy
to see that there exists a column arranging γ such that (23), (23),γ keeps
A(k − h +1)3k unchanged. From Theorem 8.2.6 (c), it is easy to prove that
|G
A(k−h+1)3k
| =2|G
A(k−h+1)3k
|. We finally compute coset representatives of
G
A(k−h+1)3k
in G
A(k−h+1)3k
. It is easy to show that there exists a column ar-
ranging γ such that g = (321), (1),γ keeps A(k − h+1)3k unchanged. From
Theorem 8.2.6 (d), we have that g, g
2
and e are the all coset representatives.
It immediately follows that |G
A(k−h+1)3k
| =3|G
A(k−h+1)3k
|. To sum up, the
order of G
A(k−h+1)3k
is equal to 3 · 2 · 3(h!(k − h)!)
3
in the case of h>k− h,
or 3 · 2 · 6(h!)
6
inthecaseofh = k − h. Therefore, the cardinal number of the
isotopy class containing A
(k−h+1)3k
is equal to (3!)
2
(3k)!/(3·2·3(h!(k −h)!)
3
)
=2(3k)!/(h!(k − h)!)
3
inthecaseofh>k− h,or(3!)
2
(3k)!/(3 · 2 · 6(h!)
6
)
=(3k)!/((k/2)!)
6
in the case of h = k−h. In the preceding paragraph we have
proven that the isotopy classes containing A
(k−h+1)3k
, h = k, k −1,...,k/2
are all isotopy classes of (3,k)-Latin array. Thus the formula of U(3,k)inthe
theorem holds.
Since the number of columns of a (3,k)-Latin array is 3k and the number
of permutations on {1, 2, 3} is 3!=6, for any (3,k,1)-Latin array we have
3k 6, that is, k 2. Thus I(3,k,1) = U(3,k,1) = 0 if k>2.
It is easy to see that the columns of any (3, 2, 1)-Latin array consists of
all permutations on {1, 2, 3}.Thusanytwo(3, 2, 1)-Latin arrays are column-
equivalent. Therefore, I(3, 2, 1) = 1 and U(3, 2, 1) = 6!.
Consider a (3, 1, 1)-Latin array of which the first row and the first column
are x
1
, x
2
, x
3
. Then the Latin array is uniquely determined by these elements.
In fact, since any row and any column are some permutations of x
1
, x
2
and
x
3
, its elements at the positions (2,3) and (3,2) take x
1
. It follows that its
elements at the positions (2,2) and (3,3) are x
3
and x
2
, respectively.
294 8. One Key Cryptosystems and Latin Arrays
Since any (3, 1, 1)-Latin array can be transformed by rearranging rows and
columns into a (3, 1, 1)-Latin array of which the first row and the first column
are 1, 2, 3, from the result in the preceding paragraph, we have I(3, 1, 1) = 1.
Since the number of permutations on {1, 2, 3} is 3!, we have U(3, 1, 1) =
3!2!.
8.2.6 The Case n =4,k 4
Enumerationof(4, 2)-Latin Arrays
It is known that the number of isotopy classes of Latin squares of order 4 is 2
and the number of Latin squares of order 4 is (4!)
2
, see [31] for example. Since
both (4,1)-Latin arrays and (4,1,1)-Latin arrays coincide with Latin squares
of order 4, we have I(4, 1) = I(4, 1, 1) = 2 and U(4, 1) = U(4, 1, 1) = (4!)
2
.
Another proof of the results using Theorem 8.2.1 will be given later.
Let A142,...,A1142 be (4,2)-Latin arrays as follows:
⎡
⎢
⎢
⎣
11223344
22114433
34341212
43432121
⎤
⎥
⎥
⎦
A142
⎡
⎢
⎢
⎣
11223344
22334411
34411223
43142132
⎤
⎥
⎥
⎦
A242
⎡
⎢
⎢
⎣
11223344
22134413
34341221
43412132
⎤
⎥
⎥
⎦
A342
⎡
⎢
⎢
⎣
11223344
22341413
34432121
43114232
⎤
⎥
⎥
⎦
A442
⎡
⎢
⎢
⎣
11223344
22341413
34412132
43134221
⎤
⎥
⎥
⎦
A542
⎡
⎢
⎢
⎣
11223344
23144123
34431212
42312431
⎤
⎥
⎥
⎦
A642
⎡
⎢
⎢
⎣
11223344
22114433
33441122
44332211
⎤
⎥
⎥
⎦
A742
⎡
⎢
⎢
⎣
11223344
22114433
33441221
44332112
⎤
⎥
⎥
⎦
A842
⎡
⎢
⎢
⎣
11223344
22114433
33442211
44331122
⎤
⎥
⎥
⎦
A942
⎡
⎢
⎢
⎣
11223344
22134413
33441221
44312132
⎤
⎥
⎥
⎦
A1042
⎡
⎢
⎢
⎣
11223344
22344113
33412421
44131232
⎤
⎥
⎥
⎦
A1142
.
Lemma 8.2.4. A142,...,A1142 are not isotopic to each other.
Proof. We compute the column characteristic value and the row charac-
teristic set of Ax42 and represent them in the format:“x: the column charac-
teristic value of Ax42; the row characteristic sets of Ax42”, where the column
characteristic value is in the form c
2
, the row characteristic set is in the form
T
1
(i, j) T
2
(i, j), in order of ij =12, 13, 14, 23, 24, 34, T
3
(i, j) is not listed. We
list the results of column characteristic values and row characteristic sets of
A142, ..., A1142 as follows: