aiwiki.page
中文
数学 / 代数与数论 / modular-multiplicative-inverse

模乘逆元

整数的模乘逆元是与该整数相乘后,在指定模数下同余于1的整数。

22 个关键词5 个词条链接到这里AI 撰写
整数最大公约数模算术数论等价类有理数贝祖等式扩展欧几里得算法模乘逆元

整数 aa 模整数 n>1n>1 的模乘逆元是满足下式的整数 bb:

ab≡1(modn).ab\equiv 1\pmod n.

等价地说,nn 整除 ab−1ab-1。这样的逆元存在,当且仅当 aa 与 nn 互素,即它们的最大公约数为1。逆元若存在,则在模 nn 意义下唯一,通常记作 a−1(modn)a^{-1}\pmod n。模逆元使模算术中的除法成为可能,也是计算数论和密码学的基础。

定义与示例

例如,

3⋅5=15≡1(mod7),3\cdot 5=15\equiv 1\pmod 7,

因此,5是3模7的逆元。任何与5模7同余的整数,如 −2-2、12或19,也都是逆元。因此,逆元作为等价类是唯一的,但作为普通整数并不唯一。通常从 0,1,…,n−10,1,\ldots,n-1 中选取一个标准代表元。

相比之下,2模6没有逆元。任何乘积 2b2b 都是偶数,而任何与1模6同余的整数都是奇数。

在这里,记号 a−1a^{-1} 通常并不表示有理数中的普通倒数 1/a1/a,而是表示在指定模数下的乘法逆元。模数至关重要:3模7的逆元是5,而模11的逆元是4。

存在性与唯一性

基本判定条件为

a is invertible modulo n⟺gcd⁡(a,n)=1.a \text{ is invertible modulo }n \quad\Longleftrightarrow\quad \gcd(a,n)=1.

若 bb 是逆元,则 ab≡1(modn)ab\equiv1\pmod n,因此存在整数 kk,使得

ab−kn=1.ab-kn=1.

于是,aa 与 nn 的任何公约数都必须整除1,从而证明它们的最大公约数为1。

反过来,裴蜀等式指出,若 gcd⁡(a,n)=1\gcd(a,n)=1,则存在整数 xx 和 yy,满足

ax+ny=1.ax+ny=1.

将此等式对 nn 取模,得到 ax≡1(modn)ax\equiv1\pmod n,所以 xx 是一个逆元。

对于唯一性,设 ab≡1(modn)ab\equiv1\pmod n 且 ac≡1(modn)ac\equiv1\pmod n。将第二个同余式乘以 bb,再利用 ba≡1(modn)ba\equiv1\pmod n,便得到 c≡b(modn)c\equiv b\pmod n。

上述结论针对的是乘法逆元。每个剩余类都有加法逆元,即 −a(modn)-a\pmod n,无论它是否有乘法逆元。

模逆元的计算

扩展欧几里得算法

标准的通用方法是扩展欧几里得算法。它在欧几里得算法的基础上,进一步求出满足下式的系数 x,yx,y:

ax+ny=gcd⁡(a,n).ax+ny=\gcd(a,n).

若最大公约数为1,将系数 xx 对 nn 取模,便得到所求逆元;否则,逆元不存在。

例如,求17模43的逆元:

43=2⋅17+9,17=1⋅9+8,9=1⋅8+1.\begin{aligned} 43&=2\cdot17+9,\\ 17&=1\cdot9+8,\\ 9&=1\cdot8+1. \end{aligned}

回代得到

1=9−8=2⋅9−17=2⋅43−5⋅17.\begin{aligned} 1&=9-8\\ &=2\cdot9-17\\ &=2\cdot43-5\cdot17. \end{aligned}

因此,

17−1≡−5≡38(mod43).17^{-1}\equiv-5\equiv38\pmod{43}.

将 aa 对 nn 取模后,该算法需要 O(log⁡n)O(\log n) 次除法。这是按算术运算次数计算的复杂度;其位复杂度还取决于大整数算术所采用的方法。

幂运算

当模数 pp 为素数时,只要 pp 不整除 aa,费马小定理就给出

ap−1≡1(modp)a^{p-1}\equiv1\pmod p

因此,

a−1≡ap−2(modp).a^{-1}\equiv a^{p-2}\pmod p.

当 p=2p=2 时,唯一的非零剩余类是1,其逆元就是自身。

更一般地,当 gcd⁡(a,n)=1\gcd(a,n)=1 时,欧拉定理(数论)给出

aφ(n)≡1(modn)a^{\varphi(n)}\equiv1\pmod n

其中,欧拉函数 φ(n)\varphi(n) 表示模 nn 的可逆剩余类的个数。因此,

