バイナリ冪乗法はどのように機能しますか？

バイナリ冪乗法（または繰り返し二乗法）は、指数をバイナリ（2進数）に変換し、各ビットを左から右へ処理します。各ビットについて、現在の結果を（モジュロで）二乗します。ビットが1の場合、底を（モジュロで）掛け合わせます。これにより、乗算回数を b-1 回から最大 2*log2(b) 回に削減します。

モジュラー冪乗計算機

バイナリべき乗法（高速べき乗法）アルゴリズムを使用して、モジュラー冪乗 a^b mod n を効率的に計算します。底、指数、法（モジュラス）を入力すると、平方剰余の繰り返し法、2進展開の可視化、暗号学的背景を含む詳細な計算過程と結果を即座に表示します。

モジュラー冪乗計算機

Embed モジュラー冪乗計算機 Widget

モジュラー冪乗計算機

モジュラー冪乗計算機は、\(a^b \bmod n\) を計算します。これは、底 \(a\) を指数 \(b\) で累乗し、法 \(n\) で割った余りを求める操作です。この電卓は、演算回数を \(O(b)\) 回の乗算からわずか \(O(\log b)\) 回に削減する バイナリ冪乗法（高速累乗法や繰り返し二乗法とも呼ばれます）を使用しています。これは、RSA、Diffie-Hellman、ElGamal などの実際の暗号実装で使用されているのと同じアルゴリズムです。

モジュラー冪乗の用途

🔐

RSA 暗号

巨大な素数の積を用いたモジュラー冪乗によるメッセージの暗号化と復号

🤝

Diffie-Hellman

安全な共有鍵を生成するための g^a mod p を計算する鍵交換プロトコル

✍

電子署名

DSA、ECDSA、EdDSA はすべてモジュラー冪乗に依存しています

🧪

素数判定

フェルマーやミラー・ラビン検定は a^(n-1) mod n を使用して素数かどうかを確認します

🏆

競技プログラミング

高速累乗を伴うモジュロ演算は、コンテストの問題において不可欠です

🔗

ブロックチェーン

プルーフ・オブ・ワークや暗号学的ハッシュ関数はモジュロ演算に依存しています

バイナリ冪乗法アルゴリズムの仕組み

重要な洞察は、任意の指数をバイナリ表現（2進数）を使用して2の累乗の和に分解できることです。例えば、\(b = 13 = 1101_2 = 2^3 + 2^2 + 2^0\) なので、\(a^{13} = a^{8} \times a^{4} \times a^{1}\) となります。

アルゴリズムは、指数のバイナリ数字を左から右へと処理します：

ステップ 1: 指数 \(b\) をバイナリに変換します。

ステップ 2: 結果（result）を 1 で初期化します（または最初のビットが 1 の場合は底で初期化）。

ステップ 3: それ以降の各ビットについて：結果を二乗（mod n）します。ビットが 1 の場合は、さらに底を 掛け合わせ（mod n）ます。

ステップ 4: すべてのビットが処理された後、その結果が \(a^b \bmod n\) です。

擬似コード

function modpow(base, exp, mod):
    result = 1
    base = base mod mod
    while exp > 0:
        if exp is odd:        // ビットが 1 の場合
            result = (result × base) mod mod
        exp = exp >> 1        // 右シフト（2で割る）
        base = (base × base) mod mod
    return result

主な公式

性質	公式	説明
モジュラー冪乗	\(a^b \bmod n\)	a^b を n で割った余り
フェルマーの小定理	\(a^{p-1} \equiv 1 \pmod{p}\)	素数 p かつ gcd(a,p)=1 の場合
オイラーの定理	\(a^{\phi(n)} \equiv 1 \pmod{n}\)	gcd(a,n)=1 の場合（φはオイラーのトーシェント関数）
バイナリ法の計算量	\(O(\log b)\) 回の乗算	最大でも 2·log₂(b) 回のモジュロ乗算
RSA 暗号化	\(c = m^e \bmod n\)	公開鍵 (e, n) でメッセージ m を暗号化
RSA 復号	\(m = c^d \bmod n\)	秘密鍵 d で暗号文 c を復号

モジュラー冪乗計算機の使い方

