扩展欧几里得算法 扩展欧几里得算法英語Extended Euclidean algorithm是欧几里得算法又叫辗转相除法的扩展已知整数ab扩展欧几里得算法可以在求得ab的最大公约数的同时找到整数xy其中一个可能是负数使它们满足貝祖等式 a x  b y  gcd  a  b  displaystyle axbygcdab 如果a是负数可以把问题转化成  a    x   b y  gcd   a   b  displaystyle leftarightxbygcdab   a  displaystyle leftaright 为a的绝对值然后令 x     x  displaystyle xx  在欧几里得算法中我们仅利用了每步带余除法所得的余数扩展欧几里得算法还利用了带余除法所得的商在辗转相除的同时也能得到貝祖等式中的xy两个系数以扩展欧几里得算法求得的系数是满足裴蜀等式的最简系数 另外扩展欧几里得算法是一种自验证算法最后一步得到的 s i   displaystyle si 和 t i   displaystyle ti  s i   displaystyle si 和 t i   displaystyle ti 的含义见下文乘以 gcd  a  b  displaystyle gcdab 后恰为 a displaystyle a 和 b displaystyle b 可以用来验证计算结果是否正确 扩展欧几里得算法可以用来计算模反元素求出模反元素是RSA加密算法中获得所需公钥私钥的必要步骤