韩信数学达人?中国古代数学启发计算机密码算法-量子比特,
没想到古代韩信点兵的传说,后来启发了计算机密码算法。
楚汉争霸时,率领韩信1500名官兵与楚军交战败退,退山。此时,敌军率领500骑杀赶来,韩信迅速点兵向敌人进发。
韩信命令3名士兵排成一列,结果多了2人,接着命令5名士兵排成一列,结果增加了3人。他又命令七名士兵排成一列,结果又增加了两名。
韩信马上算出来,军中还剩1073人,但敌人不到500,而且居高临下,众打寡妇,所以率军将敌人大败而逃。
韩信如何计算人数,背后的算法如何影响当前的计算机领域。然后往下看。
韩信还是数学家?当然,算出韩信士兵的数量只是传说,韩信本人不是数学大师。这个问题最早见于1700年前的古书中,已经在韩信死后600多年了。
南北朝时期,《孙子算经》记述了这样的问题。(注:这孙子不是写《孙子兵法》的孙武)
原书如是说:
它是中国的剩余定理,也被称为“韩信点兵”问题。
在近代数学中,很少有以中国数学家命名的重要定理,在这样的数学定理中,名字里有“中国”这个字。
南宋时期,我国数学家秦九韶首先提供了这类问题的解法:大衍术。
直到500年后,著名数学家高斯才在自己的书中描述了类似的结果。
那么问题来了:传说中的“韩信”到底是如何计算人数的呢?
为了更好地理解和表达“韩信点兵”问题的解法韩信点兵“问题,我们引入了新的数学概念‘同余'。
在数学上,如果a和b除以正整数m后的余数相同,则a、b为模型m的余数,韩信点兵用数学式表示(X为未知人数):
X ≡ 2 (mod 3、X ≡ 3 (mod 5、X ≡ 2 (mod 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。后面的各解和前面的解的差必须是3、5、7的最小公倍数105。
含义:
70 × 2 + 21 × 3 + 15 × 2 = 233 #8211; 2 × 105 = 23
其他的解只差23和105的整数倍,韩信估计军队的大致人数应该是105×10+23=1073的解。
以上70、21、15几个组的数量到底是怎么来的,感兴趣的读者还可以进一步阅读《中国剩余定理》的理解,这里不作详述。
假设一颗彗星每四年出现一次,我们在1991年看到它,另一颗彗星每十年看到一次,我们在1997年看到它。我们下一次在同一年看到它们是什么时候。
X ≡ 1991 (mod 4、X ≡ 1997 (mod 10)
算起来,他们最后一次见面是在2007年,而且每隔20年再会,接下来应该是2027年。
时至今日,中国剩余定理已成为众多计算机密码算法的基础,其应用范围已超出你的想象。
影响当前计算机算法的外媒Quantamagazine在《古代战争计划如何影响现代数学》一文中也提到,中国剩余定理对现代数学、计算机算法、天文学等领域具有很大的启发意义。
例如,非常著名的RSA密码算法应用了中国剩余定理。
在数论中,我们知道,想要求解两个大素数是很容易的,但是要把它们的积进行因数分解是很难的。
RSA密码算法将该积作为自己的密码密钥。
自1977年诞生以来,RSA密码算法已成为应用最广泛的公钥算法之一。
另外,高速傅立叶变换(FFT)也适用中国的剩余定理,可以大幅减少计算离散傅立叶变换时所需的乘法次数。
近几年,中国剩余的定理也被用于信息加密。
2018年,哥伦比亚大学的学者们发明了一种可以在文本中加密信息的方法。其中,为了确保信息恢复时的准确性,应用了中国剩余定理。
如果手机扫描成一段文字,算法就可以给出加密的信息。
这种方法被称为FontCode,它对普通字符进行微调,然后对调整后的字符重新编码信息,实现信息加密。
例如,以下5种不同颜色的“a”分别表示15个数字信息。
如果不分色,肉眼很难分辨出与普通字体的区别。
但是机器没问题。
只要扫描和分析,算法就能推断出哪些字母是特别处理的,处理后的字母代表哪些信息。
因此,在看似正常的文本中,可以隐藏这些特殊字符,并传递加密的数字串。
然后,通过计算这些数字,你会得到你真正想传达的信息。
但这种加密方式仍然不安全。当文字出现在屏幕或纸面上时,格式可能会逐渐改变。
此时中国剩余的定理必须出台。
如上所述,可以通过线性同余方程组计算数值。
求解三个未知量需要三个线性方程。
现在为了保险,科学家们增加了线性方程的数量。
例如为了解3个未知量,设定5个线性方程,只要知道5个方程中的3个,就可以求出想要的答案。
显然,1000多年过去了,我们不能像韩信点兵那样隐藏士兵的数量,但是现代数学、计算机等领域的研究者们仍然可以从中国剩余的定理中不断得到启发。
参考链接:[1]https://www.quantamagazine.org/how-ancient-war-trickery-is-alive-in-math-today-20210914/[2]https://www.sciencedaily.com/releases/2018/05/180510150231.htm[3]http://www.xinhuanet.com/science/2018-08/07/c_137372635.htm