《算法的乐趣》第五十五节

扩展欧几里得算法通过递归将方程化简为a%b=0的平凡解，再利用x=y'、y=x'-(a/b)*y'的递推关系反向推出原方程的解。

扩展欧几里得算法通过递归将方程化简为a%b=0的平凡解，再利用x=y'、y=x'-(a/b)*y'的递推关系反向推出原方程的解。该算法还可求解线性同余方程：将ax≡b(modn)改写为ax-ny=b即可求出x；当gcd(a,n)=1且b=1时，解x称为a对模n的乘法逆元，这在RSA加密中是基本操作。本章总结指出大数计算广泛用于天文、物理、生物及RSA算法，示例代码提供了CBigInt类实现。

RSA算法基于大素数分解难题，核心是大整数模幂运算C=A^B(modn)。直接先乘方再取模会导致中间结果过大，因此利用平方-乘降幂法将模幂转化为平均3log(E)/2次模乘运算。模乘的瓶颈在于取模除法，蒙哥马利算法（1985年提出）通过选取R=2^k将取模转为移位操作，避免除法，虽然单次计算开销略增，但对多次模乘的模幂运算提速显著。最终结合同余方程求出n'，在R的剩余系中完成模幂计算。素数生成需要素性测试：费马小定理因存在卡米歇尔数只能作为必要条件，实际判断大素数普遍采用米勒-拉宾算法。