Tao R. Finite Automata and Application to Cryptography

Подождите немного. Документ загружается.

8.2 Latin Arrays 295

1 : 0; 42, 00, 00, 00, 00, 42 2 : 0; 44, 00, 00, 00, 00, 00

3 : 0; 20, 00, 00, 00, 00, 20 4 : 0; 10, 00, 10, 10, 00, 10

5 : 0; 10, 00, 00, 10, 10, 00 6 : 0; 00, 00, 00, 00, 00, 00

7 : 4; 42, 42, 42, 42, 42, 42 8 : 2; 42, 20, 20, 20, 20, 42

9 : 4; 42, 44, 44, 44, 44, 42 10 : 1; 20, 20, 10, 10

, 20, 20

11 : 1; 10, 10, 10, 10, 10, 10

where T

(i, j)=4, 2, 0 mean “a cycle of length 4”, “two transpositions”,

“no derived permutation”, respectively. It is easy to verify that for any two

distinct Ai42’s either their column characteristic values are diﬀerent, or their

row characteristic sets are diﬀerent. From Corollary 8.2.1, it immediately

follows that A142,...,A1142 are not isotopic to each other. 

Lemma 8.2.5. Any (4, 2)-Latin array is isotopic to one of A142,...,A1142;

any (4, 2, 1)-Latin array is isotopic to one of A142,...,A642 and any (4, 2, 2)-

Latin array is isotopic to A742 or A942.

Proof.LetA be a (4,2)-Latin array. In the proof, by A(i, j)denotethe

element of A at row i column j;byA(i, j − h)denoteelementsofA at

row i columns j to h. Since Latin arrays can be reduced to canonical ones

by rearranging columns, without loss of generality, we suppose that A is

canonical. From Theorem 8.2.4, instead of “from row i to row j”wecansay

“between rows i and j”, for example, the intersection number between rows

i and j; and from

(i, j)=T

(j, i)=1· c

+0· c

,wecansay“thenumber

of twins between rows i and j is c

”, and so on.

We prove by exhaustion that A is isotopic to Ai42 for some i,1 i  11.

There are two cases to consider. Case 1: columns of A are diﬀerent. Case 2:

otherwise.

Case 1: no repeated columns in A. There are ﬁve alternatives according to

the numbers of twins between rows. Case 11: there are two rows of A between

which the number of twins is 4. Case 12: not the case 11 and there are two

rows of A between which the number of twins is 3. Case 13: not the cases 11

and12andtherearetworowsofA between which the number of twins is 2.

Case 14: not the cases 11 to 13 and there are two rows of A between which

the number of twins is 1. Case 15: there is no twins between any two rows of

In case 11, in the sense of row arranging and column arranging we assume

that the number of twins between rows 1 and 2 of A is 4. We subdivide this

case into two subcases according to the derived permutation from row 1 to

row 2 of A. Case 111: the derived permutation can be decomposed into a

product of two disjoint transpositions. Case 112: the derived permutation is

a cycle of length 4.

296 8. One Key Cryptosystems and Latin Arrays

In case 111, in the sense of isotopy we assume that A(2, 1−8) = 22114433.

Note that for the last two rows of any block of A, whenever one has type twins,

so has the other. This yields that A has repeated columns. But this is impos-

sible in case 1. Therefore, in the sense of column transposition within block

we have A(3, 1 −8) = 34341212. Since each column of A is a permutation, for

any column of A the element at any row can be uniquely determined by others

in that column. It follows that A(4, 1−8) = 43432121. [Hereafter, this deduc-

tion and the like are abbreviated to the form: “since last element(s), ...”.]

Therefore, A is isotopic to A142.

In case 112, in the sense of isotopy we assume that A(2, 1−8) = 22334411.

Since A has no repeated columns, in the sense of column transposition

within block we have A(3, 1 − 8) = 34411223. Since last elements, we ob-

tain A(4, 1 − 8) = 43142132. Therefore, A is isotopic to A242.

In case 12, since each element occurs exactly two times in any row of A,

between any two rows of A if the number of twins is at least 3 then it is equal

to 4. This contradicts not the case 11. Therefore, this case can not occur.

In case 13, in the sense of isotopy we suppose that the number of twins

betweenrows1and2ofA is 2. We subdivide this case into three subcases

according to the intersection number between rows 1 and 2 of A. Case 131:

