韓信竟是數(shù)學(xué)大師？中國(guó)古代數(shù)學(xué)啟發(fā)計(jì)算機(jī)加密算法

白交 2021-09-20 13:32:39 來(lái)源：量子位

曉查 明敏 發(fā)自 凹非寺

量子位 報(bào)道 | 公眾號(hào) QbitAI

沒(méi)想到，古代韓信點(diǎn)兵的傳說(shuō)，后來(lái)竟然啟發(fā)了計(jì)算機(jī)加密算法。

相傳，楚漢爭(zhēng)霸之時(shí)，韓信率1500名將士與楚軍交戰(zhàn)敗退，退往山上，這時(shí)候敵軍率五百騎殺奔而來(lái)，韓信便急速點(diǎn)兵迎敵。

韓信命令士兵3人一排，結(jié)果多出2名；接著命令士兵5人一排，結(jié)果多出3名；他又命令士兵7人一排，結(jié)果又多出2名。

韓信馬上算出，軍中還剩1073人，而敵人不足五百，而且居高臨下、以眾擊寡，于是率軍殺得敵方大敗而逃。

韓信是如何算出人數(shù)的，背后的算法又是如何影響當(dāng)今的計(jì)算機(jī)領(lǐng)域？且往下看。

韓信還是個(gè)數(shù)學(xué)家？

當(dāng)然，韓信算出士兵人數(shù)只是個(gè)傳說(shuō)，韓信本人并非數(shù)學(xué)大師。這個(gè)問(wèn)題最早見于一本1700年前的古籍，已經(jīng)是韓信死后600多年了。

在南北朝時(shí)期，《孫子算經(jīng)》記述了這樣一個(gè)問(wèn)題。（注：這位孫子不是寫《孫子兵法》的孫武）

原書是這樣說(shuō)的：

有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二。問(wèn)物幾何？

意思是，一個(gè)整數(shù)除以三余二，除以五余三，除以七余二，求這個(gè)整數(shù)。

它就是中國(guó)剩余定理，也被叫做“韓信點(diǎn)兵”問(wèn)題。

在近代數(shù)學(xué)中，很少有以中國(guó)數(shù)學(xué)家命名的重要定理，然而這樣一條數(shù)學(xué)定理，名字里就有“中國(guó)”二字。

南宋時(shí)期，我國(guó)數(shù)學(xué)家秦九韶首先給出了這類問(wèn)題的解法：大衍術(shù)。

直到500年后，著名數(shù)學(xué)家高斯才在自己的書中描述類似的結(jié)果。

那么問(wèn)題來(lái)了：傳說(shuō)中的“韓信”到底是怎么算出來(lái)人數(shù)的呢？

“韓信點(diǎn)兵”問(wèn)題求解

為了更好地理解和表述“韓信點(diǎn)兵”問(wèn)題，我們引入一個(gè)新的數(shù)學(xué)概念——“同余”。

在數(shù)學(xué)上，如果a和b除以正整數(shù)m后的余數(shù)相同，則稱a、b對(duì)于模m同余，韓信點(diǎn)兵用數(shù)學(xué)公式來(lái)表示就是（X是未知的人數(shù)）：

X ≡ 2 (mod 3)
X ≡ 3 (mod 5)
X ≡ 2 (mod 7)

為了簡(jiǎn)化問(wèn)題，我們先只考慮前兩個(gè)同余條件，滿足除以3余2、除以5余3的整數(shù)分別為：

2、5、8、11、14、17、20、23、26……
3、8、13、18、23、28、33、38……

可以看出，同時(shí)符合這兩個(gè)條件的第一個(gè)數(shù)是8，第二個(gè)數(shù)是23。后面的每個(gè)解與前一個(gè)之差都應(yīng)該是3和5的最小公倍數(shù)15，即：

X = 8 + 15K （K是整數(shù)）

這樣我們就把尋找的整數(shù)解縮小了，接著再加入第三個(gè)條件，找到分別滿足X=8+15K和除以7余2的數(shù)：

8、23、38、53、68、83、98、113、128……
2、9、16、23、30、37、44、51……

滿足條件的第一個(gè)數(shù)是23，第二個(gè)數(shù)是128。后面的每個(gè)解與前一個(gè)之差都應(yīng)該是3、5、7的最小公倍數(shù)105。

這樣尋找解的過(guò)程顯然太繁瑣。后來(lái)，明朝數(shù)學(xué)家程大位把求解方法編成了一首詩(shī)：

三人同行七十稀，五樹梅花廿一枝。

七子團(tuán)圓正半月，除百零五便得知。

意思是：

將除以3得到的余數(shù)乘以70，將除以5得到的余數(shù)乘以21，將除以7得到的余數(shù)乘以15，全部加起來(lái)后再減去105或者105的整數(shù)倍，得到的數(shù)就是答案。

70 × 2 + 21 × 3 + 15 × 2 = 233 – 2 × 105 = 23

其他的解只能和23相差105的整數(shù)倍，韓信應(yīng)該是估計(jì)出軍隊(duì)大致人數(shù)，取了105×10+23=1073這個(gè)解。

