韓信點兵的故事中，隱藏著現代加密演算法的數學基礎！ - 報橘

韓信是眾所皆知的秦漢人物，然而大家不知道的是，「韓信點兵」的故事中，隱含著現代加密演算法常見的數學定理。

那個定理是什麼？如何應用在演算法裡？ Share 【為什麼我們要挑選這篇文章】韓信是眾所皆知的秦漢人物，然而大家不知道的是，「韓信點兵」的故事中，隱含著現代加密演算法常見的數學定理。

那個定理是什麼？如何應用在演算法裡？（責任編輯：郭家宏） 本文經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(mod3) X≡3(mod5) X≡2(mod7) 為了簡化問題，我們先只考慮前兩個同餘條件，滿足除以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。

後面的每個解與前一個之差都應該是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(mod4) X≡1997(mod10) 經過計算，它們上一次相會是在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、ScienceDaily、新華網 （本文經AI新媒體量子位授權轉載，並同意TechOrange編寫導讀與修訂標題，原文標題為〈韩信竟是数学大师？中国古代数学启发计算机加密算法〉。

首圖來源：Shutterstock） Share 馬上訂閱CONNECT▼ NowReading 韓信點兵的故事中，隱藏著現代加密演算法的數學基礎！ 3minread 最新文章 雲端運算人工智慧 雲端服務 數位轉型應用 資訊安全 資訊科技 未來生活電動車 智慧城市 新零售 數位金融 數位行銷 通訊科技5G/6G 太空 低軌道衛星 電信通訊 新科技 供應鏈智慧製造 半導體 能源創新 ESG IoT Web3.0元宇宙 區塊鏈 虛擬貨幣 NFT 0% ✕ Close 徵才 最新文章 雲端運算 人工智慧 雲端服務 數位轉型應用 資訊安全 資訊科技 未來生活 電動車 智慧城市 新零售 數位金融 數位行銷 通訊科技 5G/6G 太空 低軌道衛星 電信通訊 新科技 供應鏈 智慧製造 半導體 能源創新 ESG IoT Web3.0 元宇宙 區塊鏈 虛擬貨幣 NFT 投資創新 新投資 新人才 創業故事 公共服務 數位醫療 線上學習 數位政府與未來治理 網路民主與公民 品牌簡介 ABOUTUS 聯絡我們 ✕ 徵才 最新文章 雲端運算 人工智慧 雲端服務 數位轉型應用 資訊安全 資訊科技 未來生活 電動車 智慧城市 新零售 數位金融 數位行銷 通訊科技 5G/6G 太空 低軌道衛星 電信通訊 新科技 供應鏈 智慧製造 半導體 能源創新 ESG IoT Web3.0 元宇宙 區塊鏈 虛擬貨幣 NFT 投資創新 新投資 新人才 創業故事 公共服務 數位醫療 線上學習 數位政府與未來治理 網路民主與公民 品牌簡介 ABOUTUS 聯絡我們 LatestPosts 【想看中文版快+1】馬斯克等「矽谷最傳奇一代」都是Paypal出身！他們如何從一般員工，個個躍升成身價破億企業CEO？ 全球最大「碳捕捉」設備將啟用，打造它的是一家巴菲特看好的石油公司 擁有MarTech技術就能360度全方位行銷？Gartner：只有14％企業做得到 蘋果收購英國金融新創CreditKudos！歐洲「開放銀行」能推動AppleCard市場嗎？ 立陶宛開放「電子居民」，大招台灣半導體人才！ 為提供您更好的網站服務，本網站會使用Cookies及其他相關技術優化用戶體驗，繼續瀏覽本網站即表示您同意上述聲明了解隱私權政策同意並關閉視窗Manageconsent Close PrivacyOverview Thiswebsiteusescookiestoimproveyourexperiencewhileyounavigatethroughthewebsite.Outofthese,thecookiesthatarecategorizedasnecessaryarestoredonyourbrowserastheyareessentialfortheworkingofbasicfunctionalitiesofthewebsite.Wealsousethird-partycookiesthathelpusanalyzeandunderstandhowyouusethiswebsite.Thesecookieswillbestoredinyourbrowseronlywithyourconsent.Youalsohavetheoptiontoopt-outofthesecookies.Butoptingoutofsomeofthesecookiesmayaffectyourbrowsingexperience. Necessary Necessary AlwaysEnabled Necessarycookiesareabsolutelyessentialforthewebsitetofunctionproperly.Thesecookiesensurebasicfunctionalitiesandsecurityfeaturesofthewebsite,anonymously. CookieDurationDescriptioncookielawinfo-checkbox-analytics11monthsThiscookieissetbyGDPRCookieConsentplugin.Thecookieisusedtostoretheuserconsentforthecookiesinthecategory"Analytics".cookielawinfo-checkbox-functional11monthsThecookieissetbyGDPRcookieconsenttorecordtheuserconsentforthecookiesinthecategory"Functional".cookielawinfo-checkbox-necessary11monthsThiscookieissetbyGDPRCookieConsentplugin.Thecookiesisusedtostoretheuserconsentforthecookiesinthecategory"Necessary".cookielawinfo-checkbox-others11monthsThiscookieissetbyGDPRCookieConsentplugin.Thecookieisusedtostoretheuserconsentforthecookiesinthecategory"Other.cookielawinfo-checkbox-performance11monthsThiscookieissetbyGDPRCookieConsentplugin.Thecookieisusedtostoretheuserconsentforthecookiesinthecategory"Performance".viewed_cookie_policy11monthsThecookieissetbytheGDPRCookieConsentpluginandisusedtostorewhetherornotuserhasconsentedtotheuseofcookies.Itdoesnotstoreanypersonaldata. Functional Functional Functionalcookieshelptoperformcertainfunctionalitieslikesharingthecontentofthewebsiteonsocialmediaplatforms,collectfeedbacks,andotherthird-partyfeatures. Performance Performance Performancecookiesareusedtounderstandandanalyzethekeyperformanceindexesofthewebsitewhichhelpsindeliveringabetteruserexperienceforthevisitors. Analytics Analytics Analyticalcookiesareusedtounderstandhowvisitorsinteractwiththewebsite.Thesecookieshelpprovideinformationonmetricsthenumberofvisitors,bouncerate,trafficsource,etc. Advertisement Advertisement Advertisementcookiesareusedtoprovidevisitorswithrelevantadsandmarketingcampaigns.Thesecookiestrackvisitorsacrosswebsitesandcollectinformationtoprovidecustomizedads. Others Others Otheruncategorizedcookiesarethosethatarebeinganalyzedandhavenotbeenclassifiedintoacategoryasyet. SAVE&ACCEPT