在 Python 中计算模乘逆

Suraj Joshi 2023年1月30日 2021年10月2日
  1. 使用朴素迭代方法的模乘逆
  2. 使用 pow() 内置函数的模乘逆
在 Python 中计算模乘逆

如果我们有两个数字 am,则 a 的模乘法逆元是模 m 下的 x,如果:

a * x % m = 1

在这种情况下,乘法逆只在 am 互质时才存在,即如果 am 的最大公约数是 1

x 的值可以从 1m-1

使用朴素迭代方法的模乘逆

假设我们需要在模 m 下找到 a 的乘法倒数。如果模乘逆存在,它的值可以从 1m-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 的函数,它以 am 作为输入并返回模数 ma 的乘法逆。

如果数字 a 在模 m 下没有 a 的乘法倒数,它将引发和 Exception

从上面的例子中,我们可以看到在模 2213 的模乘逆是 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
Author: Suraj Joshi
Suraj Joshi avatar Suraj Joshi avatar

Suraj Joshi is a backend software engineer at Matrice.ai.

LinkedIn

相关文章 - Python Math