二進位冪運算是如何運作的？

二進位冪運算（也稱為平方求冪）將指數轉換為二進位，然後由左至右處理每個位元。對於每個位元，它會對當前結果進行平方（取模）。如果位元為 1，還會乘以底數（取模）。這將乘法次數從 b-1 次減少到最多 2*log2(b) 次。

模冪運算計算機

使用二進制冪運算（快速冪）演算法高效計算模冪 a^b mod n。輸入底數、指數和模數，即可獲得即時結果，並包含平方求乘法的逐步分解、二進制分解視覺化以及密碼學背景說明。

模冪運算計算機

模冪運算計算機計算 \(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 全部依賴於模冪運算

🧪

質數測試

費馬與 Miller-Rabin 測試使用 a^(n-1) mod n 來檢查質性

🏆

程式競賽

帶有快速冪的模運算是解決競賽問題的必備知識

🔗

區塊鏈

工作量證明和加密雜湊函數都依賴於模運算

二進位冪運算法的工作原理

核心概念是我們可以利用二進位表示法，將任何指數分解為 2 的冪次之和。例如，\(b = 13 = 1101_2 = 2^3 + 2^2 + 2^0\)，因此 \(a^{13} = a^{8} \times a^{4} \times a^{1}\)。

該演算法從左到右處理指數的二進位數字：

步驟 1: 將指數 \(b\) 轉換為二進位。

步驟 2: 初始化結果 = 1（如果第一個位元為 1，則等於底數）。

步驟 3: 對於隨後的每個位元：平方結果（取模 n）。如果位元為 1，則還要乘以底數（取模 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 以計算 7^256 mod 13。
輸入指數 (b)： 這必須是非負整數。它代表冪次。對於密碼學應用，這可能非常大（本計算機支援高達 10^18）。
輸入模數 (n)： 這必須是正整數。這是用來除以並獲取餘數的數字。在 RSA 中，這通常是兩個大質數的乘積。
點擊計算： 計算機會使用二進位冪運算計算 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，它會額外將結果乘以底數取模 n。這將乘法次數從 b−1（樸素法）減少到最多 2×log₂(b)，使其能夠處理巨大的指數。

為什麼模冪運算在密碼學中很重要？

RSA 加密計算 c = m^e mod n 進行加密，以及 m = c^d mod n 進行解密，其中 n 是兩個大質數的乘積，指數可能長達數百位數字。如果沒有快速模冪運算，這些操作在計算上是不可能的。其安全性依賴於逆向操作（計算離散對數）在計算上被認為是不可行的。

底數可以是負數嗎？

是的，完全支援負數底數。計算機會先對底數取模 n（使用 Python 的模運算，對於正數 n 始終返回非負結果）。例如，(−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/zh-tw/模冪運算計算機/，來自 MiniWebtool，https://MiniWebtool.com/

由 miniwebtool 團隊製作。更新日期：2026-04-16

您還可以嘗試我們的 AI數學解題器 GPT，通過自然語言問答解決您的數學問題。

其他相關工具:

模冪運算計算機