扩展欧几里得算法

1. 核心目标

不仅求出 $(a,b)$，还要找到满足 裴蜀等式 (Bézout’s identity) 的整数系数 $s$ 和 $t$： $sa+tb=(a,b)$

2. 计算方法 (逆向回代法)

在执行欧几里得算法得到 $r_k=r_{k-2}-r_{k-1}{q}_{k-1}$ 后，将余数层层回代表示为 $a$ 和 $b$ 的线性组合。

递推公式法（适合编程或手算列表）： 设 $r_i=r_{i-2}-q_i{r}_{i-1}$，则系数 $s_i,t_i$ 满足：

$$\{\begin{array}{l}{s}_i=s_{i-2}-q_i{s}_{i-1}\\ t_i=t_{i-2}-q_i{t}_{i-1}\end{array}$$

初始值：

• $s_0=1,s_1=0$
• $t_0=0,t_1=1$

3. 关键应用：求模逆元

这是信安数学中最常见的考题。

若 $(a,m)=1$，则 $s\cdot a+t\cdot m=1$。

在模 $m$ 意义下： $s\cdot a\equiv 1(\mathrm{mod}m)$ 即 $s$ 是 $a$ 模 $m$ 的逆元，记作 $a^{-1}(\mathrm{mod}m)$。

举例说明

求 $17$ 模 $59$ 的逆元 $x$。

即求解 $17x\equiv 1(\mathrm{mod}59)$，也就是 $17x+59y=1$。

1. 检查： $\gcd (17,59)=1$，逆元存在。

2. 运行 EEA： $\begin{array}{rl}59& =3\cdot 17+8\\ 17& =2\cdot 8+1\end{array}$ 回代：

   $\begin{array}{rl}1& =17-2\cdot 8\\ 1& =17-2\cdot (59-3\cdot 17)\\ 1& =17-2\cdot 59+6\cdot 17\\ 1& =7\cdot 17-2\cdot 59\end{array}$

   我们得到 $x^{\prime }=7$，$y^{\prime }=-2$。

3. 确定逆元：7 \cdot 17 - 2 \cdot 59 = 1$$7 \cdot 17 \equiv 1 \pmod{59}

   逆元 $x$ 为 $7$。

考点提示

如果计算出的 $s$ 是负数，记得加上模数 $m$ 转换为正整数：$s=(s\mathrm{mod}m+m)\mathrm{mod}m$。