晓查 明敏 发自 凹非寺

量子位 报道 | 公众号 QbitAI

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

相传，楚汉争霸之时，韩信率1500名将士与楚军交战败退，退往山上，这时候敌军率五百骑杀奔而来，韩信便急速点兵迎敌。

韩信命令士兵3人一排，结果多出2名；接着命令士兵5人一排，结果多出3名；他又命令士兵7人一排，结果又多出2名。

韩信马上算出，军中还剩1073人，而敌人不足五百，而且居高临下、以众击寡，于是率军杀得敌方大败而逃。

韩信是如何算出人数的，背后的算法又是如何影响当今的计算机领域？且往下看。

韩信还是个数学家？

当然，韩信算出士兵人数只是个传说，韩信本人并非数学大师。这个问题最早见于一本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。

这样寻找解的过程显然太繁琐。后来，明朝数学家程大位把求解方法编成了一首诗：

三人同行七十稀，五树梅花廿一枝。

七子团圆正半月，除百零五便得知。

意思是：

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

70 × 2 + 21 × 3 + 15 × 2 = 233 – 2 × 105 = 23

其他的解只能和23相差105的整数倍，韩信应该是估计出军队大致人数，取了105×10+23=1073这个解。

以上70、21、15几组数到底是怎么来的，有兴趣的读者可以进一步阅读“中国剩余定理”的通解，在此不再赘述。

这道“韩信点兵”问题不仅仅能用于点兵，甚至在天文历法上也有重要应用。

假设有一颗彗星4年出现一次，我们在1991年看到了它、另一颗彗星10年看到一次，我们在1997年看到了它。我们下一次在同一年看到它们是什么时候？

X ≡ 1991 (mod 4)
X ≡ 1997 (mod 10)

经过计算，它们上一次相会是在2007年，而且每隔20年重逢一次，所以下一次应该是2027年。

时至今日，中国剩余定理已经成为了很多计算机加密算法的基础，它的应用范围已经超乎你的想象。

影响当今计算机算法

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

比如非常有名的RSA加密算法，就应用了中国剩余定理。

我们知道在数论中，想要求解出两个大素数比较简单，但是想要对它们的乘积进行因式分解就很困难了。

而RSA加密算法就是把这个乘积作为了自己的加密密钥。

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

此外，在快速傅里叶变换（FFT）中也应用了中国剩余定理，它可以大大减少计算离散傅里叶变换时所需的乘法次数。

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

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

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

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

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

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

但是机器可以。

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

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

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

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

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

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

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

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

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

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

参考链接：
[1]
[2]
[3]http://www.xinhuanet.com/science/2018-08/07/c_137372635.htm

— 完 —

量子位 QbitAI · 头条号签约

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