晓查明敏发自凹非寺
量子位报道公众号QbitAI
没想到古代韩信点兵的传说后来竟然启发了计算机加密算法
相传楚汉争霸之时韩信率1500名将士与楚军交战败退退往山上这时候敌军率五百骑杀奔而来韩信便急速点兵迎敌
韩信命令士兵3人一排结果多出2名接着命令士兵5人一排结果多出3名他又命令士兵7人一排结果又多出2名
韩信马上算出军中还剩1073人而敌人不足五百而且居高临下以众击寡于是率军杀得敌方大败而逃
韩信是如何算出人数的背后的算法又是如何影响当今的计算机领域且往下看
韩信还是个数学家
当然韩信算出士兵人数只是个传说韩信本人并非数学大师这个问题最早见于一本1700年前的古籍已经是韩信死后600多年了
在 南北朝 孙子算经
原书是这样说的
有物不知其数三三数之剩二五五数之剩三七七数之剩二问物几何
意思是一個整数除以三余二除以五余三除以七余二求這個整数
它就是 中国剩余定理
在近代数学中很少有以中国数学家命名的重要定理然而这样一条数学定理名字里就有中国二字
南宋时期我国数学家秦九韶首先给出了这类问题的解法 大衍术
直到500年后著名数学家高斯才在自己的书中描述类似的结果
那么问题来了传说中的韩信到底是怎么算出来人数的呢
韩信点兵问题求解
为了更好地理解和表述韩信点兵问题我们引入一个新的数学概念同余
在数学上如果a和b除以正整数m后的余数相同 则称ab对于模m同余
X2mod3X3mod5X2mod7
为了简化问题我们先只考虑前两个同余条件满足除以3余2除以5余3的整数分别为
25811141720232638131823283338
可以看出同时符合这两个条件的第一个数是 8 23 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头条号签约
关注我们第一时间获知前沿科技动态
