晓查明敏发自凹非寺量子位报道公众号QbitAI没想到古代韩信点兵的传说后来竟然启发了计算机加密算法
相传楚汉争霸之时韩信率1500名将士与楚军交战败退退往山上这时候敌军率五百骑杀奔而来韩信便急速点兵迎敌
韩信命令士兵3人一排结果多出2名接着命令士兵5人一排结果多出3名他又命令士兵7人一排结果又多出2名
韩信马上算出军中还剩1073人而敌人不足五百而且居高临下以众击寡于是率军杀得敌方大败而逃
韩信是如何算出人数的背后的算法又是如何影响当今的计算机领域且往下看
韩信还是个数学家
当然韩信算出士兵人数只是个传说韩信本人并非数学大师这个问题最早见于一本1700年前的古籍已经是韩信死后600多年了
在南北朝时期孙子算经记述了这样一个问题注这位孙子不是写孙子兵法的孙武原书是这样说的有物不知其数三三数之剩二五五数之剩三七七数之剩二问物几何
意思是一個整数除以三余二除以五余三除以七余二求這個整数
它就是中国剩余定理也被叫做韩信点兵问题
在近代数学中很少有以中国数学家命名的重要定理然而这样一条数学定理名字里就有中国二字
南宋时期我国数学家秦九韶首先给出了这类问题的解法大衍术
直到500年后著名数学家高斯才在自己的书中描述类似的结果
那么问题来了传说中的韩信到底是怎么算出来人数的呢
韩信点兵问题求解为了更好地理解和表述韩信点兵问题我们引入一个新的数学概念同余
在数学上如果a和b除以正整数m后的余数相同则称ab对于模m同余韩信点兵用数学公式来表示就是X是未知的人数X2mod3X3mod5X2mod7为了简化问题我们先只考虑前两个同余条件满足除以3余2除以5余3的整数分别为25811141720232638131823283338可以看出同时符合这两个条件的第一个数是8第二个数是23后面的每个解与前一个之差都应该是3和5的最小公倍数15即X815KK是整数这样我们就把寻找的整数解缩小了接着再加入第三个条件找到分别满足X815K和除以7余2的数823385368839811312829162330374451满足条件的第一个数是23第二个数是128后面的每个解与前一个之差都应该是357的最小公倍数105
这样寻找解的过程显然太繁琐后来明朝数学家程大位把求解方法编成了一首诗三人同行七十稀五树梅花廿一枝
七子团圆正半月除百零五便得知
意思是将除以3得到的余数乘以70将除以5得到的余数乘以21将除以7得到的余数乘以15全部加起来后再减去105或者105的整数倍得到的数就是答案
702213152233210523其他的解只能和23相差105的整数倍韩信应该是估计出军队大致人数取了10510231073这个解
以上702115几组数到底是怎么来的有兴趣的读者可以进一步阅读中国剩余定理的通解在此不再赘述
这道韩信点兵问题不仅仅能用于点兵甚至在天文历法上也有重要应用
假设有一颗彗星4年出现一次我们在1991年看到了它另一颗彗星10年看到一次我们在1997年看到了它我们下一次在同一年看到它们是什么时候
X1991mod4X1997mod10经过计算它们上一次相会是在2007年而且每隔20年重逢一次所以下一次应该是2027年
时至今日中国剩余定理已经成为了很多计算机加密算法的基础它的应用范围已经超乎你的想象
影响当今计算机算法外媒Quantamagazine在一篇名为古代战争计策是如何影响当代数学的文章中也提到中国剩余定理对现代数学计算机算法天文学等领域都有很大的启发意义
比如非常有名的RSA加密算法就应用了中国剩余定理
我们知道在数论中想要求解出两个大素数比较简单但是想要对它们的乘积进行因式分解就很困难了
而RSA加密算法就是把这个乘积作为了自己的加密密钥
从1977年诞生以来RSA加密算法已经成为了应用最广泛的公钥算法之一
此外在快速傅里叶变换FFT中也应用了中国剩余定理它可以大大减少计算离散傅里叶变换时所需的乘法次数
这几年中国剩余定理还被用到了信息加密上
2018年哥伦比亚大学的学者们发明了一种可以在文本中加密信息的方法其中就应用了中国剩余定理来确保信息复原时的准确性
只要手机对着一段文字扫一扫算法就能给出加密后的信息
这种方法名叫FontCode它是对普通字符进行微小的调整然后再对调整后的字符重新编码信息从而实现对信息的加密
比如以下5种不同颜色的a它们分别代表了15的数字信息
如果不用颜色区分肉眼很难分辨出它们和常规字体之间有什么不同
但是机器可以
只要通过扫描和分析算法就能推断出哪些字母被特殊处理过处理后的字母又表示了什么信息
因此在一段看似普通的文本中可以很好隐藏这些特殊的字母从而传递出一段加密的数字串
然后再对这些数字进行计算就能得出真实想要传递的信息
但是这样的加密方式还不够保险毕竟字符出现在屏幕或纸面上时它的格式都有可能发生一些细小的变化
这时就需要中国剩余定理登场了
在上面我们已经介绍了通过线性同余方程组就能计算出数值
如果想求解3个未知量那么需要3个线性方程才能做到
现在为了保险起见科学家们把线性方程的数量增加了
比如为了求解出3个未知量他们会设置5个线性方程5个方程中只要知道3个就能求解出想要的答案了
显然1000多年过去了虽然我们不会再像韩信点兵一样隐藏士兵数量但是现代数学计算机等领域的研究者们依旧能从中国剩余定理中获得源源不断的启发
参考链接1完量子位QbitAI头条号签约关注我们第一时间获知前沿科技动态
