在 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