一個簡單的幾何問題如何推動了資訊理論、密碼學、區塊鏈等科技

給出空間中的一組點，你能找到某種型別的曲線穿過所有的點嗎？這個問題，體現的是一個

“插值問題”

，自古以來就引起了數學家的興趣。

今年早些時候，布朗大學的兩位年輕數學家，埃裡克·拉爾森（Eric Larson）和伊莎貝爾·沃格特（Isabel Vogt）在一篇長達70多頁的論文中，對這個問題進行了證明，完全系統地解決了這個問題。小編在《

一對年輕的數學家夫婦解決了一個幾何學中最基本物件的古老問題

》一文中作了介紹。

這裡小編要介紹的是，這種數學曲線的

“插值問題”，

一個看起來簡單的幾何學思想，如何被用來推動了當代資訊理論、密碼學、區塊鏈等科學技術的發展。

雖然

埃裡克·拉爾森和伊莎貝爾·沃格特

的

這項工作在純數學界引起了很大的興趣，但這一插值研究的實際應用後果遠遠超出了幾何學的範疇。

“插值”

是儲存和通訊電子資料、構建加密方案等的核心。這就是為什麼你可以刮傷CD盤而仍然可以聽到清晰的音樂，或者把二維碼弄髒而仍然有效的掃描它；這也是為什麼航天飛行器可以將清晰的數字影象傳回地球；這也是為什麼一個計算機叢集可以進行復雜的計算，即使其中一臺計算機出現故障。

這些應用都依賴於“插值”概念的一個驚人的、美妙的直接應用

：所謂的

裡德-所羅門碼

（又稱裡所碼，Reed-solomon codes，簡稱RS codes）

，以及在此基礎上所建立起來的編碼。

點對點

假設你想傳送一個由兩個數字組成的資訊，譬如2和7。你傳輸的一些資料可能會丟失或被破壞，例如，2可能會翻轉為-2。因此，與其簡單地傳送資料，你可以新增額外的資訊來幫助收件人識別和修復可能出現的錯誤。這就是

所謂的“

糾錯碼

”。

這樣一種程式碼的最簡單的例子是多次傳輸同一資訊。為了讓收件人識別是否發生了錯誤，傳送兩次相同的資訊：2、7、2、7。如果對應位置的數字不匹配（比如說，如果傳輸的數字是2，7，-2，7），收件人就會知道其中一個是錯的，但不知道是哪個。為了讓他們弄清楚並糾正錯誤，可以傳送三次相同的資訊：2、7、2、7、2、7。收件人只需採取“多數投票”的方式，就能弄清楚你的意圖資訊。

但這種糾正錯誤的手段是非常低效的。有一個聰明一點的方法就是，將資訊編碼為一條曲線，併發送足夠的資訊讓收件人重建該曲線。

比如在傳送2和7的簡單例子中，曲線是直線 y = 2x + 7。在兩個預先確定的x值上評估這條曲線，併發送所得到的y值。接收者現在有兩個點，因為插值問題告訴我們，兩個點決定了一條唯一的直線，接收者只需要找到透過他們收到的點的直線。這條線的係數揭示了所要傳達的資訊。

為了避免錯誤，你再次新增額外的資訊。在這裡，你傳送與另一個預先確定的X座標相對應的Y值。如果這三個點沒有落在同一條線上，就會出現錯誤。為了找出錯誤所在，你只需再發送一個值，這意味著你總共傳送了四個數字，而不是之前的方法所要求的六個。

這種優勢隨著資訊的大小而增加。比方說，你想傳送一個較長的資訊，有1000個數字。效率較低的程式碼需要傳送2000個數字來識別錯誤，再發送3000個數字來糾正錯誤。但是如果你使用涉及透過給定的點進行多項式內插的程式碼，你只需要1，001個數字來發現錯誤，1，002個數字來糾正它。你可以增加更多的點來識別和糾正更多的潛在錯誤。隨著你的資訊長度的增加，兩種程式碼之間的效率差異也越來越明顯。

