浅谈求逆元

本篇博客是对密码学中数论部分的整理，主要关注如何求同余运算中的逆元。重点是欧几里得算法和扩展欧几里得算法的应用，难度中等偏下，但是十分重要。之后再介绍费马小定理求解逆元，利用快速幂算法，应该能够比较快速的求出解。

本文假设读者已经掌握基础的数论知识，故基础部分略过不讲。本文章将按照欧几里得算法、扩展欧几里得算法、费马小定理的顺序讲解。后续还可以扩展到中国剩余定理，参见文章浅谈中国剩余定理 | Adam8en の 8log。

🚀🚀🚀

欧几里得算法

在介绍欧几里得算法前，我们先引入最大公约数的概念。

定理：设$a,b,c$是任意不全为零的整数，且$a=qb+c$，其中$q$是整数。

则有$\gcd(a,b)=\gcd(b,c)$，即被除数和除数的最大公因子与除数和余数的最大公因子相同。

例如：

$\gcd(18,12)=\gcd(12,6)=\gcd(6,0)=6$

于是这个定理被总结为欧几里得算法（Euclidean Algorithm），因此也得名辗转相除法。

任给两个整数$a,b$，设$a>b>0$，则有：

$\begin{array}{c} \begin{array}{cc} a=b q_{0}+r_{0}, & 0<r_{0}<b, \\ b=r_{0} q_{1}+r_{1}, & 0<r_{1}<r_{0} \end{array}\\ \quad......\\ \begin{array}{c} r_{n-2}=r_{n-1} q_{n}+r_{n}, \quad 0<r_{n}<r_{n-1} \\ r_{n-1}=\mathrm{r}_{\mathrm{n}} \mathrm{q}_{\mathrm{n}+1}+\mathrm{r}_{\mathrm{n}+1}, \quad \mathrm{r}_{\mathrm{n}+1}=0 \end{array} \end{array}$

因为$b>r_0>r_1>r_2>...$，故经过有限次除法后，总可以得到一个余数是零，即上式中$r_{n+1}=0,r_n=\gcd(a,b)$。

以下是一个运用欧几里得算法求最大公约数的例子：

扩展欧几里得算法

扩展欧几里得算法是最通用且效率较高的方法之一。它不仅可以求解逆元，还可以用于求解线性同余方程和多项式逆元。

在介绍扩展欧几里得算法前，我们先引入一个定理：

定理：任给整数$a>b>0$，则存在两个整数$x,y$使得$\gcd(a,b)=xa+yb$（贝祖等式）

如何证明这个算法呢，通过逆向运用欧几里得算法就可以实现，而这个过程就是扩展欧几里得算法。

回到欧几里得算法的最后一项，依次将后一项代入前一项。

$\begin{array}{c} \begin{aligned} r_{n} & =r_{n-2}-r_{n-1} q_{n} \\ r_{n-1} & =r_{n-3}-r_{n-2} q_{n-1} \end{aligned}\\.\\.\\.\\ \begin{array}{c} r_{1}=b-r_{0} q_{1} \\ r_{0}=a-b q_{0} \end{array} \end{array}$

即可得$r_n$由$a$和$b$的线性组合表示。

下面给出扩展欧几里得算法的应用举例：

稍作变换，当$\gcd(a,m)=1$时，应用扩展欧几里得定理，最后得到：

$1=ax+my$

两边同时模$m$

$ax\bmod m=1$

即此时的$x$为$a^{-1}$，即所求$a$的逆元。

为了加深印象，再给出一个应用扩展欧几里得算法求逆元的例子：

可以看到，大致的流程就是先正向应用一遍欧几里得算法，然后再依次把每个式子的余数倒着代回原式，最后就可以逆推得到关于$\gcd(a,b)=ax+by$的式子，解出$x,y$。

费马小定理

可以看到运用扩展欧几里得定理虽然效率较高，但是仍然要先应用一遍正向的欧几里得算法再反推回去，稍显麻烦。在某些时候我们可以用费马小定理来提升计算效率。

费马小定理对素数模数$p$特别有用。具体来说，如果$a$和$p$互质（即$\gcd(a,p)=1$），那么$a^{p-1}\equiv 1\bmod p$。因此逆元可以表示为：

$a^{-1}\equiv a^{p-2}\bmod p$

对于大数的幂运算，通常还使用快速幂算法来进一步提高效率。

快速幂算法

假设我们要求$a$模$p$的逆元，其中$p$是素数。则我们需要求$a^{p-2}\bmod p$。

当$p$特别大时，计算幂的操作将会变得复杂。我们引入了快速幂算法，他能将朴素的计算幂时间复杂度从$O(n)$优化到$O(\log n)$。

假设我们需要计算$a^b\bmod m$。首先可以把$b$表示为二进制的形式。例如，若$b=13$，则其二进制表示为$1101_2$。根据二进制表示，$13$可以表示为：

$13=1·2^3+1·2^2+0·2^1+1·2^0$

因此：

$a^{13}=a^{2^{3}+2^2+2^0}=a^{2^3}·a^{2^2}·a^{2^0}$

通过这种表示方式，可以避免直接计算大幂次，而是通过迭代平方来逐步得到结果。

应用快速幂算法的步骤如下：

1. 初始化结果为1：$result=1$
2. 当$exp$大于0时，重复以下步骤：
   • 如果$exp$是奇数（即$exp\%2==1$），则更新结果：$result=(result·base)\%mod$
   • 将$base$平方，并对$mod$取模：$base=(base·base)\% mod$。
   • 将$exp$右移一位（即$exp=exp//2$）

为方便理解，这里给出实现快速幂算法的Python代码。

def fast_pow(base, exp, mod):
    result = 1  # 初始化结果
    base = base % mod  # 确保 base 小于 mod，避免不必要的大数运算
    while exp > 0:
        if exp % 2 == 1:  # 如果 exp 是奇数
            result = (result * base) % mod  # 更新结果
        base = (base * base) % mod  # 将 base 平方
        exp //= 2  # 将 exp 右移一位
    return result

# 示例
base = 3
exp = 13
mod = 11
print(fast_pow(base, exp, mod))  # 输出应为 5，因为 3^13 ≡ 5 (mod 11)

下面我们运用费马小定理+快速幂算法来解一道题。

---