• 編按：演算法隨著網路與電腦的普及無所不在，是現代人無法忽視的思考方式。《＜演算法星球＞一書中，作者用各種簡單風趣的案例來解釋演算法是什麼？又與從電話簿裡找號碼、搜尋引擎的原理、幫孩子分蛋糕以及為想婚男女配對等挑戰有何關係？本文選自該書第 4 章「萬有引力的西邊」，世界上有各種非決定性多項式問題，例如編碼，如何套用演算法的思考來解決？

人類傳送機密訊息已長達幾千年。一開始，訊息沒有被編碼，只是隱藏而已。不管是信差郵包裡的夾層或是機密文件，隱藏訊息的過程本身也必須是隱密的。（知道如何隱藏訊息的人，也知道如何找出訊息。）機密訊息建立於訊息攔截者與溝通者的不對稱性；當我們今天為自己的資訊編碼的時候，基本上我們並沒有發現不對稱性的倒轉就在其中。（為資訊編碼並寄送出資訊的我們，一點都不了解編碼技術，犯罪者與情報單位卻通曉一切。）

機密溝通在過去是主權者的特權。1977 年，破除這種情勢的點子出現了：藉由複雜性為資訊編碼—一個今天每個人都知道的編碼技術，取代了過去那個被保護得很好的秘密保密程序；然而，每個人也還是只能為自己的個人資訊解碼。如此，每位公民都能藉由編碼保護自己的個人資訊，不被任何權威侵犯。這樣的技術既非不可知、秘密或是更昂貴的東西（我們其實可以更常使用它），問題在於有沒有編碼的意願。

藉由複雜性進行編碼的核心設計，是把資訊包裝成一個困難問題的解答，只要擁有正確的秘訣，就可以輕易破解它。非決定性多項式問題的特質完全適合這項任務，不過卻造成編碼動作執行上的另一個問題，因而產生的疑慮是：它是否又屬於非決定性多項式中最困難的問題層級呢？我們還是一個一個來看吧。

機密文件

編碼的基本任務如下：我想要告知你一件事，但不能讓別人知道。問題是，我只能透過公開管道送出我的信息，而無法對你悄悄耳語。每個人都可以閱讀這則信息，所以我們必須想出一個辦法，讓信息內容只對你產生資訊意義。於是，你需要一把能解開信息的鑰匙。如此一來，對其他人而言，這個信息只不過是一疊發出沙沙聲響的紙而已。

今天在許多狀況中我們都信任編碼，典型的例子是購買火車票。在購買的過程中，類似信用卡號碼這類敏感的資訊會在網路上傳遞，成為通訊的一部分。鐵路局透過網站賣票，要求取得你的卡片號碼。網站會讓你下載一個小程式到你的筆記型電腦上，接著要你填入個人資料至表格裡，就在那兒—你的筆記型電腦裡—這個程式為你的資料進行了編碼。

然後，程式寄送出你編碼後的資料，穿越浩瀚無垠的網際網路，去到鐵路局的伺服器那頭。（沒有編碼就把資料送上網路旅程的人，可能會馬上印出一張機票。）當訊息穿越網際網絡移動時，沒有人能解讀你的資料，但鐵路局得馬上閱讀這份資料。那麼，該怎麼做呢？

從最簡單的狀況開始思考。我們想為世界上最小的資訊編碼，因此只說「呼」或「哈」，來表示「男生」或「女生」。我們想傳送一個位元，然後不讓其他人知道答案是女生還是男生，所以我們事先約定好，答案若是男生就說「呼」，若是女生則說「哈」，或是顛倒過來，如此就可以毫無掛慮地釋出訊息，甚至加注：「以下訊息『呼』透露答案是男生或是女生。」其他人則沒辦法知道我們的答案。這個編碼非常完美，而且還很簡單。

