公元前三世纪，欧几里得提出的辗转相除法用于求最大公因数，至今在现代公钥密码学中仍然重要。扩展欧几里得算法及其衍生技术是RSA密钥生成和模逆元计算的核心。文章详细介绍了辗转相除法、扩展欧几里得算法、中国剩余定理及Montgomery模乘，强调了这些算法在互联网安全中的应用和重要性。

本文介绍了博主的算法竞赛模板，最新实现已迁移至 CP-lib，模板代码正在逐步更新。内容涵盖了 Simpson 法、自适应 Simpson 法、Cantor 展开、无向图连通子图、精确覆盖问题及扩展中国剩余定理等。

文章讨论了中国古代数学中的“孙子问题”，即同余方程组的求解。通过《孙子算经》的方法，介绍了利用最小公倍数和余数求解正整数解的过程。文中提到的关键数字70、21和15是通过模数的约简得到的，体现了中国剩余定理的基本形式。