the intersection number is 2. Case 132: the intersection number is 1. Case 133:

the intersection number is 0.

In case 131, in the sense of isotopy we assume A(2, 1 − 4) = 2211. Since

each element occurs exactly once in each column and 2 times in each row of A,

elements in block 3 row 2 of A are uniquely determined, namely, A(2,

5−

6) =

44. [Hereafter, this deduction and the like are abbreviated to the form: “since

unique value(s), ...”.] This contradicts not the cases 11 and 12. Therefore,

this case can not occur.

In case 132, in the sense of isotopy we assume A(2, 1 − 4) = 2233. Since

unique values, we have A(2, 7 − 8) = 11. This contradicts not the cases 11

and 12. Therefore, this case can not occur.

In case 133, in the sense of isotopy we assume A(2, 1−2) = 22, A(2, 5−6) =

44. Since row 2 has already two occurrences of 2 and of 4, elements in blocks

2and4row2are1or3.Sinceblock2row2andblock4row2arenot

twins, in the sense of column transposition within block we have A(2, 3−4) =

A(2, 7−8) = 13. [Hereafter, this deduction and the like are abbreviated to the

form: “since no twins, ...”. ] Since each element occurs once in each column,

in the sense of row transposition we have A(4, 3) = 4. Since last element, we

have A(3, 3) = 3. Since A has no repeated columns, in the sense of column

transposition within block we have A(3, 1 − 2) = 34,A(3, 5 − 6) = 12. Since

last elements, we obtain A(4, 1 − 2) = 43,A(4, 5 − 6) = 21. Consider the

columns in which the elements at row 3 are not determined yet and the

8.2 Latin Arrays 297

elements determined so far do not contain 4. Since such a column is unique,

the place in row 3 which can take value 4 is unique. It immediately follows

that A(3, 4) = 4. [Hereafter, this deduction and the like are abbreviated to

the form: “since unique place(s), ...”.] Since unique value, we have A(3, 7) =

2. Since unique value, we have A(3, 8) = 1. Since last elements, we obtain

A(4, 4) = 1,A(4, 7 − 8) = 32. Therefore, A is isotopic to A342.

In case 14, in the sense of isotopy we assume that there is one twins

between rows 1 and 2, say A(2, 1 − 2) = 22. Since no twins, we have A(2, 5 −

6) = 14 and A(2, 7 − 8) = 13. Since each element occurs exactly two times

in each row of A, elements 3 and 4 in row 2 which are not determined yet

so far can only occur in block 2 row 2. Consequently, in the sense of column

transposition we have A(2, 3−4) = 34. [Hereafter, this deduction and the like

are abbreviated to the form: “since row sum, ...”.] Since each element occurs

once in each column, in the sense of row transposition we have A(4, 3) = 1.

Since last element, we obtain A(3, 3) = 4. Since A has no repeated columns,

in the sense of column transposition within block we have A(3, 1 − 2) = 34.

Since last elements, we have A(4, 1 − 2) = 43. Since unique place, we have

A(4, 5) = 4. Since last element, we have A(3, 5) = 2. At this point, there are

two alternatives according to the value of

A(3, 4), 3 for the case 141, and 1

for the case 142.

In case 141, since unique places, we have A(3, 6) = A(3, 8) = 1,A(4, 7) =

3. Since last elements, we have A(4, 4) = 1,A(4, 6) = A(4, 8) = A(3, 7) = 2.

Therefore, A is isotopic to A442.

In case 142, since unique place, we have A(3, 7) = 3. Since last elements,

we have A(4, 4) = 3,A(4, 7) = 2. Denoting A(4, 8) = a,itiseasytoseethata

takes values 1 or 2. Since row sum, we have A(4, 6) = a



,where1



=2,2



=1.

Since last elements, we have A(3, 8) = a



,A(3, 6) = a. Whenever a =1,A is

isotopic to A542. Whenever a =2,A can be transformed into A542 by row

transposition (12), renaming (12)(34) and some column arranging.

In case 15, in the sense of isotopy we assume A(2, 1 − 2) = 23. We have

A(2, 8) = 3 in the sense of isotopy. (In fact, when 3 does not occur in block 4

row 2, 2 occurs in it since no twins. Thus we can transform A in advance by

renaming (23) and some column arranging.) Since no twins, we have A(2, 3 −

4) = 14. Since unique places, in the sense of column transposition we have

