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

乘法逆元是数论中的重要概念，定义为对于整数a和模数m，若存在b使得a·b≡1（mod m），则b为a在模m下的乘法逆元。常用的求解方法包括扩展欧几里得算法和费马小定理。扩展欧几里得算法高效求解逆元，而费马小定理适用于质数模。若a与m不互质，则逆元不存在。