在 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