モジュラー累乗計算機 (aᵇ mod m)
暮らし
モジュラー累乗は a を b 乗し、m で割った余りを計算します — RSA や Diffie-Hellman をはじめ、多くの暗号・数論の作業の中核となる演算です。先に a^b を求めてから余りを取る方法は大きな指数では不可能なため、このツールは高速な二進累乗(二乗と乗算)を使い、各ステップで m による余りを取ります。すべての算術は任意精度の大整数で処理されるので、底・指数・法が数百桁でも結果は正確です。また、底と法が互いに素であるときは常に、底のモジュラー乗法逆元(a·x ≡ 1 を満たす x)も報告します。すべての計算はブラウザ内でローカルに行われ、何もアップロードされません。
—
a^b mod m
9
a のモジュラー逆元 (mod m)2
使い方
- 底(a)、指数(b)、法(m)を入力します。
- 非常に大きな数でも正確に計算された a^b mod m を確認します。
- 底のモジュラー逆元を確認します — gcd(a, m) = 1 のときのみ表示されます。
- a = 7、b = 256、m = 13 を入力すると 9 になります。
よくある質問
- なぜ a^b を先に求めて余りを取らないのですか?
- 大きな指数では a^b の桁数が天文学的になり、実際には作れません。二乗と乗算はすべての中間値を m² 未満に保つため、指数の大きさに関係なく高速かつ正確です。
- モジュラー逆元の行とは何ですか?
- a·x ≡ 1 (mod m) を満たす数 x です。底と法が共通因数を持たないとき(gcd = 1)のみ存在し、そうでなければ逆元が存在しないと表示されます。モジュラー算術で「割り算」をする際に使う値です。
- 指数が 0 のときは何になりますか?
- a^0 mod m は任意の底で 1 です(m = 1 のときは 0)。指数は非負の整数でなければならず、底は負でもよく、先に 0…m−1 の範囲に正規化されます。