整数 a 模整数 n>1 的模乘逆元是满足下式的整数 b:
ab≡1(modn).
等价地说,n 整除 ab−1。这样的逆元存在,当且仅当 a 与 n 互素,即它们的最大公约数为1。逆元若存在,则在模 n 意义下唯一,通常记作 a−1(modn)。模逆元使模算术中的除法成为可能,也是计算数论和密码学的基础。
定义与示例
例如,
3⋅5=15≡1(mod7),
因此,5是3模7的逆元。任何与5模7同余的整数,如 −2、12或19,也都是逆元。因此,逆元作为等价类是唯一的,但作为普通整数并不唯一。通常从 0,1,…,n−1 中选取一个标准代表元。
相比之下,2模6没有逆元。任何乘积 2b 都是偶数,而任何与1模6同余的整数都是奇数。
在这里,记号 a−1 通常并不表示有理数中的普通倒数 1/a,而是表示在指定模数下的乘法逆元。模数至关重要:3模7的逆元是5,而模11的逆元是4。
存在性与唯一性
基本判定条件为
a is invertible modulo n⟺gcd(a,n)=1.
若 b 是逆元,则 ab≡1(modn),因此存在整数 k,使得
于是,a 与 n 的任何公约数都必须整除1,从而证明它们的最大公约数为1。
反过来,裴蜀等式指出,若 gcd(a,n)=1,则存在整数 x 和 y,满足
将此等式对 n 取模,得到 ax≡1(modn),所以 x 是一个逆元。
对于唯一性,设 ab≡1(modn) 且 ac≡1(modn)。将第二个同余式乘以 b,再利用 ba≡1(modn),便得到 c≡b(modn)。
上述结论针对的是乘法逆元。每个剩余类都有加法逆元,即 −a(modn),无论它是否有乘法逆元。
模逆元的计算
扩展欧几里得算法
标准的通用方法是扩展欧几里得算法。它在欧几里得算法的基础上,进一步求出满足下式的系数 x,y:
ax+ny=gcd(a,n).
若最大公约数为1,将系数 x 对 n 取模,便得到所求逆元;否则,逆元不存在。
例如,求17模43的逆元:
43179=2⋅17+9,=1⋅9+8,=1⋅8+1.
回代得到
1=9−8=2⋅9−17=2⋅43−5⋅17.
因此,
17−1≡−5≡38(mod43).
将 a 对 n 取模后,该算法需要 O(logn) 次除法。这是按算术运算次数计算的复杂度;其位复杂度还取决于大整数算术所采用的方法。
幂运算
当模数 p 为素数时,只要 p 不整除 a,费马小定理就给出
ap−1≡1(modp)
因此,
a−1≡ap−2(modp).
当 p=2 时,唯一的非零剩余类是1,其逆元就是自身。
更一般地,当 gcd(a,n)=1 时,欧拉定理(数论)给出
aφ(n)≡1(modn)
其中,欧拉函数 φ(n) 表示模 n 的可逆剩余类的个数。因此,
a−1≡aφ(n)−1(modn).
反复平方法可以高效地计算这些幂。不过,对于一般的合数模数,求出 φ(n) 可能需要尚未掌握的信息,例如 n 的因数分解。扩展欧几里得算法则不需要因数分解。
将逆元提升至更高次幂模数
素数幂模数下的逆元,可以用牛顿法在模算术中的类似方法加以提升。若
ax≡1(modpk),
定义
x′=x(2−ax).
则
1−ax′=(1−ax)2,
因此
ax′≡1(modp2k).
每次提升都会使逆元所适用的素数幂模数的指数加倍。这对较大素数幂模数下的运算很有用,其中也包括以2的幂为模数的运算。
模除法与一次同余方程
若 a 模 n 可逆,则同余方程
ax≡b(modn)
有唯一解
x≡a−1b(modn).
这相当于在模算术中将方程两边同时除以 a。
若逆元不存在,就不能用这种方式进行除法。不过,该同余方程仍可能有解。令 d=gcd(a,n),则:
- 若 d 不整除 b,则无解。
- 若 d 整除 b,则模 n 恰有 d 个不同的解。
在第二种情况下,将整数系数和模数都除以 d,得到
dax≡db(modn/d),
其中未知数的系数模 n/d 可逆。
例如,
6x≡8(mod14)
可化为
3x≡4(mod7).
由于 3−1≡5(mod7),可得 x≡6(mod7),对应于模14的两个解:x≡6 和 x≡13(mod14)。
这一区别同样决定了约去因子的规则:约去一个不可逆的因子时,通常需要改变模数。
代数解释
模 n 的剩余类构成环(数学) Z/nZ。其中的可逆元素称为单位。它们在乘法运算下构成一个阿贝尔群,记作
(Z/nZ)×,
共有 φ(n) 个元素。
若 n=p 为素数,则每个非零剩余类都可逆,且 Z/pZ 是一个有限域。若 n 为合数,则有些非零剩余类不可逆。这些剩余类是零因子:若 d=gcd(a,n)>1 且 a≡0(modn),则非零剩余类 n/d 满足
a(n/d)≡0(modn).
中国剩余定理给出了一种按分量描述的方式。若 n=rs 且 gcd(r,s)=1,则 a 模 n 可逆,当且仅当它模 r 和模 s 都可逆。由这两个逆元可以重构出它模 n 的逆元。
应用与实现注意事项
模逆元广泛用于精确计算:
- **密码学:**在RSA密码系统中,私钥指数取为公钥指数在适当的指数模数下的逆元。
- **由剩余类重构:**中国剩余定理的构造性公式利用逆元来合并同余式。
- 线性代数:Z/nZ 上的矩阵可逆,当且仅当其行列式是单位。对于整数矩阵 A,这意味着 gcd(detA,n)=1。
- **多项式计算:**有限域上的除法和插值会用到非零系数以及求值点之差的乘法逆元。
- **批量求逆:**对于一组可逆剩余类,可以先构造前缀积,再从后向前计算,从而只用一次求逆和线性次数的乘法,求出所有逆元。
实现时,必须区分不可逆的情况与有效结果。扩展欧几里得算法返回的负系数,通常要化为标准的非负剩余。采用固定位宽算术时,还必须考虑中间乘积的溢出问题。
在涉及秘密数据的密码学计算中,求逆算法的运行时间和内存访问模式可能影响安全性。普通的欧几里得算法实现可能采用依赖数据的执行路径,因此密码学实现可能改用恒定时间的求逆方法。