====== 椭圆曲线ECC(SM2)算法中的逆元高性能快速算法 ======

椭圆曲线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) => 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) => 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 \\
& => 
\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}
=>
\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}
=>
\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}
=>
\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}
=>
\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
$$