A(2, 5) = 4. Denoting A(2, 7) = b, it is easy to see that b takesvalues1or

2. Since row sum, we have A(2, 6) = b



. In the sense of row transposition

we assume A(3, 1) = 3,A(4, 1) = 4. Since no twins, we have A(4, 2) = 2.

Since last element, we have A(3, 2) = 4. We prove A(3, 3) = 3 by reduction

to absurdity. Suppose to the contrary that A(3, 3) = 3. Since last element,

we have A(4, 3) = 4. It follows that there is a twins between rows 3 and

4. This contradicts the case 15. Therefore, we obtain A(3, 3) = 4. Since

298 8. One Key Cryptosystems and Latin Arrays

last element, we have A(4, 3) = 3. Since no twins, we have A(4, 4) = 1.

Since no twins between rows 2 and 4 exists, we have A(4, 8) = 1. Since last

elements, we have A(3, 4) = 3,A(3, 8) = 2. Since unique places, we have

A(4, 6) = 4,A(4, 7) = 3. Since row sum, we have A(4, 5) = 2. Since last

elements, we have A(3, 5 − 7) = 1bb



. Since no twins between rows 2 and 4

exists, we have b = 1. It immediately follows that b = 2. Therefore, A is

isotopic to A642.

Case 2: A has repeated columns. Subdivide this case into three subcases

according to the number of twins between rows. Case 21: there are two rows

of A between which the number of twins is 4. Case 22: not the case 21 but

there are two rows of A between which the number of twins is 2. Case 23:

otherwise.

In case 21, in the sense of isotopy we assume that there are four twins

between rows 1 and 2. We subdivide this case into two subcases according

to the derived permutation from rows 1 to 2 of A. Case 211: the derived

permutation can be decomposed into a product of two disjoint transpositions.

Case 212: the derived permutation is a cycle of length 4.

In case 211, in the sense of isotopy we assume A(2, 1 − 8) = 22114433,

A(3, 1 − 2) = 33, A(4, 1 − 2) = 44. Since unique values, we have A(3, 3 −

4) = 44,A(4, 3 − 4) = 33. Denoting A(4, 7 − 8) = ab, clearly, a and b take

values 1 or 2. Since row sum, in the sense of column transposition we have

A(4, 5 − 6) = a



. Since last elements, we have A(3, 5 − 8) = aba



.Inthe

sense of column transposition ab may take three values 11,12 and 22, it follows

that A is isotopic to A742,A842 and A942, respectively.

In case 212, in the sense of isotopy we assume A(2, 1 − 8) = 22334411,

A(3, 1 − 2) = 33, A(4, 1 − 2) = 44. Since unique values, we have A(4, 3 − 4) =

11,A(3, 7−8) = 22. Since last elements, we have A(3, 3−4) = 44,A(4, 7−8) =

33. Since row sum, we have A(3, 5 −6) = 11,A(4, 5 − 6) = 22. It is easy to see

that A can be transformed into A942 by row transposition (23), renaming

(23) and some column arranging.

In case 22, in the sense of isotopy we assume that there are two twins

betweenrows1and2ofA. We subdivide this case into three subcases ac-

cording to the intersection number between rows 1 and 2 of A. Case 221: the

intersection number is 2. Case 222: the intersection number is 1. Case 223:

the intersection number is 0.

In case 221, in the sense of isotopy we assume A(2, 1 − 4) = 2211. Since

unique places, we have A(2, 5 − 6) = 44,A(2,

7 − 8) = 33. This contradicts

not the case 21. Therefore, this case can not occur.

In case 222, in the sense of isotopy we assume A(2, 1−2) = 22,A(2, 3−4) =

33. Since unique values, we have A(2, 7 − 8) = 11. Since row sum, we have

8.2 Latin Arrays 299

A(2, 5 − 6) = 44. This contradicts not the case 21. Therefore, this case can

not occur.

In case 223, in the sense of isotopy we assume A(2, 1−2) = 22,A(2, 5−6) =

44,A(3, 1 − 2) = 33,A(4, 1 − 2) = 44. Since no twins, we have A(2, 3 − 4) =

A(2, 7 − 8) = 13. Since unique values, we have A(4, 3 − 4) = 31,A(3, 7) = 2.

Since last elements, we have A(3, 3 − 4) = 44,A(4, 7) = 3. Since no twins,

we have A(3, 8) = 1. Since row sum, in the sense of column transposition

