モジュラ逆元計算機

整数 a の法 m における乗法逆元とは、a との積を m で割った余りが 1 になる整数 x です。合同式でいえば、a と x の積が法 m で 1 と合同になることを意味します。この計算機は拡張ユークリッド互除法で最小の非負の逆元を求め、掛け算による検算を表示します。法は一より大きい整数でなければなりません。 逆元が存在するのは、a と m が互いに素、つまり最大公約数が 1 の場合に限られます。より大きい共通因数があると、a を含む積は法 m でもその因数で割り切れるため、余りが 1 にはなりません。例えば 6 は法 15 で逆元を持ちません。最大公約数が 3 だからです。一方、3 の法 11 における逆元は 4 です。3 と 4 の積は 12 で、11 で割った余りが 1 になります。 拡張ユークリッド互除法は最大公約数を求めるだけでなく、ax と my の和が最大公約数になる係数 x と y も求めます。その公約数が 1 なら、x を法 m で剰余に直すと逆元になります。x が負の場合は m を必要な回数足すことで、合同類を変えずにゼロから m 引く一までの標準範囲に移せます。 モジュラ逆元は剰余演算で割り算の代わりになります。同じ剰余を異なる整数が表すため、剰余類に通常の割り算をそのまま適用することはできません。法 m で a で割るとは、逆元が存在する場合に a の逆元を掛けることです。この手法は一次合同式の解法、剰余における分数の簡約、中国剰余定理の適用、多くの数論アルゴリズムの導出で重要です。 暗号でもモジュラ逆元は広く使われます。RSA の鍵生成ではトーシェント関数に関連する値を法として指数の逆元を求め、楕円曲線計算では有限体上の点の公式を評価する際に逆元を使います。符号理論、チェックサム、疑似乱数生成器、数式処理も効率的な逆元計算に依存します。実際の暗号実装ではブラウザーの通常の数値演算ではなく、慎重に設計された多倍長整数演算や定数時間処理を用いますが、基礎となる数論は同じです。 逆元は法 m において一意であり、通常の整数として一つだけという意味ではありません。4 が 3 の法 11 における逆元なら、15、負の 7、および 4 と 11 の整数倍だけ異なるすべての数が同じ逆元の剰余を表します。計算機は比較や再利用がしやすい最小の非負代表元である 4 を表示します。 検算するには、元の整数に表示された逆元を掛け、法で割った余りが 1 になるか確認します。負の入力にも同じ規則が適用されます。剰余は常に標準範囲へ正規化できるためです。逆元がないと表示された場合は最大公約数を別途求めてください。1 より大きければ、存在しない理由を確認できます。