模逆元计算

算法

模逆元是模运算中的一个重要概念,对于整数a和模数m,如果存在整数x满足a·x ≡ 1 (mod m),则称x为a模m的模逆元。模逆元通常通过扩展欧几里得算法计算,在密码学、数论和组合数学中有广泛应用。

时间复杂度:最差 O(log m)
空间复杂度:O(1)

算法讲解

模逆元计算

介绍

模逆元是数论中的重要概念,特别是在密码学、组合数学和各种算法中有广泛应用。对于整数a和模数m,如果存在整数x使得 a·x ≡ 1 (mod m),则称x为a关于模m的乘法逆元(简称模逆元),通常记作a^(-1) mod m。这相当于在模m的剩余系中找到a的"倒数"。

需要注意的是,模逆元只在a与m互质(即最大公约数gcd(a,m)=1)的情况下存在。当模数m是质数时,1到m-1的所有数都有模逆元;当m不是质数时,只有与m互质的数才有模逆元。

算法步骤

计算模逆元有几种常用方法:

方法一:扩展欧几里得算法

  1. 利用扩展欧几里得算法求解贝祖等式 ax + my = gcd(a,m)
  2. 当gcd(a,m)=1时,ax + my = 1
  3. 由此可得 ax ≡ 1 (mod m),即x就是所求的模逆元
  4. 注意:结果x可能为负,需要对m取模使结果在[0,m)范围内

方法二:费马小定理(仅适用于模数为质数的情况)

  1. 当m为质数且a不是m的倍数时,根据费马小定理,a^(m-1) ≡ 1 (mod m)
  2. 两边同时除以a,得到 a^(m-2) ≡ a^(-1) (mod m)
  3. 因此,a的模逆元为a^(m-2) mod m

...