椭圆曲线ECC或SM2算法中，需要在素数有限域 $p$ 内计算某个整数 $a$ 的逆元 $b$。逆元的定义如下：

$$ \begin{cases} a \times b = 1(mod p) \\ b = a ^ {-1} \end{cases} $$

这里 $mod p$ 的含义为等号左右两边取模，取模的结果一定为非负整数，如： $$ 10 \times 12 = 8(mod 7) \Rightarrow 120 mod 7 = 8 mod 7 $$

计算逆元 $b$ 的方法有很多，最简单的方法，是指数运算： $$ b = a ^ {p - 2} mod p $$ 但是这种方法涉及到指数运算，计算量大，效率低。更高效的算法，是使用扩展欧几里得算法（又叫辗转相除法），定义如下： $$ \begin{cases} ax + cy = gcd(a,c) \\ gcd(a,c)：a和c的最大公约数 \\ 求：x和y \end{cases} $$

当 $c = p$ 的时候，因为$p$是素数，它与任何数的最大公约数都是1，所以等式变为： $$ ax + py = 1(mod p) \Rightarrow ax = 1(mod p) $$ 这样，求出 $x$，就是求出了 $a$ 的逆元。

那如何计算出 $x$ 是多少呢？这里就用到里递归的解法：

因为： $$gcd(a,p) = gcd(p, a \ modp)$$ 所以： $$ \begin{cases} ax_1 + py_1 = px_2 + (a \ modp)y_2 \\ a \ modp = a - [ {a \over p} ]p \\ 注：[ \ ]表示向下取整，例如 [{11 \over 3}] = 3 \end{cases} $$

推导这个方程： $$ ax_1 + py_1 \\ \begin{aligned} & = px_2 + (a \ modp)y_2 \\ & = px_2 + (a - [ {a \over p} ]p)y_2 \\ & = ay_2 + p(x_2 - [{a \over p}]y_2) \end{aligned} $$

要让等式两边相等，则： $$ \begin{cases} x_1 = y_2 \\ y_1 = x_2 - [{a \over p}]y_2 \end{cases} $$

同理，将 $x_2$ 和 $y_2$ 转化为 $x_3$ 和 $y_3$ 的形式，以此类推，直到 $x_n$ 的系数等于1，$y_n$ 的系数等于0，然后反向计算，就得到了结果。

因为不好理解，我这里举个例子，求20在11素数域中的逆元： $$ 20x_1 + 11y_1 = 1(mod11) $$ 计算： $$ 20x_1 + 11y_1 \\ \begin{aligned} & = 11x_2 + (20mod11)y_2 = 11x_2 + 9y_2 \\ & = 9x_3 + (11mod9)y_3 = 9x_3 + 2y_3 \\ & = 2x_4 + (9mod2)y_4 = 2x_4 + 1y_4 \\ & = 1x_5 + (2mod1)y_5 = 1x_5 + 0y_5 = 1 \\ & \Rightarrow \begin{cases} x_5 = 1 \\ y_5 = 0（可以为任意值，取0比较方便） \end{cases} \end{aligned} $$ 因为： $$ \begin{cases} x_4 = y_5 \\ y_4 = x_5 - [{a_4 \over p_4}]y_5 = x_5 - [{2 \over 1}]y_5 \end{cases} \Rightarrow \begin{cases} x_4 = 0 \\ y_4 = 1 \end{cases} $$ 同理求得： $$ \begin{cases} x_3 = y_4 \\ y_3 = x_4 - [{a_3 \over p_3}]y_4 = x_4 - [{9 \over 2}]y_4 \end{cases} \Rightarrow \begin{cases} x_3 = 1 \\ y_3 = -4mod11 = 7 \end{cases} $$

$$ \begin{cases} x_2 = y_3 \\ y_2 = x_3 - [{a_2 \over p_2}]y_3 = x_3 - [{11 \over 9}]y_3 \end{cases} \Rightarrow \begin{cases} x_2 = 7 \\ y_2 = -6mod11 = 5 \end{cases} $$

$$ \begin{cases} x_1 = y_2 \\ y_1 = x_2 - [{a_1 \over p_1}]y_2 = x_2 - [{20 \over 11}]y_2 \end{cases} \Rightarrow \begin{cases} x_1 = 5 \\ y_1 = 2 \end{cases} $$

结果：
$$20在11素数域中的逆元 = 5$$

验算： $$(20 \times 5)mod11 = 100mod11 = 1$$

使用指数法计算： $$ 20 ^ {11-2} mod11 = 20 ^ 9 mod11 = 5 $$