凹隆寺的小查明民
量子比特報告|公衆号 QbitAI
出乎意料的是,古代南韓字母點兵的傳說,後來啟發了計算機加密算法。
據傳說,楚漢争奪霸權,漢信率1500将領和楚軍戰敗,撤退到山上,這次敵人騎着500人殺,漢信會迅速點士兵去迎接敵人。
韓信連續指令三名士兵,結果又有兩名;
韓鑫立即計算出,全軍還剩下1073人,而敵人不到500人,而且高高在上,向人群撲去,于是軍隊率領敵人打敗逃跑。
韓鑫是如何計算出人數的,它背後的算法又是如何影響當今的計算機世界的?然後往下看。
<h1類"pgc-h-right-arrow"資料軌道""9">韓鑫還是數學家?</h1>
當然,韓信計算出,兵數隻是一個傳說,韓信本人并不是數學高手。這個問題最早出現在韓信去世600多年後的一本1700年前的古書中。
在南北朝時期,《孫子兵法》記錄了這樣的問題。(注:這個孫子不是寫《孫子兵法》的孫武)
原著是這樣說的:
有些東西不知道數字,三三個數字留了二個,五個五個數字留了三個,七個七個數字留了兩個。詢問幾何形狀?
這意味着整數除以三或二,除以五或三,除以七或二,然後求全數。
這是中國的殘餘定理,也被稱為"漢信點兵"問題。
在現代數學中,很少有以中國數學家命名的重要定理,但這樣的數學定理在它的名字中帶有"中國"這個詞。
南宋時期,中國數學家秦九璇首先給出了這種問題的解決方案:衍射。
直到500年後,著名數學家高斯才在他的書中描述了類似的結果。
那麼問題來了:傳說中的"漢信"究竟是怎麼算出人數的?
<"漢信點士兵">h1級""pgc-h-right-arrow"資料跟蹤"的問題.20."</h1>
為了更好地了解和表達"韓文字母點兵"的問題,我們引入了一個新的數學概念——"相同盈餘"。
數學上,如果a和b除以正整數m的餘數,則a、b為同一模型m,用數學公式表示的漢新點士兵為(X為未知人數):
X ≡ 2 (模組 3)
X ≡ 3 (模組 5)
X ≡ 2 (模組 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-15K 并除以 7 加 2 的數字:
8、23、38、53、68、83、98、113、128......
2、9、16、23、30、37、44、51......
符合條件的第一個數字是 23,第二個數字是 128。每個後續解決方案與前一個解決方案之間的差異應為 105 個中的 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套如何來的次數,有興趣的讀者可以進一步閱讀《中國殘餘定理》的一般解釋,這裡就不重複了。
這種"南韓點兵"問題不僅不能用于點兵,甚至在天文曆法中也有重要的應用。
假設一顆彗星每四年出現一次,我們在1991年看到它,另一顆彗星每10年看到一次,我們在1997年看到它。我們下次在同一年什麼時候見到他們?
X ≡ 1991 (mod 4)
X ≡ 1997 (mod 10)
據計算,他們最後一次見面是在2007年,每20年一次,是以下一次是2027年。
如今,中國的殘餘定理已經成為許多計算機加密算法的基礎,其應用已經超出了你的想象。
<h1級"pgc-h-arrow-right-track"資料軌道""44">影響當今的計算機算法</h1>
外媒作家Quantamagazine在一篇題為《古代戰争計劃如何影響當代數學》的文章中也提到,中國的殘餘定理對現代數學、計算機算法、天文學等領域具有重要的啟迪意義。
例如,非常著名的RSA加密算法,中國殘餘定理的應用。
我們知道,在數論中,要求求解兩個大素數很簡單,但很難考慮它們的乘積。
RSA 加密算法将此産品用作自己的加密密鑰。
自1977年誕生以來,RSA加密算法已成為使用最廣泛的公鑰算法之一。
此外,中國殘差定理應用于快速傅裡葉變換(FFT),它可以大大減少計算離散傅裡葉變換所需的乘法次數。
近年來,中國剩餘的定理也被用來加密資訊。
2018年,哥倫比亞大學的學者們開發了一種加密文本資訊的方法,應用中國剩餘的定理來確定資訊恢複的準确性。
隻要手機掃過一段文字,算法就可以給出加密資訊。
這種方法稱為FontCode,是對普通字元進行小的調整,然後對調整後的字元進行重新編碼以加密資訊。
例如,以下五種不同顔色的"a",它們代表1-5個數字資訊。
如果沒有顔色區分,肉眼很難分辨出與正常字型有什麼不同。
但機器可以。
通過掃描和分析,該算法可以推斷出哪些信件經過專門處理,以及處理後的信件代表哪些資訊。
是以,在看似普通的文本中,最好隐藏這些特殊字母,進而傳遞出加密的數字字元串。
然後,通過計算這些數字,您可以獲得您真正想要傳遞的資訊。
但這種加密還不夠安全,畢竟當字元出現在螢幕或紙上時,其格式可能會略有變化。
在這一點上,需要中國剩餘的定理。
如上所述,值可以通過線性同心方程計算。
如果要求解3個未知量,則需要3個線性方程才能做到這一點。
現在,出于安全原因,科學家們增加了線性方程的數量。
例如,為了求解三個未知量,他們會設定五個線性方程,五個方程隻要知道三個,就可以解出想要的答案。
顯然,1000多年後,雖然我們不會再像韓鑫點兵那樣隐藏士兵的數量,但現代數學、計算機等領域的研究者仍然可以從中國剩餘的定理中源源不斷地獲得靈感。
相關連結:
[1]https://www.quantamagazine.org/how 古代戰争詭計是活生生的數學今天-20210914/
[2]https://www.sciencedaily.com/releases/2018/05/180510150231.htm
[3]http://www.xinhuanet.com/science/2018-08/07/c_137372635.htm
- 完成 -
量子位 QbitAI 頭條簽名
關注我們,搶先了解尖端技術