扩展欧几里得算法

扩展欧几里得算法（英語：Extended Euclidean algorithm）是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足貝祖等式 如果a是负数，可以把问题转化成 （为a的绝对值），然后令。 通常談到最大公因數時，我們都會提到一個非常基本的事實（由貝祖等式给出）：給定二个整數a、b，必存在整數x、y使得ax + by = gcd(a,b)。 众所周知，已知两个数和，对它们进行辗转相除（欧几里得算法），可得它们的最大公约数。不过，在欧几里得算法中，我们仅仅利用了每步带余除法所得的余数。扩展欧几里得算法还利用了带余除法所得的商，在辗转相除的同时也能得到貝祖等式（貝祖定理中描述的等式）中的x、y两个系数。以扩展欧几里得算法求得的系数是满足裴蜀等式的最简系数。 另外，扩展欧几里得算法是一种自验证算法，最后一步得到的和（和的含义见下文）乘以后恰为和，可以用来验证计算结果是否正确。 扩展欧几里得算法可以用来计算模反元素(也叫模逆元)，求出模反元素是RSA加密算法中获得所需公钥、私钥的必要步骤。