モジュラ乗法逆元計算機

法 m における乗法逆元とは、剰余演算で掛け算を打ち消す整数です。整数 a の逆元 x は、a と x の積を m で割った余りが 1 になるという条件を満たします。通常、a と x の積は法 m で 1 と合同であると表します。例えば、3 と 4 の積は 12 で、12 を 11 で割ると余りは 1 です。したがって、4 は法 11 における 3 の乗法逆元です。 すべての整数の組に逆元が存在するわけではありません。必要十分条件は a と m が互いに素、つまり最大公約数が 1 であることです。法 9 における 6 を考えると、6 のどの倍数も 9 と公約数 3 を持つため、余りを 1 にできません。一方、7 と 26 の最大公約数は 1 であり、105 を 26 で割った余りが 1 なので、法 26 における 7 の逆元は 15 です。計算機は回答を表示する前に最大公約数を確認します。 拡張ユークリッドの互除法は逆元を効率よく求めます。通常の互除法は割り算と余りの計算を繰り返して最大公約数を求めます。拡張版では係数も追跡し、最大公約数を元の入力値の整数係数による線形結合として表します。最大公約数が 1 なら、a に掛かる係数が逆元です。この係数は負になることもあるため、計算機では法 m で剰余を取り、ゼロから m 引く一までの最小の非負代表を表示します。 モジュラ逆元を使うと、合同式で割り算に相当する操作ができます。a と x の積が法 m で b と合同となる式を解くには、逆元が存在する場合に b に a の逆元を掛けます。逆元は一次合同式、中国剰余定理、剰余演算における分数、ハッシュ、誤り検出、公開鍵暗号などで重要です。例えば RSA の鍵生成では、トーシェントを法とする指数の逆元を求めます。実際の暗号処理には、通常のブラウザー数値ではなく、厳格な監査を受けた任意精度ライブラリを使います。 整数のみを入力し、法には 1 より大きい値を指定してください。負の整数にも法 m で同値な最小非負剰余があるため、a は負でもかまいません。この計算機は JavaScript の安全な整数を使い、授業の演習や中規模の数論問題に適しています。最大公約数と積による直接の検算を表示するので、求めた逆元で本当に余りが 1 になるか確認できます。暗号で扱う非常に大きい入力には、大整数とセキュリティ上重要な計算に対応したソフトウェアを使用してください。