扩展欧几里德算法（Extended Euclid）

作者：吕默威

在进行RSA加密的时候，其中有一步是给定两个互质的整数a和b，要计算出a对于b的模反元素d（也有的说是a关于模b的逆元），也就是说求一个整数d，使得ad被b除的余数为1。即a，b，d满足如下公式：

也有的地方写成：

这里想要求出d，就要用到扩展欧几里德算法。

要讲扩展欧几里德算法，可以先从欧几里德算法讲起。欧几里德算法又称辗转相除法，用于计算两个整数a，b的最大公约数。 其计算原理依赖于如下定理：

两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。

也可以描述成：

其中，a、b均为整数，gcd(a,b)表示a和b的最大公约数，是greatest common divisor的缩写（不是我们伟大的党）。

该定理可以用如下方法证明：

假设c是a，b的一个公约数，则有：

因此c也是a mod b的约数，所以c就是b，a mod b的公约数，因为最大公约数也是公约数，所以定理得整。

基本代码实现：

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return
        gcd(b, a % b);
}

上面代码用递归实现，递归的结束条件是b = 0，因为如果两个整数a、b，有a % b = 0，那么a、b的最大公约数就是b。

上面说完了欧几里德算法，再看扩展欧几里德算法。扩展欧几里德算法是用来在已知整数a、b求解一组整数x、y，使它们满足等式：

根据贝祖定理，x、y是必定存在的，证明从略。

扩展欧几里德算法思路如下：

当a=b=0，x、y可取任意值，这个没什么意义；

当a!=0，b=0，gcd(a,b)=a，此时可令x=1、y=1，其实y可以取任意值；

当ab!=0，设:

根据：

可得：

根据恒等定理可得

这样就可以把x₁、y₁用x₂、y₂来表示，进行递归计算，而递归结束的条件就是b=0。 扩展欧几里德的代码实现：

static Integer[] exgcd(int a, int b)
{
    if (b == 0)
    {
        return new Integer[]{ 1, 1 };
    }
    Integer[] ret = exgcd(b, a % b);
    int t = ret[0];
    ret[0] = ret[1];
    ret[1] = t - a / b * ret[1];
    return ret;
}

我们回过头再来看本文开头的问题：给定两个互质的整数a和b，计算出一个整数d，使得ad被b除的余数为1。 先来解释什么叫互质：如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。比如，15和32没有公因子，所以它们是互质关系。 所以a和b互质，就有：

于是，就有：

这样就可以用扩展欧几里德算法来求出d的解了。

扩展欧几里德算法除了可以计算模反元素，还可以用来求解不定方程和线性同余方程。

本文来自网易实践者社区，经作者吕默威授权发布