韩信点兵算法原理编程韩信点兵算法原理( 二 ) _经验知识

其他的解只能和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]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