什麼是模冪運算
模冪運算是一種求冪次後的模的計算方法，通常用於計算 \( a^b \bmod c \)，其中 \( a \) 為底數，\( b \) 為指數，\( c \) 為模。這種計算在密碼學、數論和計算機科學中非常常見，可以有效地計算大數的冪次模值。
如何計算模冪
計算 \( a^b \bmod c \) 時，直接計算 \( a^b \) 會非常大，因此我們通常使用快速冪算法或模冪算法，逐步將計算規模縮小。下面是快速冪算法的關鍵步驟：
- 將指數 \( b \) 轉換為二進制形式。
- 初始化結果為 1。
- 從指數的最低位（右側）開始逐位計算，如果該位為 1，則更新結果，新的結果為前一個結果乘以當前的底數值並取模。
- 每次位移操作後，將底數平方並對模 \( c \) 取模，並設為新的底數。
- 重複操作，直到遍歷完指數的所有二進制位。
最終得到的結果就是 \( a^b \bmod c \)。
示例
例子 1：計算 \( 5^3 \bmod 13 \)
解答：
將指數 3 轉換為二進制，即 \( 3_{10} = 11_2 \)。
初始化：result = 1，底數 = 5，模 = 13。
遍歷二進制位（從右到左）：
- 最低位 1：更新結果：result = \( (1 \times 5) \bmod 13 = 5 \)，更新底數：\( (5 \times 5) \bmod 13 = 12 \)
- 最高位 1：更新結果：result = \( (5 \times 12) \bmod 13 = 8 \)
結果：\(5^3 \bmod 13 = 8\)。
例子 2：計算 \( 7^4 \bmod 10 \)
解答：
將指數 4 轉換為二進制，即 \( 4_{10} = 100_2 \)。
初始化：result = 1，底數 = 7，模 = 10。
遍歷二進制位（從右到左）：
- 最低位 0：不更新 result，更新底數：\( (7 \times 7) \bmod 10 = 9 \)
- 次低位 0：不更新 result，更新底數：\( (9 \times 9) \bmod 10 = 1 \)
- 最高位 1：更新結果：result = \( (1 \times 1) \bmod 10 = 1 \)
結果：\(7^4 \bmod 10 = 1\)。
例子 3：計算 \( 3^{10} \bmod 7 \)
解答：
將指數 10 轉換為二進制，即 \( 10_{10} = 1010_2 \)。
初始化：result = 1，底數 = 3，模 = 7。
遍歷二進制位（從右到左）：
- 最低位 0：不更新 result，更新底數：\( (3 \times 3) \bmod 7 = 2 \)
- 次低位 1：更新結果：result = \( (1 \times 2) \bmod 7 = 2 \)，更新底數：\( (2 \times 2) \bmod 7 = 4 \)
- 次高位 0：不更新 result，更新底數：\( (4 \times 4) \bmod 7 = 2 \)
- 最高位 1：更新結果：result = \( (2 \times 2) \bmod 7 = 4 \)
結果：\(3^{10} \bmod 7 = 4\)。