Tag Archives: 有限體

梅林的魔術方塊

本文的閱讀等級:初級 梅林 (Merlin) 是美國 Parker Brothers 公司於1978年生產的一款掌上型遊戲機 (見圖),內含六種益智遊戲,魔術方塊是其中之一[1]。遊戲機面板設有九個按鍵,布置成 陣列。每一個按鍵內裝一顆LED燈泡,燈號有兩種:閃爍或熄滅。按下任一按鍵可切換燈號,同時鄰近的按鍵燈號也一併自動切換。設 表示切換按鍵, 表示鄰近按鍵, 表示非鄰近按鍵。每一切換按鍵的鄰近按鍵定義如下: 遊戲開始時,系統產生一組隨機圖案,遊戲的目的要將初始圖案變換為生產商預設的目標圖案──除中心按鍵外,所有的周邊按鍵都在閃爍狀態。梅林魔術方塊的遊戲規則存在多樣的變化,譬如,目標圖案可以任意設定。往下閱讀前,建議讀者先體會遊戲過程。請進入線上梅林魔術方塊遊戲網站 Merlin Magic Square Game,畫面左邊顯示目標圖案,先點選方框設計個人喜好的圖案 (打勾代表燈號閃爍)。按下“Enjoy new game”,畫面右邊即出現隨機圖案,點選右圖的方框切換燈號,直到產生與左圖相同的圖案即告獲勝。 Advertisements

Posted in 線性代數專欄, 應用之道 | Tagged , , | Leave a comment

希爾密碼

本文的閱讀等級:初級 希爾密碼 (Hill cipher) 由美國數學家希爾 (Lester S. Hill) 於1929年發明,它是線性代數於密碼學的一個經典應用。希爾密碼是一種替換式密碼,加密一方按照特定規律將明文取代為密文,密文接收者解密時必須使用相反規律才能取得原文本[1]。舉例來說,凱撒密碼是最廣為人知的一種簡易替換式密碼,加密方式係將明文訊息的每一個字母替換為循環移位後的對應字母,位移量即為密鑰 (key)。以英文為例,除了26個字母,還可加入標點符號和空格以方便閱讀。譬如,若移位量為3,則29個明文字母 (含句號「.」,問號「?」與空格「」) 與對應的密文字母如下所示: 明文字母表:ABCDEFGHIJKLMNOPQRSTUVWXYZ .? 密文字母表:DEFGHIJKLMNOPQRSTUVWXYZ .?ABC 為便利計算,我們將29個字母以數字 0, 1, 2,…, 28 依序編碼,即 A0,B1,C2,以此類推。簡單講,每一個字母可視為二十九進制的數字。設非零整數 表示密鑰,凱撒密碼的加密公式為 ,解密公式為 。不同於凱撒密碼的簡易加密法,希爾密碼採用表格式 (polygraphic) 加密,我們不再單獨替換個別字母,而是替換一組字母。首先將明文訊息切割為相同大小的單元,稱為組,每一組包含 () 個字母,接著使用矩陣乘法將每組明文轉換成密文,所乘矩陣即為密鑰。解密同樣使用矩陣乘法,惟所乘矩陣為密鑰的逆矩陣。希爾密碼其實是由 階密鑰矩陣表達的一線性變換, 維明文向量形成定義域, 維密文向量形成到達域,矩陣乘法實現加密與解密程序。下面我們說明希爾密碼的加密與解密過程以及破解方法,模算術是必要的預備知識 (見“利用模算術判定可逆矩陣”)。

Posted in 線性代數專欄, 應用之道 | Tagged , , , | Leave a comment

有限體與模算術

本文的閱讀等級:中級 從前,在一個遙遠的小城裡住著 個居民,他們主要的職業是組成各式各樣的俱樂部。由於某種不明的原因,不斷擴增的俱樂部開始威脅小城的生存。為了管制俱樂部總量,市議會決議通過兩條看似天真的法令: 每一個俱樂部必須有奇數個會員。 任兩個俱樂部必須有偶數個相同的會員。 小城市長宣稱:「有了這兩條法令,本城的俱樂部總數不會多於居民人口。」下面我們用線性代數方法來證明這個組合數學定理[1]。

Posted in 線性代數專欄, 向量空間 | Tagged , , , , , , , | Leave a comment