底 (a) を入力: 累乗したい数値を入力します。正負どちらも可能です。例えば、7^256 mod 13 を計算する場合は 7 を入力します。
指数 (b) を入力: 非負の整数である必要があります。これは累乗のパワーを表します。暗号用途では非常に大きな値になることがありますが、この電卓は 10^18 までサポートしています。
法 (n) を入力: 正の整数である必要があります。これは割り算をして余りを求めるための数値です。RSA では通常、2つの大きな素数の積になります。
計算をクリック: 電卓はバイナリ冪乗法を使用して a^b mod n を計算し、即座に結果を表示します。
アニメーションを見る: 「再生」を押すと、バイナリ冪乗法アルゴリズムがステップごとに実行される様子を確認できます。指数の各ビットが順番に処理され、アルゴリズムが「二乗」のみを行うか、「二乗して乗算」を行うかが示されます。
追跡データを確認: ステップごとの表にはすべての中間計算が表示され、効率の比較では、バイナリ冪乗法が素朴な連続乗算よりもどれだけ速いかが示されます。

なぜバイナリ冪乗法は速いのか

\(2^{1000} \bmod 13\) の計算を考えてみましょう。素朴な方法では 999 回の乗算が必要です。バイナリ冪乗法では 1000 をバイナリ（1111101000）に変換しますが、これは 10 ビットです。必要なのは最大 9 回の二乗と、ビットが「1」の場所での数回の乗算だけで、合計約 15 回の演算で済みます。これは 約 98.5% の演算削減 になります。数百桁の指数を持つ暗号規模の計算では、その差は天文学的です。バイナリ法では数千回の演算で済みますが、素朴な方法では宇宙にある原子の数よりも多くの演算が必要になってしまいます。

FAQ

モジュラー冪乗とは何ですか？

モジュラー冪乗は (a^b) mod n を計算する操作です。底を指数で累乗し、その結果を法で割った余りを求めます。これは公開鍵暗号（RSA、Diffie-Hellman、ElGamal）の核心的な操作であり、数論、競技プログラミング、コンピュータサイエンスで広く使用されています。バイナリ冪乗法により、O(log b) 回の乗算で効率的に計算できます。

バイナリ冪乗法（繰り返し二乗法）はどのように機能しますか？

バイナリ冪乗法は、指数をそのバイナリ表現に変換し、各ビットを左から右（または右から左）へ処理します。各ビットについて、現在の結果を法 n で二乗します。ビットが 1 の場合は、さらに結果に底（mod n）を掛けます。これにより、乗算回数を b−1 回（素朴な方法）から最大 2×log₂(b) 回に減らすことができ、巨大な指数でも計算が可能になります。

なぜ暗号においてモジュラー冪乗が重要なのですか？

RSA暗号では、暗号化のために c = m^e mod n、復号のために m = c^d mod n を計算します。ここで n は2つの大きな素数の積であり、指数は数百桁に及ぶことがあります。高速なモジュラー冪乗がなければ、これらの操作は計算上不可能です。安全性は、逆操作（離散対数の計算）が計算上実行不可能であると信じられていることに基づいています。

底が負の数でも大丈夫ですか？

はい、負の底も完全にサポートされています。電卓はまず底を法 n で簡約します（正の n に対して常に非負の結果を返す Python のモジュロ演算を使用）。例えば、(−3)^2 mod 7 = 9 mod 7 = 2 です。モジュロ簡約は常に [0, n−1] の範囲の値を生成するため、負の結果が出ることはありません。

法が1の場合はどうなりますか？

任意の整数を 1 で割った余りは 0 です。これは、任意の整数を 1 で割ると、その整数自身が商となり、余りが 0 になるためです。したがって、a と b のすべての値に対して a^b mod 1 = 0 となります。電卓はこれを特殊なケースとして処理します。

このコンテンツ、ページ、またはツールを引用する場合は、次のようにしてください：

"モジュラー冪乗計算機"（https://MiniWebtool.com/ja/モジュラー冪乗計算機/） MiniWebtool からの引用、https://MiniWebtool.com/

by MiniWebtool チーム. 更新日: 2026-04-16

また、AI 数学ソルバー GPT を使って、自然言語による質問と回答で数学の問題を解決することもできます。