模逆元

对整数模数 $m>1$，若整数 $a$ 与 $x$ 满足

$$ ax\equiv1\pmod m, $$

则 $x$ 是 $a$ 模 $m$ 的乘法逆元，记为 $a^{-1}$。它存在当且仅当 $\gcd(a,m)=1$；存在时在模 $m$ 的剩余类中唯一。

例如 $3\times7=21\equiv1\pmod{10}$，所以 3 模 10 的逆元是 7。2 模 10 没有逆元，因为 2 与 10 不互素。

如何求逆元

扩展欧几里得算法 可求整数 $x,y$：

$$ ax+my=\gcd(a,m). $$

若右侧为 1，则对模 $m$ 取余得到 $ax\equiv1$，因此 $x$ 就是逆元。实现中把可能为负的系数归一化到 $0\le x<m$。

例：

$$ 55\times7-2\times192=1, $$

因此 $7^{-1}\equiv55\pmod{192}$。

用逆元做模除法

要解 $ax\equiv b\pmod m$，如果 $a$ 可逆，可以两边乘 $a^{-1}$：

$$ x\equiv a^{-1}b\pmod m. $$

如果 $a$ 不可逆，就不能直接除以它。例如 $2x\equiv12\pmod{26}$ 有 $x=6,19$ 两个剩余类，而不是单一答案。相关计算见 affine-cipher-solving。

RSA 中的角色

RSA 的私有指数 $d$ 与公有指数 $e$ 满足特定模数下的逆元关系。对不同素数 $p,q$，令 $n=pq$：

• 教学中常选 $ed\equiv1\pmod{\phi(n)}$，其中 $\phi(n)=(p-1)(q-1)$。
• 也可使用 $\lambda(n)=\operatorname{lcm}(p-1,q-1)$ 的关系；满足该条件就能构造相应的 RSA 指数运算。

这里解密使用 $C^d\bmod n$，不是把密文乘以 $d$；逆元关系约束的是指数乘积 $ed$。

模逆元本身容易计算；困难在于攻击者通常不知道由秘密因子确定的模数。不能把“求逆元”本身说成难题，也不能说计算 $d$ 的唯一途径就是先分解 $n$。

裸 RSA 幂运算不构成安全的实际加密方案，具体结构与填充见 RSA。模逆元的定义不依赖 RSA，也不限于模 $\phi(n)$。

学习检查

1. 为什么 3 模 10 有逆元，2 模 10 没有？
2. 贝祖等式中的哪个系数给出逆元？负数系数如何表示？
3. 为什么同余式不能总像实数等式那样约去系数？

[!info] related notes

• 辗转相除法
• 仿射密码
• RSA