在 Python 中計算模乘逆
Suraj Joshi
2023年1月30日
2021年10月2日
如果我們有兩個數字 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
Author: Suraj Joshi
Suraj Joshi is a backend software engineer at Matrice.ai.
LinkedIn