モジュラ逆元の求め方
モジュラ逆元は、指定した法の中で乗算を元に戻します。このページは乗法逆元だけを扱い、RSA鍵生成や素因数分解は行いません。
使い方
- 負数を含む整数 a を入力します。
- 1より大きい正の法 m を入力します。
- 計算すると、存在する場合は0からm−1の範囲の一意な x が得られます。
- ベズー等式と実際の積の余りで答えを確認します。
条件と公式
逆元が存在する条件は gcd(a,m)=1 です。拡張ユークリッド互除法で a·u+m·v=1 の係数を求め、uをmで還元します。
負のaは ((a mod m)+m) mod m で正規化します。
計算例
3 mod 11
gcd(3,11)=1、3×4=12、12 mod 11=1なので逆元は4です。
−3 mod 11
−3は8に正規化され、8×7=56、56 mod 11=1なので逆元は7です。
6 mod 9
gcd(6,9)=3なので逆元はありません。
入力制限と範囲
- 各入力は10進200桁までです。先頭の0も入力桁数に含みます。
- 小数、指数表記、単位、数字内の空白、Infinityは使用できません。
- 法0、1、負数は無効です。a=0は入力できますが、m>1では逆元がありません。
- 結果は正確な整数です。暗号鍵生成やセキュリティサービスではありません。
よくある質問
最大公約数が1である必要は？
1より大きい共通因数はすべての積a×xを割るため、余り1にはできません。
負数にも逆元はある？
あります。まず最小の非負剰余に直して判定します。
答えが1つだけなのは？
すべての逆元はmの倍数だけ違うため、0からm−1の一意な値を表示します。
1/aと同じ？
違います。指定した法で積の余りが1になる整数です。