扩展欧几里得算法

扩展欧几里得算法(Extended Euclidean Algorithm)是欧几里得算法的推广。在计算两个整数最大公约数的同时,它还能求出一对整数系数,使这对系数与两个原数的线性组合恰好等于它们的最大公约数,即满足贝祖等式。这组系数在求模逆元和解线性同余方程时至关重要。

概述

普通欧几里得算法只输出最大公约数,而许多数论应用还需要知道如何用两个原数的整数线性组合表示这个公约数。扩展版本在递归求公约数的回溯过程中同步推导出这组系数,几乎不增加额外开销,是数论与密码学中不可或缺的基础算法。

核心原理

• 贝祖等式:对任意整数,存在整数系数使其线性组合等于两数的最大公约数。
• 递归结构:利用较大数对较小数取余不断缩小问题规模,与普通辗转相除一致。
• 系数回溯:当递归到余数为零的边界时,公约数的系数可直接确定;回溯时根据取余关系逐层反推上一层的系数。
• 复杂度:与普通欧几里得算法相同,迭代次数与两数中较小者的对数成正比。

应用场景

扩展欧几里得算法主要用于求模逆元,即在模数与被求数互质时找出其乘法逆元,这是 RSA、椭圆曲线密码和各类模运算的核心步骤。它还用于求解形如线性同余方程的整数解、支持中国剩余定理的分量构造,以及数论竞赛中的诸多题目。

常见问题

问:什么条件下模逆元存在?答:当被求数与模数互质,即二者最大公约数为一时,模逆元存在且唯一;此时扩展欧几里得算法求得的系数取模后即为逆元。

问:它和费马小定理求逆元有何区别?答:费马小定理仅在模数为质数时适用且需做幂运算,扩展欧几里得算法只要求模数与被求数互质,适用范围更广、常数也较小。