古代韩信点兵的传说居然启发了计算机加密算法

没想到，古代韩信点兵的传说居然启发了计算机加密算法。

姓

相传，楚汉争霸时，韩信率领1500名士兵与楚军交战，退守深山这时，敌军以500骑的速度杀来，韩信迅速派了一些士兵去迎敌

韩信一连点了三个兵，结果多了两个，然后士兵们被命令五人一排，结果多了三个，他一连命令七个士兵，结果又多了两个。

韩信当即计算，军中还剩1073人，但敌人不到500人，且居高临下，寡不敌众，遂引军大败而逃。

韩信是如何计算人数的，其背后的算法又是如何影响今天的计算机领域的往下看

韩信也是数学家。

当然，韩信对士兵数量的计算只是一个传说，韩信本人也不是数学大师这个问题最早见于1700年前的一本古书，距离韩信去世已有600多年

在南北朝时期，《孙子算经》描述了这样一个问题。

原著是这么说的，

我不知道事情的数量三三个数还剩两个，五五个数还剩三个，七七个数还剩两个问几何

意思是，一个整数除以三大于二，除以五大于三，除以七大于二，求这个整数。

它是中国的剩余定理，也叫韩信点兵问题。

在现代数学中，很少有以中国数学家命名的重要定理可是，这样一个数学定理的名字里却有中国二字

南宋时，我国数学家秦九照首次给出了解决这类问题的方法。

直到500年后，著名数学家高斯才在书中描述了类似的结果。

那么问题来了，传说中的:的韩信是怎么算出来人数的呢。

韩信点兵问题的解决

为了更好地理解和表达韩信调兵问题，我们引入了一个新的数学概念——同余。

数学上，如果A和B除以正整数M后的余数相同，那么A和B就说是以M为模全等，韩信的兵用数学公式表示为:

X 2

X 3

X 2

为了简化问题，我们先只考虑前两个同余条件，满足除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

这样，我们把要找的整数解缩小，再加上第三个条件，就可以找到满足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的最小公倍数

这个寻找解决方案的过程显然太麻烦了。后来，明朝数学家程大伟把这个解编成了一首诗:

三个人一起走在七十稀里，五棵树二十一朵梅花。

七个孩子团聚是半个月，除了105。

意思是:

将3除得到的余数乘以70，5除得到的余数乘以21，7除得到的余数乘以15，全部相加再减去105或105的整数倍，得到的数就是答案。

70 2 21 3 15 2=233 — 2 105=23

其他解决方案只能与23相差105的整数倍韩信应该估计了大概的兵力，取了10510 23=1073的解

以上70，21，15这几组是怎么来的感兴趣的读者可以进一步阅读中国剩余定理的通解，这里不再赘述

韩信点兵这个问题不仅可以用来点兵，在天文历法中也有重要的应用。

假设一颗彗星每四年出现一次，我们在1991年看到它，另一颗彗星每十年出现一次，我们在1997年看到它同年我们下次什么时候能见到他们

X 1991

X 1997

计算后

到目前为止，中国剩余定理已经成为许多计算机加密算法的基础，其应用范围已经超出了你的想象。

影响了今天的计算机算法。

外媒Quantamagazine在一篇名为《古代战争计策是如何影响当代数学》的文章中也提到，中国剩余定理对现代数学，计算机算法，天文学等领域都有很大的启发意义。

例如，众所周知的RSA加密算法应用了中国剩余定理。

我们知道，在数论中，求解两个大素数相对简单，但要分解它们的乘积却非常困难。

RSA加密算法将该产品作为自己的加密密钥。

自1977年诞生以来，RSA加密算法已经成为应用最广泛的公钥算法之一。

此外，中国剩余定理还应用于快速傅里叶变换，可以大大减少计算离散傅里叶变换所需的乘法次数。

>

这几年，中国剩余定理还被用到了信息加密上。

2018 年，哥伦比亚大学的学者们发明了一种可以在文本中加密信息的方法，其中就应用了中国剩余定理来确保信息复原时的准确性。

只要手机对着一段文字扫一扫，算法就能给出加密后的信息。

这种方法名叫 FontCode，它是对普通字符进行微小的调整，然后再对调整后的字符重新编码信息，从而实现对信息的加密。

比如以下 5 种不同颜色的a，它们分别代表了 1—5 的数字信息。

如果不用颜色区分，肉眼很难分辨出它们和常规字体之间有什么不同。

但是机器可以。

只要通过扫描和分析，算法就能推断出哪些字母被特殊处理过，处理后的字母又表示了什么信息。

因此，在一段看似普通的文本中，可以很好隐藏这些特殊的字母，从而传递出一段加密的数字串。

然后，再对这些数字进行计算，就能得出真实想要传递的信息。

但是这样的加密方式还不够保险，毕竟字符出现在屏幕或纸面上时，它的格式都有可能发生一些细小的变化。

这时就需要中国剩余定理登场了。

在上面我们已经介绍了，通过线性同余方程组就能计算出数值。

如果想求解 3 个未知量，那么需要 3 个线性方程才能做到。

现在为了保险起见，科学家们把线性方程的数量增加了。

比如为了求解出 3 个未知量，他们会设置 5 个线性方程，5 个方程中只要知道 3 个，就能求解出想要的答案了。

显然，1000 多年过去了，虽然我们不会再像韩信点兵一样隐藏士兵数量，但是现代数学，计算机等领域的研究者们依旧能从中国剩余定理中获得源源不断的启发。