we have A(3, 5 − 6) = 12. Since last elements, we have A(4, 5 − 6) = 21 and

A(4, 8) = 2. Therefore, A is isotopic to A1042.

In case 23, it is easy to show that the number of twins between two rows

of A is equal to 4 whenever it is at least 3. Thus in this case the number of

twins between some two rows of A is equal to 1. In the sense of isotopy we

assume that columns 1 and 2 are the same and A

(2, 1 −2) = 22,A(3, 1 −2) =

33,A(4, 1−2) = 44. Since no twins, we have A(2, 5−6) = 41,A(2, 7−8) = 13.

Since row sum, in the sense of column transposition we have A(2, 3− 4) = 34.

Since unique values, we have A(3, 4) = 1,A(3, 7) = A(4, 6) = 2. Since last

elements, we have A(4, 4) = A(4, 7) = 3,A(3, 6) = 4. Since no twins, we have

A(3, 8) = 1. Since unique places, we have A(3, 3) = 4,A(3, 5) = 2. Since last

elements, we have A(4, 8) = 2,A(4, 3) = A(4, 5) = 1. Therefore, A is isotopic

to A1142.

Since the column characteristic value of any (4, 2, 2)-Latin array is 4, A742

and

A942 are all distinct isotopy class representatives of (4, 2, 2)-Latin array.

That is, any (4, 2, 2)-Latin array is isotopic to A742 or A942. 

Theorem 8.2.10. I(4, 2) = 11, I(4, 2, 1) = 6, I(4, 2, 2) = 2.

Proof. This is immediate from Lemmas 8.2.4 and 8.2.5. 

Theorem 8.2.11. U (4, 2) = 12640320, U (4, 2, 1) = 10281600, U(4, 2, 2) =

60480.

Proof. Denote the order of autotopism group G

Ai42

of Ai42 by n

,i =

1,...,11. Then the number of elements in the isotopy class containing Ai42

is 4!4!8!/n

. Therefore, we have

U(4, 2) =



i=1

4!4!8!/n

,U(4, 2, 1) =



i=1

4!4!8!/n

,U(4, 2, 2) =



i=7,9

4!4!8!/n

We compute G

A142

.InGR

A142

, labels of edges (1, 2) and (3, 4) are the

same, say “red”; labels of other edges are the same and not red, say “green”.

Since columns of A142 are diﬀerent, we have G



A142

= {e},wheree stands

for the identity isotopism. It immediately follows that its order is 1.

300 8. One Key Cryptosystems and Latin Arrays

To compute the coset representatives of G



A142

in G



A142

,notethatan

isotopism α, β, γ on a Latin array can be decomposed into a product

of α, (1), (1) (the row arranging α), (1),β,(1) (the renaming β), and

(1), (1),γ (the column arranging γ), independent of their order. Clearly,

for any isotopism in G



its row arranging component is (1). We then con-

sider the renaming component β so that the renaming β and some column

arranging γ keep A142 unchanged. Since each column of A142 is a permu-

tation, β can be uniquely determined by any two columns, say j and h,of

A142 such that β transforms column h into column j.Foreachh ∈{1,...,8},

take β as the permutation which transforms column h into column 1. For ex-

ample, in the case of h = 3, the renaming β transforms the column 2134

into the column 1234; that is, β = (12). In this way, we obtain eight candi-

dates for β: (1), (34), (12), (12)(34), (13)(24), (1423), (1324) and (14)(23),

which can be generated by (34) and (1324) for example. It is easy to verify

that β transforms A142 into a (4, 2)-Latin array which can be further trans-

formed into A142 by some column arranging, for β = (34) and (1324). It

follows that β transforms A142 into a (4, 2)-Latin array which can be further

transformed into A142 by some column arranging, for all eight candidates.

From Theorem 8.2.6 (b), autotopisms with diﬀerent renamings correspond

to diﬀerent cosets, and autotopisms with the same renaming correspond to

the same coset. Therefore, the coset representatives of all diﬀerent cosets are

((1), (34), ·, (1), (1423), ·), here and elsewhere a dot · in an isotopism repre-

sents some column arranging, and (g

,...,g

) stands for the set generated by

,...,g

(the column arranging component is neglected in the case of coset

representatives of G



in G



). That is, G



A142

=((1), (34), ·, (1), (1423), ·)



A142

=((1), (34), ·, (1), (1423), ·). It immediately follows that the order

