迹忆客 专注技术分享

如果我们有两个数字 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