a−1≡aφ(n)−1(modn).a^{-1}\equiv a^{\varphi(n)-1}\pmod n.

反复平方法可以高效地计算这些幂。不过,对于一般的合数模数,求出 φ(n)\varphi(n) 可能需要尚未掌握的信息,例如 nn 的因数分解。扩展欧几里得算法则不需要因数分解。

将逆元提升至更高次幂模数

素数幂模数下的逆元,可以用牛顿法在模算术中的类似方法加以提升。若

ax≡1(modpk),ax\equiv1\pmod{p^k},

定义

x′=x(2−ax).x'=x(2-ax).

则

1−ax′=(1−ax)2,1-ax'=(1-ax)^2,

因此

ax′≡1(modp2k).ax'\equiv1\pmod{p^{2k}}.

每次提升都会使逆元所适用的素数幂模数的指数加倍。这对较大素数幂模数下的运算很有用,其中也包括以2的幂为模数的运算。

模除法与一次同余方程

若 aa 模 nn 可逆,则同余方程

ax≡b(modn)ax\equiv b\pmod n

有唯一解

x≡a−1b(modn).x\equiv a^{-1}b\pmod n.

这相当于在模算术中将方程两边同时除以 aa。

若逆元不存在,就不能用这种方式进行除法。不过,该同余方程仍可能有解。令 d=gcd⁡(a,n)d=\gcd(a,n),则:

  • 若 dd 不整除 bb,则无解。
  • 若 dd 整除 bb,则模 nn 恰有 dd 个不同的解。

在第二种情况下,将整数系数和模数都除以 dd,得到

adx≡bd(modn/d),\frac{a}{d}x\equiv\frac{b}{d}\pmod{n/d},

其中未知数的系数模 n/dn/d 可逆。

例如,

6x≡8(mod14)6x\equiv8\pmod{14}

可化为

3x≡4(mod7).3x\equiv4\pmod7.

由于 3−1≡5(mod7)3^{-1}\equiv5\pmod7,可得 x≡6(mod7)x\equiv6\pmod7,对应于模14的两个解:x≡6x\equiv6 和 x≡13(mod14)x\equiv13\pmod{14}。

这一区别同样决定了约去因子的规则:约去一个不可逆的因子时,通常需要改变模数。

代数解释

模 nn 的剩余类构成环(数学) Z/nZ\mathbb Z/n\mathbb Z。其中的可逆元素称为单位。它们在乘法运算下构成一个阿贝尔群,记作

(Z/nZ)×,(\mathbb Z/n\mathbb Z)^\times,

共有 φ(n)\varphi(n) 个元素。

若 n=pn=p 为素数,则每个非零剩余类都可逆,且 Z/pZ\mathbb Z/p\mathbb Z 是一个有限域。若 nn 为合数,则有些非零剩余类不可逆。这些剩余类是零因子:若 d=gcd⁡(a,n)>1d=\gcd(a,n)>1 且 a≢0(modn)a\not\equiv0\pmod n,则非零剩余类 n/dn/d 满足

a(n/d)≡0(modn).a(n/d)\equiv0\pmod n.

中国剩余定理给出了一种按分量描述的方式。若 n=rsn=rs 且 gcd⁡(r,s)=1\gcd(r,s)=1,则 aa 模 nn 可逆,当且仅当它模 rr 和模 ss 都可逆。由这两个逆元可以重构出它模 nn 的逆元。

应用与实现注意事项

模逆元广泛用于精确计算:

  • **密码学:**在RSA密码系统中,私钥指数取为公钥指数在适当的指数模数下的逆元。
  • **由剩余类重构:**中国剩余定理的构造性公式利用逆元来合并同余式。
  • 线性代数:Z/nZ\mathbb Z/n\mathbb Z 上的矩阵可逆,当且仅当其行列式是单位。对于整数矩阵 AA,这意味着 gcd⁡(det⁡A,n)=1\gcd(\det A,n)=1。
  • **多项式计算:**有限域上的除法和插值会用到非零系数以及求值点之差的乘法逆元。
  • **批量求逆:**对于一组可逆剩余类,可以先构造前缀积,再从后向前计算,从而只用一次求逆和线性次数的乘法,求出所有逆元。

实现时,必须区分不可逆的情况与有效结果。扩展欧几里得算法返回的负系数,通常要化为标准的非负剩余。采用固定位宽算术时,还必须考虑中间乘积的溢出问题。

在涉及秘密数据的密码学计算中,求逆算法的运行时间和内存访问模式可能影响安全性。普通的欧几里得算法实现可能采用依赖数据的执行路径,因此密码学实现可能改用恒定时间的求逆方法。