python - モジュラー方程式を解く (Python)

Question

Python で解決するのは簡単だと思われる問題がありますが、Python を初めて使用するため、これを解決する方法がわかりません。

私が解決しようとしているのは...

(x * e) mod k = 1 (ここでe、 とkは既知の値です)

これを行う簡単な方法はありますか？

Answer 1

独自のアルゴリズムをコーディングする代わりに、一般的な数学ライブラリgmpyを使用したい場合は、方程式を解く (つまり、剰余逆数を見つける) 関数を invert() と呼びます。現在のバージョンの gmpy (この記事の執筆時点ではバージョン 2) をインストールしたら、次のようにします。

>>> import gmpy2
>>> x = gmpy2.invert(e, k) # (Supply e and k here)

注: gmpy はネイティブの mpz (多倍精度整数) 形式で値を返しますが、値を Python コードの通常の int と同じように問題なく扱うことも、必要に応じて明示的に int にキャストすることもできます。

>>> x = int(gmpy2.invert(3, 7))

gmpy2.invert() のドキュメントは次のとおりです。

invert(x, m) -> mpz

x*y == 1 (mod m) となる y を返します。逆が存在しない場合は、ZeroDivisionError を発生させます。

このアプローチの利点は、gmpy アルゴリズムが高速であり、余分なコードを入力する必要がないことです。欠点は、サードパーティのモジュールをインポートする必要があることです。