of G



A142

is 8.

To compute the coset representatives of G



A142

in G



A142

,letα, β, γ∈G



where the row arranging α is a permutation of 2,3,4. From the proof of Theo-

rem 8.2.3 (b), if α, β, γ is an autotopism of A142, then the row arranging α

is an automorphism of GR

A142

. It follows that edges (1, 2) and (α(1),α(2)),

that is, (1,α(2)), have the same color. Since the edge (1, 2) is the unique

red edge with endpoint 1, we have α(2) = 2 whenever α, β, γ∈G



A142

Thus candidates of α are (34) and (1) in this case. Transform rows of A142

by row transposition (34). Clearly, the result can be further transformed

into A142 by some column arranging. We then obtain a coset representa-

tive (34), (1), ·. Together with another coset representative e,fromTheo-

rem 8.2.6 (c), they are coset representatives of all distinct cosets; that is,



A142

=((34), (1), ·) G



A142

, here and elsewhere (g

,...,g

) stands for the

set generated by g

,...,g

but redundant autotopisms with identical row ar-

8.2 Latin Arrays 301

ranging component are omitted except one in the case of coset representatives

of G



in G



. Consequently, the order of G



A142

is 2 · 8.

To compute the coset representatives of G



A142

in G

A142

,letα, β, γ∈

A142

.Thusα is an automorphism of PR

A142

.Tryα(3) = 1. Since the edge

(3, 4) is red, the edge (α(3),α(4)), that is, (1,α(4)), is red. Since the edge

(1, 2) is the unique red edge with endpoint 1, we have α(4) = 2. It follows

that α = (1423) or (13)(24). Try α = (1423). A142 can be transformed into



⎡

⎢

⎣

33 44 11 22

44 33 22 11

12 12 34 34

21 21 43 43

⎤

⎥

⎦

by row arranging (1423) and some column arranging. It is evident that



can be transformed into A142 by some column arranging. Therefore,

g = (1423), (1), · is an autotopism of A142. It follows from Theorem 8.2.6 (d)

that g, g

and g

= e are coset representatives of all distinct cosets of



A142

in G

A142

.Thatis,G

A142

=((1423), (1), ·) G



A142

, here and elsewhere

,...,g

) stands for the set generated by g

,...,g

but redundant auto-

topisms with identical value of the row arranging at 1 are omitted except one

in the case of coset representatives of G



in G

. Consequently, the order of

A142

is 4 · 2 · 8.

We turn to computing n

. From the column characteristic value, the

order of G



A1142

is 2! =2.

To compute coset representatives of G



A1142

in G



A1142

,sincetherowar-

ranging is restricted to be (1), from Theorem 8.2.7, for the result obtained

from A1142 by applying a renaming β and reducing to a canonical form, the

distribution of column types and row types of its blocks are coincided with

ones for A1142, in particular, β transforms repeated columns of A1142 into

repeated columns of the result. Since there is only one block of A1142 with

repeated columns, β transforms the block with repeated columns into itself.

It follows that β = (1). Therefore, there is only one coset and e is a coset

representative. It immediately follows that G



A1142

= G



A1142

To compute coset representatives of G



A1142

in G



A1142

,letα, β, γ∈G



where the row arranging α is a permutation of 2,3,4. Try α = (234). The row

arranging (234) transforms A1142 into



⎡

⎢

⎣

11 22 33 44

44 13 12 32

22 34 41 13

33 41 24 21

⎤

⎥

⎦

Suppose that A



can be transformed into A1142 by a renaming β and some

column arranging. Since column types of the ﬁrst block of A



and the ﬁrst

302 8. One Key Cryptosystems and Latin Arrays

block of A1142 are the same and diﬀerent from column types of other blocks,

from Theorem 8.2.7, the ﬁrst block of A



is transformed into the ﬁrst block of

A1142 by renaming β and some column arranging. Thus β transforms the col-

umn 1423 into the column 1234; that is, β = (234). It is easy to verify that

(1), (234), · transforms A



into A1142 indeed. Thus (234), (234), · keeps

A1142 unchanged. Similarly, it is easy to see that (34), (34), · keeps A1142

unchanged. Note that the autotopisms generated by the two autotopisms con-

tain six diﬀerent autotopisms of which row arrangings are all the possible.

From Theorem 8.2.6 (c), ((234), (234), ·, (34), (34), ·) are coset representa-

