模冪運算計算機
使用二進制冪運算(快速冪)演算法高效計算模冪 a^b mod n。輸入底數、指數和模數,即可獲得即時結果,並包含平方求乘法的逐步分解、二進制分解視覺化以及密碼學背景說明。
偵測到廣告封鎖,導致我們無法顯示廣告
MiniWebtool 依靠廣告收入免費提供服務。如果這個工具幫到你,歡迎升級 Premium(無廣告 + 更快),或將 MiniWebtool.com 加入允許清單後重新整理頁面。
- 或升級 Premium(無廣告)
- 允許 MiniWebtool.com 顯示廣告,然後重新載入
模冪運算計算機
模冪運算計算機計算 \(a^b \bmod n\) — 將底數 \(a\) 提高到指數 \(b\) 的冪次,並取除以模數 \(n\) 後的餘數。它使用二進位冪運算法(也稱為快速冪或平方求冪),將運算從 \(O(b)\) 次乘法減少到僅 \(O(\log b)\) 次。這與 RSA、Diffie-Hellman 和 ElGamal 等實際密碼學實作中所使用的演算法相同。
模冪運算的應用
二進位冪運算法的工作原理
核心概念是我們可以利用二進位表示法,將任何指數分解為 2 的冪次之和。例如,\(b = 13 = 1101_2 = 2^3 + 2^2 + 2^0\),因此 \(a^{13} = a^{8} \times a^{4} \times a^{1}\)。
該演算法從左到右處理指數的二進位數字:
虛擬碼
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)
引用此內容、頁面或工具為:
"模冪運算計算機" 於 https://MiniWebtool.com/zh-tw//,來自 MiniWebtool,https://MiniWebtool.com/
由 miniwebtool 團隊製作。更新日期:2026-04-16
您還可以嘗試我們的 AI數學解題器 GPT,通過自然語言問答解決您的數學問題。