CalculatorLib
カテゴリ
数学と統計
べき乗剰余計算機
保存
計算を入力してください
このツールで前回入力した値があります。
もう一度使う
×
結果
数値を変えてもう一度計算すると、結果を並べて比較できます。
べき乗剰余の計算結果
9
7^256 mod 13
このページの誤りを報告
べき乗剰余計算機とは?
べき乗剰余計算機は \((\text{base}^{\text{exponent}}) \bmod m\) 、つまり「底をべき乗した値を法(モジュラス)で割った余り」を求めるツールです。この演算は「モジュラ指数演算(べき乗剰余)」と呼ばれ、整数論や暗号技術のいたるところで活躍します。RSA暗号、ディフィー・ヘルマン鍵交換、素数判定、ハッシュ関数などの基盤となる計算です。底を実際にべき乗してから余りを取る方法では、指数が大きいと天文学的な桁数になってしまい計算不能になるため、ここでは高速なアルゴリズムを使います。
使い方
3つの整数を入力します。底(base) 、指数(exponent、0以上) 、そして法(modulus)m(1より大きい正の整数) です。「計算」を押すと、結果が 0 から m−1 の範囲で返されます。底が負の数の場合も、自動的に正しい非負の剰余に変換されます。
計算の仕組み
本計算機は、巨大な \(\text{base}^{\text{exponent}}\) をそのまま作ることはせず、二乗・乗算法(バイナリ法、繰り返し二乗法) を用います。まず指数を2進数として読み取り、結果の初期値を1とします。そこから底を法 m のもとで繰り返し二乗していき、その時点の指数の2進桁が1のときだけ、二乗した値を結果に掛け合わせ、再び m で割った余りを取ります。途中に現れる数は常に \(m^2\) より小さく保たれるため、指数が数百桁あっても高速に計算できます。
二乗乗算法:指数のビットを走査し、各ステップで二乗してビットが1のとき乗算し、常にmで剰余を取る。
計算例
\(7^{256} \bmod 13\) を求めてみましょう。13を法とした7の位数は12の約数で、\(7^{12} \equiv 1\) が成り立ちます。\(256 = 12 \times 21 + 4\) なので、$$7^{256} \equiv 7^4 = 2401 \equiv 9 \pmod{13}$$となります。よって答えは 9 。217桁にもなる \(7^{256}\) を一度も作ることなく、瞬時に求められます。
各ステップで現在の値を二乗してmで剰余を取り、指数のビットが立っている箇所で底を掛ける。
よくある質問
法(m)が1のときは? どんな整数も1を法とすると0と合同なので、結果は0になります。
指数を0にできますか? はい。どんな底でも0乗は1なので、結果は \(1 \bmod m\)(m > 1 のときは1)になります。
そのままべき乗を計算してはいけないの? 指数が大きいと途中の数が膨大な桁数になり、オーバーフローしてしまいます。各ステップで剰余を取ることで値を小さく保ち、効率よく計算できるのです。
関連する電卓
剰余(mod)計算ツール
使いやすい剰余(mod)計算ツールで割り算の余りを簡単に求めましょう。被除数と除数を入力するだけで、正確な余りをすばやく計算できます。
べき乗計算機(指数計算)
底(基数)と指数を入力するだけで、累乗(べき乗)の答えを瞬時に算出。小数・負の数・分数指数にも対応した使いやすい指数計算ツールです。
虚数単位iのべき乗計算機
虚数単位iの任意のべき乗を計算します。指数nを入力すると、周期4の循環を使ってi^nを1・i・−1・−iのいずれかで表示。負の指数にも対応しています。
剰余計算機(a mod b)
a mod b(aをbで割ったあまり)を計算します。負の数や小数にも対応し、商と途中式(証明)をステップごとに表示します。
2のn乗計算機
2の累乗(2^n)を瞬時に計算。指数を入力するだけで正確な値が分かります。負の指数や小数の指数にも対応しています。
10のべき乗計算機
10を任意の指数で累乗した値(10^n)を無料で計算。正の指数・負の指数・小数の指数にも瞬時に対応する10のべき乗計算機です。
発見
標準正規分布のパーセント点計算
標準正規分布の下側・上側・内側(両側)累積確率(0〜1)から、パーセント点(逆累積分布/probit z値)を高精度で求めます。
正規分布グラフ計算機
正規分布(ガウス分布)の確率密度f(x)、下側累積確率P(x)、上側累積確率Q(x)を、指定したxの範囲で表として一覧表示します。
非心F分布の計算(PDF・CDF)
自由度と非心度を指定して、非心F分布の確率密度f(x)、下側累積確率P(x)、上側累積確率Q(x)を計算。表とグラフで結果を表示します。
逆数計算機
無料の逆数計算機。任意の数や分数の逆数(乗法逆元)を求めます。x の逆数は 1/x、a/b の逆数は b/a です。
フィボナッチ数列の表計算機
フィボナッチ数 F_n を指定範囲で一覧表とグラフにして表示。開始番号・増分・行数を設定するだけ。無料で使えるオンライン計算ツールです。