tives of all distinct cosets. That is, G



A1142

=((234), (234), ·, (34), (34), ·)



A1142

. Therefore, the order of G



A1142

is 6 · 2.

To compute coset representatives of G



A1142

in G

A1142

,letα, β, γ∈G.

Try α = (1234). A1142 can be transformed into



⎡

⎢

⎣

11 22 33 44

23 34 24 11

34 13 41 22

42 41 12 33

⎤

⎥

⎦

by row arranging (1234) and some column arranging. Suppose that A



can be

transformed into A1142 by a renaming β and some column arranging. Since

column types of the fourth block of A



and the ﬁrst block of A1142 are the

same and diﬀerent from column types of other blocks, from Theorem 8.2.7, the

fourth block of A



is transformed into the ﬁrst block of A1142 by renaming

β and some column arranging. Thus β transforms the column 4123 into the

column 1234; that is, β = (1234). It is easy to verify that (1), (1234), · trans-

forms A



into A1142 indeed. Thus (1234), (1234), · keeps A1142 unchanged.

From Theorem 8.2.6 (d), ((1234), (1234), ·) are coset representatives of all

distinct cosets; that is, G

A1142

=((1234), (1234), ·) G



A1142

. Therefore, n

the order of G

A1142

,is4· 6 · 2.

Similarly, we can compute values of n

,...,n

The following is the computing results in the format: “x: the order of



Ax42

, the number of cosets of G



Ax42

in G



Ax42

, the number of cosets of



Ax42

in G



Ax42

, the number of cosets of G



Ax42

in G

Ax42

(the product of the

four numbers is n

); the set of coset representatives of G



Ax42

in G



Ax42

;the

set of coset representatives of G



Ax42

in G



Ax42

; the set of coset representatives

of G



Ax42

in G

Ax42

.” γ in a coset representative α, β, γ is omitted.

1: 1, 8, 2, 4; ((1), (34), (1), (1423)); ((34), (1)); ((1423), (1)).

2: 1, 4, 2, 2; ((1), (1234)); ((34), (1)); ((12), (12)(34)).

3: 1, 2, 1, 4; ((1), (13)(24)); e;((13)(24), (1), (14)(23), (12)(34)).

4: 1, 2, 2, 4; (

(1), (34)); ((24), (12)); ((4321), (1)).

8.2 Latin Arrays 303

5: 1, 1, 2, 3; e;((34), (34)); ((431), (234)).

6: 1, 4, 6, 4; ((1), (12)(34), (1), (14)(23)); ((34), (23), (234), (234));

((4321), (12)).

7: 2

, 4, 6, 4; ((1), (12)(34), (1), (13)(24)); ((234), (234), (34), (34));

((4321), (24)).

8: 2

, 2, 2, 4; ((1), (12)(34)); ((34), (34)); ((1423), (1423)).

9: 2

, 4, 2, 4; ((1), (1423)); ((34), (34)); ((1423), (1)).

10 : 2, 1, 2, 4; e;((23), (23)); ((1243), (1243)).

11 : 2, 1, 6, 4; e;((234), (234), (34), (34)); ((1234), (1234)).

Using the formulae at the beginning of the proof, we then have

U(4, 2) =



i=1

4!4!8!/n

= 4!4!8!(1/(8 · 2 · 4) + 1/(4 · 2 · 2) + 1/(2 · 4) + 1/(2 · 2 · 4) + 1/(2 · 3)

+1/(4 · 6 · 4) + 1/(2

· 4 · 6 · 4) + 1/(2

· 2 · 2 · 4)

+1/(2

· 4 · 2 · 4) + 1/(2 · 2 · 4) + 1/(2 · 6 · 4))

=3· 4!7! + 3!3!8! + 4!4!7! + 3!3!8! + 4 · 4!8! + 3!8!

+3 · 7!+2· 3!3!7! + 9 · 7!+3!3!8!+2· 3!8!

= 7!(72 + 576 + 3 + 72 + 9) + 8!(36 + 36 + 96 + 6 + 36 + 12)

= 7!732 + 8!222 = 7!2508 = 12640320,

U(4, 2, 1) =



i=1

4!4!8!/n

=3· 4!7! + 3!3!8! + 4!4!7! + 3!3!8! + 4 · 4!8! + 3!8!

= 7!(72 + 576) + 8!(36 + 36 + 96 + 6)

