如何進行模冪運算？
如何解決這樣的問題：
讓 $ N = 11 $ . 什麼是 $ 2^{2652557887263} \pmod N $ ?
作為問題的一部分，我們得到了乘法表[Math Processing Error] $ \mathbb{Z}_{11} $ :
x | 1 2 3 4 5 6 7 8 9 10 --------------------------------- 1 | 1 2 3 4 5 6 7 8 9 10 2 | 2 4 6 8 10 1 3 5 7 9 3 | 3 6 9 1 4 7 10 2 5 8 4 | 4 8 1 5 9 2 6 10 3 7 5 | 5 10 4 9 3 8 2 7 1 6 6 | 6 1 7 2 8 3 9 4 10 5 7 | 7 3 10 6 2 9 5 1 8 4 8 | 8 5 2 10 7 4 1 9 6 3 9 | 9 7 5 3 1 10 8 6 4 2 10|10 9 8 7 6 5 4 3 2 1…也[Math Processing Error] $ (\mathbb{Z}{11}^*,\times) $ , 的單位群[Math Processing Error] $ \mathbb{Z}{11} $ 乘法下：
exp| 0 1 2 3 4 5 6 7 8 9 10 ------------------------------------------------ g | g^0 g^1 g^2 g^3 g^4 g^5 g^6 g^7 g^8 g^9 g^10 ------------------------------------------------ 1 | 1 1 1 1 1 1 1 1 1 1 1 2 | 1 2 4 8 5 10 9 7 3 6 1 3 | 1 3 9 5 4 1 3 9 5 4 1 4 | 1 4 5 9 3 1 4 5 9 3 1 5 | 1 5 3 4 9 1 5 3 4 9 1 6 | 1 6 3 7 9 10 5 8 4 2 1 7 | 1 7 5 2 3 10 4 6 9 8 1 . | 10| 1 10 1 10 1 10 1 10 1 10 1總的來說，我很難理解表中的數字是如何生成的，以及它們是如何用來解決上述問題的。
第二個表的第二行給你的值 $ g^e\pmod{11} $ 為了 $ 0 \le e \le 10 $ . 請注意[Math Processing Error] $ 2^{10}\pmod{11} \equiv 2^{0}\pmod{11} $ . 這意味著[Math Processing Error] $ 2^{10} $ 提升到任何權力是一致的 $ 1\pmod{11} $ .
考慮到這一點，不難看出 $ 2^{2652557887263}\pmod{11} \equiv 2^3\pmod{11} $ . 所以答案是[Math Processing Error] $ 8 $ .
PS 我懷疑您的問題可能與本網站的主題無關，因此投反對票。
模冪運算由Square 和 Multiply完成。通常在每一步之後都會使用模運算。
並且您的範例中的大指數可以通過歐拉定理減少，特殊情況為[Math Processing Error] $ n $ 被費馬小定理覆蓋的素數。
有了這個，你實際上可以計算一個等價的指數[Math Processing Error] $ x $ 作為 $ x’ = x\mod \phi(n) $ . 在你的例子中 $ \phi(n) = 10 $ 你得到 $ 2652557887263 = 3 \mod 10 $
編輯：通常在處理模運算時，您實際上並沒有使用通常的整數進行計算- 我們只是使用這些整數來表示所謂的同餘類，請參閱維基百科關於模運算的章節。