算法: 求模意义下的乘法逆元

来自吾萌百科
Luke li讨论 | 贡献2024年10月24日 (四) 09:01的版本 (模意义下的乘法逆元是一种重要的数论算法,可用于密码加密等领域。有主要的两种求乘法逆元的方法:费马小定理法,和扩展欧几里得法。)
(差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)

预备知识

模运算

定义

这里我们只讨论整数中的乘法逆元。[1] 具体而言,如果在模 [math]\displaystyle{ p }[/math] 意义下,[math]\displaystyle{ ax\equiv 1(mod\ p) }[/math] ,我们就称 [math]\displaystyle{ x }[/math][math]\displaystyle{ a }[/math] 的乘法逆元。记作 [math]\displaystyle{ a^{-1}=x }[/math]

如果 [math]\displaystyle{ p }[/math] 是质数,那么对于任意的 [math]\displaystyle{ a\ne 0 }[/math] 都一定存在乘法逆元;如果 [math]\displaystyle{ p }[/math] 不是质数,那么可能存在 [math]\displaystyle{ a\ne 0 }[/math] 不存在乘法逆元。

用途

在处理过程中需要取模的问题时,可能会遇到除法。我们都知道,把取模过的数字相除无法得出原来的结果(即 [math]\displaystyle{ \frac{a\mod c}{b\mod c}\ne \frac{a}{b} }[/math] ),此时我们就需要用 [math]\displaystyle{ \times a^{-1} }[/math] 代替 [math]\displaystyle{ \div a }[/math]

另外,乘法逆元在加密算法(如RSA),扩展中国剩余定理算法等算法中有着重要意义。

做法

如何求取乘法逆元呢?这里介绍两种简单的方法。

费马小定理

根据费马小定理,我们有 [math]\displaystyle{ a^p\equiv a(mod\ p),\ p\ \ is\ \ prime }[/math] 。因此对于 [math]\displaystyle{ p }[/math] 是质数的情形,我们可以使用 [math]\displaystyle{ a^{p-2} }[/math] 作为 [math]\displaystyle{ a }[/math] 在模 [math]\displaystyle{ p }[/math] 意义下的乘法逆元。

这可以使用快速幂在时间复杂度 [math]\displaystyle{ O(\log p) }[/math] 内计算出来。

扩展欧几里得

我们都知道欧几里得的辗转相除法,有人从这一算法中得到启发发明了扩展欧几里得算法。

这一算法与裴蜀定理息息相关。裴蜀定理是说:[math]\displaystyle{ ax+by=c }[/math] 有解,当且仅当 [math]\displaystyle{ \gcd(a,b)|c }[/math] 。因此我们可以先解出 [math]\displaystyle{ ax+by=\gcd(a,b) }[/math] 的解集,然后再把 [math]\displaystyle{ x,y }[/math][math]\displaystyle{ \frac{c}{\gcd(a,b)} }[/math] ,即可得出最后的解。 [2]

在辗转相除法中,我们知道 [math]\displaystyle{ \gcd(a,b)=\gcd(b,a\ mod\ b) , b\ne 0 }[/math] 。运用递归的思想,先求出 [math]\displaystyle{ bx'+(a\ mod\ b)y'=\gcd(b,a\ mod\ b)=\gcd(a,b) }[/math] 的解,然后再转化为原方程的解即可。

可以列出方程式 [math]\displaystyle{ ax+by=bx'+(a\ mod\ b)y' }[/math] ,其中 [math]\displaystyle{ x,y }[/math] 是未知数,其余的字母都是已知数。因为 [math]\displaystyle{ a\ mod\ b=a-a\lfloor \frac{a}{b} \rfloor }[/math] ,移项得到 [math]\displaystyle{ ax+by=a(y'-\lfloor \frac{a}{b}\rfloor y')+bx' }[/math] ,所以 [math]\displaystyle{ x=y'-\lfloor \frac{a}{b}\rfloor y',\ y=x' }[/math] 是原方程一组可行的解。

这样我们就得到了解方程 [math]\displaystyle{ ax+by=c }[/math] 的方法。

将“求模 [math]\displaystyle{ p }[/math] 意义下 [math]\displaystyle{ a }[/math] 的乘法逆元”这个问题转化一下,就可以改为求 [math]\displaystyle{ ax+py=1 }[/math] 这一问题中 [math]\displaystyle{ x }[/math]的解。显然可以使用裴蜀定理判断是否有解,然后使用exgcd(扩展欧几里得)解决。

  1. OI-wiki中更详细的介绍
  2. 详情见 oi-wiki贝祖定理