以上70、21、15幾組數(shù)到底是怎么來(lái)的，有興趣的讀者可以進(jìn)一步閱讀“中國(guó)剩余定理”的通解，在此不再贅述。

這道“韓信點(diǎn)兵”問(wèn)題不僅僅能用于點(diǎn)兵，甚至在天文歷法上也有重要應(yīng)用。

假設(shè)有一顆彗星4年出現(xiàn)一次，我們?cè)?991年看到了它、另一顆彗星10年看到一次，我們?cè)?997年看到了它。我們下一次在同一年看到它們是什么時(shí)候？

X ≡ 1991 (mod 4)
X ≡ 1997 (mod 10)

經(jīng)過(guò)計(jì)算，它們上一次相會(huì)是在2007年，而且每隔20年重逢一次，所以下一次應(yīng)該是2027年。

時(shí)至今日，中國(guó)剩余定理已經(jīng)成為了很多計(jì)算機(jī)加密算法的基礎(chǔ)，它的應(yīng)用范圍已經(jīng)超乎你的想象。

影響當(dāng)今計(jì)算機(jī)算法

外媒Quantamagazine在一篇名為《古代戰(zhàn)爭(zhēng)計(jì)策是如何影響當(dāng)代數(shù)學(xué)》的文章中也提到：中國(guó)剩余定理對(duì)現(xiàn)代數(shù)學(xué)、計(jì)算機(jī)算法、天文學(xué)等領(lǐng)域都有很大的啟發(fā)意義。

比如非常有名的RSA加密算法，就應(yīng)用了中國(guó)剩余定理。

我們知道在數(shù)論中，想要求解出兩個(gè)大素?cái)?shù)比較簡(jiǎn)單，但是想要對(duì)它們的乘積進(jìn)行因式分解就很困難了。

而RSA加密算法就是把這個(gè)乘積作為了自己的加密密鑰。

從1977年誕生以來(lái)，RSA加密算法已經(jīng)成為了應(yīng)用最廣泛的公鑰算法之一。

此外，在快速傅里葉變換（FFT）中也應(yīng)用了中國(guó)剩余定理，它可以大大減少計(jì)算離散傅里葉變換時(shí)所需的乘法次數(shù)。

這幾年，中國(guó)剩余定理還被用到了信息加密上。

2018年，哥倫比亞大學(xué)的學(xué)者們發(fā)明了一種可以在文本中加密信息的方法，其中就應(yīng)用了中國(guó)剩余定理來(lái)確保信息復(fù)原時(shí)的準(zhǔn)確性。

只要手機(jī)對(duì)著一段文字掃一掃，算法就能給出加密后的信息。

這種方法名叫FontCode，它是對(duì)普通字符進(jìn)行微小的調(diào)整，然后再對(duì)調(diào)整后的字符重新編碼信息，從而實(shí)現(xiàn)對(duì)信息的加密。

比如以下5種不同顏色的“a”，它們分別代表了1-5的數(shù)字信息。

如果不用顏色區(qū)分，肉眼很難分辨出它們和常規(guī)字體之間有什么不同。

但是機(jī)器可以。

只要通過(guò)掃描和分析，算法就能推斷出哪些字母被特殊處理過(guò)，處理后的字母又表示了什么信息。

因此，在一段看似普通的文本中，可以很好隱藏這些特殊的字母，從而傳遞出一段加密的數(shù)字串。

然后，再對(duì)這些數(shù)字進(jìn)行計(jì)算，就能得出真實(shí)想要傳遞的信息。

但是這樣的加密方式還不夠保險(xiǎn)，畢竟字符出現(xiàn)在屏幕或紙面上時(shí)，它的格式都有可能發(fā)生一些細(xì)小的變化。

這時(shí)就需要中國(guó)剩余定理登場(chǎng)了。

在上面我們已經(jīng)介紹了，通過(guò)線性同余方程組就能計(jì)算出數(shù)值。

如果想求解3個(gè)未知量，那么需要3個(gè)線性方程才能做到。

現(xiàn)在為了保險(xiǎn)起見，科學(xué)家們把線性方程的數(shù)量增加了。

比如為了求解出3個(gè)未知量，他們會(huì)設(shè)置5個(gè)線性方程，5個(gè)方程中只要知道3個(gè)，就能求解出想要的答案了。

顯然，1000多年過(guò)去了，雖然我們不會(huì)再像韓信點(diǎn)兵一樣隱藏士兵數(shù)量，但是現(xiàn)代數(shù)學(xué)、計(jì)算機(jī)等領(lǐng)域的研究者們依舊能從中國(guó)剩余定理中獲得源源不斷的啟發(fā)。

參考鏈接：
[1]https://www.quantamagazine.org/how-ancient-war-trickery-is-alive-in-math-today-20210914/
[2]https://www.sciencedaily.com/releases/2018/05/180510150231.htm
[3]http://www.xinhuanet.com/science/2018-08/07/c_137372635.htm