拉丁方陣及其應用 應用數學系 傅恆霖.

Presentation on theme: "拉丁方陣及其應用 應用數學系 傅恆霖."— Presentation transcript:

1 拉丁方陣及其應用 應用數學系 傅恆霖

2 A Latin square of order n is an n×n array based on an n-set S such that each element of S occurs exactly once in each row and each column. We can take A latin square of order 3

3 Array Presentations We can use L = [li,j]nxn to represent a latin square of order n. For convenience, li,j is read as the (i,j)-entry of the latin square L. Two latin squares of the same order are distinct if there is an ordered pair (i,j) such that their corresponding entries are not the same.

4 How many? Let L(n) denote the number of distinct latin squares of order n. L(1) = 1 L(2) = 2 L(3) = 12 L(4) = 576 …

5 L(5) = L(6) = L(7) = L(8) = … L(11) = What’s next?

6 Sudoku Sudoku, or Su Doku, is a Japanese word (or phrase) meaning something like Number Place. There are about 5.525x1027 latin squares of order 9 and 6.671x1021 valid Sudoku grids. Note here that a Sudoku grid is a latin square with special properties.

7 A latin square of order n defines a quasigroup on 3 elements.
<S,*> is a quasigroup if <S,*>is a groupoid and have unique solution

8 How much do you know? A quasigroup is not a group due to the “associative law”. It is not difficult to prove that an associative quasigroup is a group. Equivalently, if a quasigroup is also a semigroup, then it is in fact a group! Group?

9 36 officers (Euler 1779) Latin square Orthogonal Latin squares
14:39:15 9 9

10 Two latin squares and of order n are orthogonal if 。
Two orthogonal latin squares of order 4

11 are mutually orthogonal latin squares of order n (MOLS(n)), if for 。
Theorem Let n be a prime power and n≠2 . Then there exists n-1 latin squares (best possible!) of order n which is a collection of mutually orthogonal latin squares.

12 14:39:15 12

13 An Updated Result NEXT! 14:39:15 13 13

14 利用L⊥M我們可定義函數f，f為 的一個Permutation，或者說f為由 對映至 的1-1, onto 函數。

15 (＊) 令α為的一個排列，β也是排列， 則 ， 其中 。 　　由上述的結果，我們可以發現當L⊥M時，與L垂直的n階拉丁方陣至少有n！個。所以，要判斷key是由哪兩個方陣所形成並不容易！

16 Cryptosystem from MOLS(n)
有 個 Messages (Plaintexts)。 以n階拉丁方陣建構一個圖(OLSG)，G，則有 |E(G)| 個keys。 (最早使用k個MOLS(n)，則有 個keys.)

17 討論： 1.當n相當大時，MOLS(n)的個數也會很大。 2.如果只考慮MOLS(n)，key space較小。 3.Orthogonal mate。不容易找！(全部找出來！)

18 分散模式解 (Sharing Scheme)
　　在近代有很多重大的決定，為了確保決策過程沒有暇疵，通常會採用由多個人都同意的情況下才執行；例如開金庫，發射核彈…。所以，建立一個系統使得較小的人數無法開啟是有它的必要性。

19 A critical set C in a latin square 　　 is a set
(partial latin square) with the following two properties： 1. L is the only latin square of order n which has symbol k in (i,j)-cell for each ；and 2. no proper subset of c has property (1). A critical set

20 例 　　上面圈出的三個位置，任兩個都會形成一個臨界集(Critical Set)。少了，或多了都不是臨界；然而多了(3個)也可以繼續填成唯一的拉丁方陣。

21 Critical Set for Sudoku
If we expect the solution of a Sudoku puzzle is unique, then the partial latin square shown must have contain a “critical” set in the sense of satisfying the requirements of a Sudoku game. Sometimes, we did find more than one solution for some game.

22 Fact 1 A critical set C of a latin square L provides minimal infos from which L can be reconstructed. Fact 2 Deciding whether a partial latin square is a critical set is NP-complete. (From completion point of view.) Fact 3 Denote the minimum size of a critical set of order n by M(n) [D. Curran & G.H.J.van Rees, Cong. Numer. 1979]

23 Critical sets, n=5

24 分散模式解 1.Key → L (拉丁方陣) n public 2.選一個集合它是L中多個臨界集的聯集：S。
3.把其中 t’≦|S|。(可以容許高階者持有多一些(i,j ; k), 甚至一個Critical Set！) 4.足夠多的人即可得到“Key“。

25 A (s,t)-secret sharing scheme is a system where k pieces of information called shares or shadows of a secret key K are distributed so that each participant has a share such that: 1. the key K can be reconstructed from knowledge of any t or more shares; and 2. the key K can not be reconstructed from knowledge of fewer than t shares.

26 臨界集的選擇有很多！ ↑ 對於臨集的了解不多。 ↓ 增加破解難度

27 More Applications Coding Theory Group Testing Experimental Designs
More to be introduced!