接下來，每個訊息都可以是「呼」或「哈」，或是以廣為人知的 0 或 1 來表示。我們甚至可以使用公開熟知的標準，將 0 與 1 轉換成一段文件，並且轉換回來。唯一需要事先約定好的是，是否每個 0 就以 0 來書寫，每個 1 就以 1 表示，還是顛倒過來書寫。這和為一個位元編碼的原則完全一樣。不過，這樣卻可能無法成功編碼，因為其他人可以用兩種可能對訊息進行試驗，一次是 1 就是 1，另一次是 1 則為 0，如此多半能透過其中的一種可能，看出訊息原本的意義。如果寄出的是較長的資訊，資訊本身的結構則有可能展現出已經編碼過的文件為何，如此編碼就會被破解；相反地，一位元編碼則因為兩種可能的結果都具有意義，因而排除了舉一反三而被識破的可能。

這麼做對於稍微複雜的編碼也有效果，比如一份其每個拼字都由其他字母甚至空格來取代的機密文件。（聽起來機密度非常高。）不過，太多清楚的內文結構，例如一個字母重覆兩次時還是會被辨識出來。比如說，哪個記號最常出現，就很可能是空格；只要認出空格，就能看出非常短的字。然而非常短的字並不多。依此類推，編碼的神秘面紗很快就會被揭開。

馬塔潘角與失落的 L

一個破解機密文件的實例故事來自二次世界大戰。當時，德國納粹與同盟為其機密訊息運用了恩尼格瑪密碼機（Enigma machine）。此密碼機最高竿的秘訣，在於會更換機密訊息的每個字母；同一字母在訊息的不同處，會由不同字母來替換。在一定的時間間隔中，機密訊息第一個字的首位字母之替代字母，又會被另一個新的替換字母所取代；從那時起，恩尼格瑪密碼機便自動使用新的替換字母，取代每個新出現的字母。這讓事情變得相當棘手。

即使如此，英國布萊切利園（Bletchley Park）的解碼專家—圖靈亦是他們的成員之一，還是看出相當的規律性，從而破解了納粹訊息。當時，瑪薇絲．貝提（Mavis Batey）與圖靈一同職掌海軍訊息的解密。（貝提負責義大利海軍。人們一般認為，她所破解的敵方機密命令，讓英澳海軍在希臘瑪塔潘角的大勝，是極為關鍵性的幫助。）

貝提認為，恩尼格瑪密碼機有個弱點—其實那原是設計者相當聰明的點子：恩尼格瑪密碼機從來不使用文件真正的字母本身來編碼，因此 L 可能是所有其他字母，唯一不是的就是 L 本身。（如果一個字母用自己來編碼未免也太蠢了。）有一天，一則訊息送到貝提的辦公桌上，該訊息完全不含 L 字母，貝提開始進行一件連演算法至今都很難做到的事：她開始思考，特別對那位坐在鍵盤前發出訊息的訊息傳遞者進行思考。她認為，義大利敵友非常可能只是不斷敲著 L 鍵，寫了一封測試訊息。因為恩尼格瑪密碼機從來不用 L 為 L 編碼，顯示該訊息根本不會有字母 L。編碼過的訊息洩露內容，是因為訊息本身仍展現出夠多未經編碼的訊息結構。貝提因而找出了當天恩尼格瑪密碼機起始設定的字母。

即使是長訊息，也能像解開一位元編碼般被完美解開。只需將每個訊息寄出的 0 和 1 組合分開或隨機固定下來。是否在此處以 11 表示 00，或是相反？（這個操作方法相當完美。）誰要是擁有無盡長的每個字母之編碼單，就能輕輕鬆鬆解碼。對其他人而言，這條訊息與偶然的紙張沙沙聲則沒有任何差別。（唯一的問題是針對每張火車票、每個最後一分鐘禮物、每本在網路上被訂購的書所做的編碼單，它和人們寄出的訊息一樣長。）

• 本文出自八旗文化出版《演算法星球》
• 書名：《演算法星球》
• 出版社：八旗文化
• 作者：賽巴斯提安･史帝樂（Sebastian Stiller）