在 Python 中计算模乘逆
Suraj Joshi
2023年1月30日
如果我们有两个数字 a 和 m，则 a 的模乘法逆元是模 m 下的 x，如果：
a * x % m = 1
在这种情况下，乘法逆只在 a 和 m 互质时才存在，即如果 a 和 m 的最大公约数是 1。
x 的值可以从 1 到 m-1。
使用朴素迭代方法的模乘逆
假设我们需要在模 m 下找到 a 的乘法倒数。如果模乘逆存在，它的值可以从 1 到 m-1。因此，我们遍历这个范围并检查模乘逆的条件。如果范围内的任何数字满足条件，我们将数字作为模乘逆。
def find_mod_inv(a, m):
for x in range(1, m):
if (a % m) * (x % m) % m == 1:
return x
raise Exception("The modular inverse does not exist.")
a = 13
m = 22
try:
res = find_mod_inv(a, m)
print("The required modular inverse is: " + str(res))
except:
print("The modular inverse does not exist.")
输出：
The required modular inverse is: 17
在这里，我们有一个名为 find_mod_inv 的函数，它以 a 和 m 作为输入并返回模数 m 下 a 的乘法逆。
如果数字 a 在模 m 下没有 a 的乘法倒数，它将引发和 Exception。
从上面的例子中，我们可以看到在模 22 下 13 的模乘逆是 17。
使用 pow() 内置函数的模乘逆
我们还可以使用 Python 的内置函数 pow() 来计算一个数的模乘法逆。
a = 38
m = 97
res = pow(a, m - 2, m)
print("The required modular inverse is: " + str(res))
输出：
The required modular inverse is: 23
要使用 pow() 方法计算模乘法逆，pow() 方法的第一个参数将是要找到模逆的数字，第二个参数将是模减去 2，最后一个参数将是模数的顺序。
但是，对于 Python 3.8 及更高版本，我们可以将第二个参数替换为 -1。
a = 38
m = 97
res = pow(a, -1, m)
print("The required modular inverse is: " + str(res))
输出
The required modular inverse is: 23
作者： Suraj Joshi
Suraj Joshi is a backend software engineer at Matrice.ai.
LinkedIn