Python でモジュラ逆数を計算する

1. ナイーブ反復アプローチを使用したモジュラ逆数
2. pow() 組み込み関数を使用したモジュラ逆数

a と m の 2つの数がある場合、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 の逆数を持たない場合、それは発生し、例外になります。

上記の例から、モジュロ 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 番目のパラメーターはモジュロからを引いた次数になります。2 そして最後のパラメータはモジュロの次数になります。

ただし、Python 3.8 以降の場合、2 番目の引数を -1 に置き換えることができます。

a = 38
m = 97
res = pow(a, -1, m)
print("The required modular inverse is: " + str(res))

出力

The required modular inverse is: 23