= 7!648 + 8!174 = 7!2040 = 10281600,

U(4, 2, 2) = 4!4!8!/n

+ 4!4!8!/n

= 4!4!8!/(2

· 4 · 6 · 4) + 4!4!8!/(2

· 4 · 2 · 4)

=3· 7!+9· 7! = 60480.

We obtain the results of the theorem. 

Corollary 8.2.2. I(4, 1) = I(4, 1, 1) = 2 , U (4, 1) = U(4, 1, 1) = (4!)

Proof. From Theorem 8.2.1, we have I(4, 1) = I(4, 1, 1) = I(4, 2, 2) = 2,

and U(4, 1, 1) = U(4, 2, 2)4!(2!)

/8!. Thus U(4, 1) = U(4, 1, 1) = 60480/105 =

576 = (4!)

. 

304 8. One Key Cryptosystems and Latin Arrays

Enumerationof(4, 3)-Latin Arrays

Let A143,...,A4643 be (4,3)-Latin arrays as follows:

⎡

⎢

⎣

111222333444

222111444333

333444111222

444333222111

⎤

⎥

⎦

A143

⎡

⎢

⎣

111222333444

222111444333

333444222111

444333111222

⎤

⎥

⎦

A243

⎡

⎢

⎣

111222333444

222111444333

333444112221

444333221112

⎤

⎥

⎦

A343

⎡

⎢

⎣

111222333444

222111444333

333444221112

444333112221

⎤

⎥

⎦

A443

⎡

⎢

⎣

111222333444

222133444113

333444112221

444311221332

⎤

⎥

⎦

A543

⎡

⎢

⎣

111222333444

222131444313

333444112221

444313221132

⎤

⎥

⎦

A643

⎡

⎢

⎣

111222333444

222434141133

333141424212

444313212321

⎤

⎥

⎦

A743

⎡

⎢

⎣

111222333444

222431144133

333144421221

444313212312

⎤

⎥

⎦

A843

⎡

⎢

⎣

111222333444

222111444333

334443112221

443334221112

⎤

⎥

⎦

A943

⎡

⎢

⎣

111222333444

222111444333

334443221112

443334112221

⎤

⎥

⎦

A1043

⎡

⎢

⎣

111222333444

222333444111

334441112322

443114221233

⎤

⎥

⎦

A1143

⎡

⎢

⎣

111222333444

222331444113

334443112221

443114221332

⎤

⎥

⎦

A1243

⎡

⎢

⎣

111222333444

222313444113

334441112232

443134221321

⎤

⎥

⎦

A1343

⎡

⎢

⎣

111222333444

222313444113

334441212231

443134121322

⎤

⎥

⎦

A1443

⎡

⎢

⎣

111222333444

222131444331

334443212112

443314121223

⎤

⎥

⎦

A1543

⎡

⎢

⎣

111222333444

222131444331

334443112212

443314221123

⎤

⎥

⎦

1643

⎡

⎢

⎣

111222333444

222113444331

334441112223

443334221112

⎤

⎥

⎦

A1743

⎡

⎢

⎣

111222333444

222443114133

334111442322

443334221211

⎤

⎥

⎦

A1843

⎡

⎢

⎣

111222333444

222314441331

334441222113

443133114222

⎤

⎥

⎦

A1943

⎡

⎢

⎣

111222333444

222134441331

334413114222

443341222113

⎤

⎥

⎦

A2043

⎡

⎢

⎣

111222333444

222341441331

334413114222

443134222113

⎤

⎥

⎦

A2143

⎡

⎢

⎣

111222333444

222334441113

334441212321

443113124232

⎤

⎥

⎦

A2243

⎡

⎢

⎣

111222333444

222334441113

334411124322

443143212231

⎤

⎥

⎦

A2343

⎡

⎢

⎣

111222333444

222334441113

334411224321

443143112232

⎤

⎥

⎦

2443

⎡

⎢

⎣

111222333444

222314441133

334431124221

443143212312

⎤

⎥

⎦

A2543

⎡

⎢

⎣

111222333444

222314441133

334431224211

443143112322

⎤

⎥

⎦

A2643

⎡

⎢

⎣

111222333444

222314441133

334443112221

443131224312

⎤

⎥

⎦

A2743

⎡

⎢

⎣

111222333444

222314441133

334443122211

443131214322

⎤

⎥

⎦

A2843