【為什麼我們要挑選這篇文章】韓信是眾所皆知的秦漢人物，然而大家不知道的是，「韓信點兵」的故事中，隱含著現代加密演算法常見的數學定理。那個定理是什麼？如何應用在演算法裡？（責任編輯：郭家宏）
本文經 AI 新媒體量子位（公眾號 ID：QbitAI）授權轉載，轉載請連繫出處
作者：量子位
沒想到，古代韓信點兵的傳說，後來竟然啟發了電腦加密演算法。
相傳，楚漢爭霸之時，韓信率 1,500 名將士與楚軍交戰敗退，退往山上，這時候敵軍率五百騎殺奔而來，韓信便急速點兵迎敵。
韓信命令士兵 3 人一排，結果多出 2 名；接著命令士兵 5 人一排，結果多出 3 名；他又命令士兵 7 人一排，結果又多出 2 名。
韓信馬上算出，軍中還剩 1,073 人，而敵人不足五百，而且居高臨下、以眾擊寡，於是率軍殺得敵方大敗而逃。
韓信是如何算出人數的，背後的演算法又是如何影響當今的電腦科學領域？且往下看。
韓信點兵，是傳說還是真實故事？
當然，韓信算出士兵人數只是個傳說，韓信本人並非數學大師。這個問題最早見於一本 1,700 年前的古籍，已經是韓信死後 600 多年了。
在南北朝時期，《孫子算經》記述了這樣一個問題。（註：這位孫子不是寫《孫子兵法》的孫武）
原書是這樣說的：
有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。問物幾何？
意思是，一個整數除以三餘二，除以五餘三，除以七於二，求這個整數。
它就是中國剩餘定理，也被叫做「韓信點兵」問題。
在近代數學中，很少有以中國數學家命名的重要定理，然而這樣一條數學定理，名字裡就有「中國」二字。
南宋時期，中國數學家秦九韶首先給出了這類問題的解法：大衍術。直到 500 年後，著名數學家高斯才在自己的書中描述類似的結果。
那麼問題來了：傳說中的「韓信」到底是怎麼算出來人數的呢？
韓信點兵問題解法：中國剩餘定理
為了更好地理解和表述韓信點兵問題，我們引入一個新的數學概念：同餘。
在數學上，如果 a 和 b 除以正整數 m 後的餘數相同，則稱 a、b對於 m 同餘，韓信點兵用數學公式來表示就是（X 是未知的人數）：
X ≡ 2 (mod 3)
X ≡ 3 (mod 5)
X ≡ 2 (mod 7)
為了簡化問題，我們先只考慮前兩個同餘條件，滿足除以 3 餘 2、除以 5 餘 3 的整數分別為：
2、5、8、11、14、17、20、23、26 ……
3、8、13、18、23、28、33、38 ……
可以看出，同時符合這兩個條件的第一個數是 8，第二個數是 23。後面的每個解與前一個之差都應該是 3 和 5 的最小公倍數 15，即：
X = 8 + 15K （K 是整數）
這樣我們就把尋找的整數解縮小了，接著再加入第三個條件，找到分別滿足 X = 8 + 15 K 和除以 7 餘 2 的數：
8、23、38、53、68、83、98、113、128 ……
2、9、16、23、30、37、44、51 ……
滿足條件的第一個數是 23，第二個數是 128。後面的每個解與前一個之差都應該是 3、5、7 的最小公倍數 105。
這樣尋找解的過程顯然太繁瑣。後來，明朝數學家程大位把求解方法編成了一首詩：
三人同行七十稀，五樹梅花廿一枝。
七子團圓正半月，除百零五便得知。
意思是：
將除以 3 得到的餘數乘以 70，將除以 5 得到的餘數乘以 21，將除以 7 得到的餘數乘以 15，全部加起來後再減去 105 或者 105 的整數倍，得到的數就是答案。
70 × 2 + 21 × 3 + 15 × 2 = 233 – 2 × 105 = 23
其他的解只能和 23 相差 105 的整數倍，韓信應該是估計出軍隊大致人數，取了 105 × 10 + 23 = 1073 這個解。
以上 70、21、15 幾組數到底是怎麼來的，有興趣的讀者可以進一步閲讀「中國剩餘定理」的通解，在此不再贅述。
這道「韓信點兵」問題不僅僅能用於點兵，甚至在天文曆法上也有重要應用。
假設有一顆彗星 4 年出現一次，我們在 1991 年看到了它、另一顆彗星 10 年看到一次，我們在 1997 年看到了它。我們下一次在同一年看到它們是什麼時候？
X ≡ 1991 (mod 4)
X ≡ 1997 (mod 10)
經過計算，它們上一次相會是在 2007 年，而且每隔 20 年重逢一次，所以下一次應該是 2027 年。
時至今日，中國剩餘定理已經成為了很多電腦加密演算法的基礎，它的應用範圍已經超乎你的想像。
中國剩餘定理的應用：RSA 加密演算法
外媒 Quantamagazine 在一篇名為《古代戰爭計策是如何影響當代數學》的文章中也提到：中國剩餘定理對現代數學、電腦演算法、天文學等領域都有很大的啟發意義。
例如非常有名的 RSA 加密演算法，就應用了中國剩餘定理。
我們知道在數論中，想要求解出兩個大質數比較簡單，但是想要對它們的乘積進行因式分解就很困難了。而 RSA 加密演算法就是把這個乘積作為了自己的加密密鑰。從 1977 年誕生以來，RSA 加密演算法已經成為了應用最廣泛的公鑰演算法之一。
此外，在快速傅立葉變換（FFT）中也應用了中國剩餘定理，它可以大大減少計算離散傅立葉變換時所需的乘法次數。
這幾年，中國剩餘定理還被用到了資訊加密上。2018 年，哥倫比亞大學的學者們發明了一種可以在文本中加密資訊的方法，其中就應用了中國剩餘定理來確保資訊復原時的準確性。
只要手機對著一段文字掃一掃，演算法就能給出加密後的資訊。
這種方法名叫 FontCode，它是對普通字元進行微小的調整，然後再對調整後的字元重新編碼資訊，從而實現對資訊的加密。
比如以下 5 種不同顏色的 a，它們分別代表了 1 到 5 的數字資訊，如果不用顏色區分，肉眼很難分辨出它們和常規字體之間有什麼不同。但是機器可以，只要透過掃瞄和分析，演算法就能推斷出哪些字母被特殊處理過，處理後的字母又表示了什麼資訊。
因此，在一段看似普通的文本中，可以很好隱藏這些特殊的字母，從而傳遞出一段加密的數字串。然後，再對這些數字進行計算，就能得出真實想要傳遞的資訊。
但是這樣的加密方式還不夠保險，畢竟字元出現在螢幕或紙面上時，它的格式都有可能發生一些細小的變化。這時就需要中國剩餘定理登場了。
在上面我們已經介紹了，透過線性同餘方程組就能計算出數值。如果想求解 3 個未知量，那麼需要 3 個線性方程才能做到。
現在為了保險起見，科學家們把線性方程的數量增加了。例如為了求解出 3 個未知量，他們會設置 5 個線性方程，5 個方程中只要知道 3 個，就能求解出想要的答案了。
顯然，1,000 多年過去了，雖然我們不會再像韓信點兵一樣隱藏士兵數量，但是現代數學、電腦等領域的研究者們，依舊能從中國剩餘定理中獲得源源不斷的啟發。
參考資料：Quantamagazine、Science Daily、新華網
（本文經 AI 新媒體量子位 授權轉載，並同意 TechOrange 編寫導讀與修訂標題，原文標題為〈韩信竟是数学大师？中国古代数学启发计算机加密算法〉。首圖來源：Shutterstock）
