べき乗剰余計算機

べき乗剰余は、整数の底を非負整数の指数でべき乗し、正の法で割った余りを求める計算です。式 a^b mod m は、0 から m - 1 までの範囲で a^b と合同な唯一の余りを表します。最終的な余りが小さくても、べき乗の値は急速に巨大化するため、直接計算はすぐに非現実的になります。この計算機は、その巨大な中間整数を生成しません。 この効率的な方法は、二進法によるべき乗、繰り返し二乗法、二乗乗算法と呼ばれます。指数を二進数で表し、各ビットを処理します。まず底を m で割った余りに置き換えます。各段階で現在の因子を二乗し、m を法として剰余を取ります。対応する指数のビットが一なら、その因子を結果に掛け、すぐに再び剰余を取ります。中間値を毎回縮小するため、計算中の値は法の二乗より小さく保たれます。 必要な手順数は指数の対数に比例します。そのため、十億乗の計算でも、十億回の乗算ではなく約三十段階の二乗で済みます。表示される演算回数は、二乗と、指数の一のビットに対応する選択的な乗算を分けて数えています。指数がゼロの場合は、正しく 1 mod m を返します。 剰余演算では、余りが同じ数を同等に扱います。例えば、17 と 5 はどちらも 12 で割った余りが 5 なので、法 12 で合同です。負の底にも対応しており、最初に同等の非負剰余へ正規化します。この計算機では指数は非負である必要があります。負の指数を扱うには法に関する乗法逆元が必要であり、それが存在するのは底と法が互いに素の場合だけです。 べき乗剰余は数論と現代暗号の基本です。RSA 暗号と署名では、メッセージを大きな指数でべき乗し、合成数を法として計算します。Diffie-Hellman 鍵交換や多くの離散対数方式では、素数を法とするべき乗を使います。この演算は素数判定、疑似乱数生成器、チェックサム、周期的なパターン、競技プログラミングにも用いられます。 三つの入力欄はすべて、浮動小数点数ではなく正確な任意精度整数として処理されます。そのため、JavaScript の通常の安全な整数の上限を超えても全桁を保持できます。法は一より大きくし、カンマや小数点は入力しないでください。手作業で確かめるには、最初に底の剰余を求め、小さな指数について乗算を繰り返し、毎回余りを取ると便利です。