形容寒冷的冬天的优美句子，冬天温暖人心的唯美段落句子26句形容寒冷的冬天的短句

晓查明敏发自凹非寺

量子位报道公众号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头条号签约

关注我们第一时间获知前沿科技动态