更有效的程式碼就是裡德-所羅門程式碼。自1960年推出以來，數學家們取得了進一步的突破，開發了能夠以更高的效率糾正更多錯誤的演算法。“它非常優雅、乾淨、具體，”多倫多大學的數學家和計算機科學家Swastik Kopparty說。“它可以在半小時內教會一個二年級的本科生。”

裡德-所羅門碼在電子儲存和傳輸資訊方面一直特別有用。但同樣的概念在密碼學和分散式計算中也是至關重要的。

以

金鑰共享

為例。假設你想在幾方之間分配一個

秘密

，這樣就沒有一個人可以獲得整個秘密，但他們一起可以。比如說一個加密金鑰，或者一個導彈發射程式碼。你將數字編碼為多項式，在一組預先確定的點上評估該多項式，並將每個結果分配給不同的人。

最近，裡德-所羅門碼被應用於雲計算和區塊鏈技術等領域。假設你需要執行一個對你的膝上型電腦來說太複雜的計算，你讓一個大型計算叢集來執行它，但現在你需要驗證你得到的計算結果是否正確。裡德-所羅門編碼讓你要求提供額外的資訊，如果叢集沒有正確地完成計算，它很可能無法產生這些資訊。法國雷恩數學研究所研究員Jade Nardi說：“這個工作很神奇，”。“這個過程真的很奇妙，它依靠這些程式碼的方式讓我震驚。”

在一次概念驗證測試中，美國宇航局的科學家將蒙娜麗莎編碼到鐳射束上，並將其從地球表面傳送到月球航天器上。裡德-所羅門編碼被用來糾正由地球大氣層引入的傳輸錯誤。（圖片由美國航天局戈達德分局孫曉莉提供）

但裡德-所羅門碼也有一個重要的限制。它們的構造是這樣的：你只能在一組固定的，通常是相對較小的，數值上評估你的多項式。也就是說，你只能用一組特定的數字來編碼你的資訊。這組數字或字母表的大小反過來又限制了你可以傳送的資訊的長度，你試圖使你的字母表越大，你就越需要計算能力來解碼這些資訊。

因此，數學家們尋求一種更加理想的程式碼。

未來的程式碼

一個更為普遍、更為強大的程式碼將允許儲存或傳送更長的資訊，而不需要增加字母表的大小。為了做到這一點，數學家們設計了涉及插值函式的程式碼，它在一個與更復雜的曲線相關的特殊空間中，透過該曲線上的給定點。這些所謂的代數幾何程式碼 “不知從何而來，它們比我們知道的任何其他具有較小字母表的程式碼都要好”，Kopparty說。“這打敗了一切。這是一個真正的震驚。”

還有一個問題。在實踐中，實現裡德-所羅門碼比實現代數幾何碼要容易，而且要容易多得多。“密碼學家西蒙-阿貝拉爾說：”這是最先進的，但它仍在研究中，以真正變成實用的東西。“它涉及相當抽象的數學，而且很難在計算機上處理這些程式碼。”

就目前而言，這並不令人擔憂。在現實世界的應用中，裡德-所羅門碼和相關形式的糾錯已經足夠了。但情況可能並不總是如此。例如，如果強大的量子計算機在未來可用，它們將能夠打破今天的密碼學協議。因此，研究人員一直在尋找能夠抵禦量子攻擊的方案。這種方案的一個主要競爭者將需要比裡德-所羅門碼更強的東西。某些版本的代數幾何碼可能就能發揮作用。其他研究人員對代數幾何碼在雲計算中可能發揮的作用抱有很大希望。

但即使沒有這樣的潛在用途，今後有沒有用？誰也不敢、也不能打包票。在數學史上，有時所發現的新東西在當時看起來確實沒有多大用途，但是50年後、100年後，會出乎意料地發現，它對一些看起來毫不相關的事情有用，就像這個古老的插值問題。