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

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

am の 2つの数がある場合、a のモジュラ逆数は、次の場合にモジュロ m の下で x になります。

a * x % m = 1

この場合、逆数は、am が互いに素である場合、つまり、am の両方の最大公約数が 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 という名前の関数があります。この関数は、am を入力として受け取り、モジュロ 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

関連記事 - Python Math

  • Python の虚数
  • Python の二項係数