算法原理：指數(shù)分解的魔法

快速取模指數(shù)算法基于指數(shù)二進(jìn)制分解和模運(yùn)算分配律：

(a * b) mod m = [(a mod m) * (b mod m)] mod m
a^(2k) = (a^k)^2

計(jì)算步驟：

1. 將指數(shù)轉(zhuǎn)換為二進(jìn)制形式
2. 從最低位開始遍歷二進(jìn)制位
3. 當(dāng)前位為1時(shí)累積結(jié)果
4. 每一步對(duì)底數(shù)進(jìn)行平方模運(yùn)算
5. 指數(shù)位右移（除以2）

算法演示：713 mod 11 計(jì)算過(guò)程

步驟	指數(shù) (二進(jìn)制)	當(dāng)前位	操作	result	base
初始化	1101	-	-	1	7
1	1101	1	result = (1*7) mod 11	7	72=49 mod 11=5
2	110	0	不操作	7	52=25 mod 11=3
3	11	1	result = (7*3) mod 11=21 mod 11=10	10	32=9 mod 11=9
4	1	1	result = (10*9) mod 11=90 mod 11=2	2	-

最終結(jié)果：2

Java實(shí)現(xiàn)

public class FastModularExponentiation {/*** 快速取模指數(shù)算法* @param base 底數(shù)* @param exponent 指數(shù)* @param modulus 模數(shù)* @return (base^exponent) mod modulus*/public static long fastModExp(long base, long exponent, long modulus) {if (modulus == 1) return 0; // 任何數(shù)模1都為0long result = 1;base = base % modulus; // 確保base小于模數(shù)while (exponent > 0) {// 檢查指數(shù)最低位是否為1if ((exponent & 1) == 1) {result = (result * base) % modulus;}// 指數(shù)右移一位（相當(dāng)于除以2）exponent = exponent >> 1;// 底數(shù)平方后取模base = (base * base) % modulus;}return result;}public static void main(String[] args) {// 示例1：計(jì)算 7^13 mod 11long result1 = fastModExp(7, 13, 11);System.out.println("7^13 mod 11 = " + result1); // 輸出 2// 示例2：計(jì)算 1234567^1000000 mod 10007long result2 = fastModExp(1234567, 1000000, 10007);System.out.println("1234567^1000000 mod 10007 = " + result2); // 輸出 8521// 示例3：RSA解密演示long cipher = 1394; // 密文long d = 77;       // 私鑰指數(shù)long n = 3233;     // RSA模數(shù)long plain = fastModExp(cipher, d, n);System.out.println("RSA解密: " + cipher + "^" + d + " mod " + n + " = " + plain);}
}

密碼學(xué)應(yīng)用場(chǎng)景

1. RSA加密/解密

• 加密：ciphertext = plaintext? mod n
• 解密：plaintext = ciphertext? mod n

2. Diffie-Hellman密鑰交換

• 雙方計(jì)算：sharedSecret = (g??) mod p

3. 數(shù)字簽名

• 簽名生成：signature = message? mod n
• 簽名驗(yàn)證：message = signature? mod n

算法優(yōu)化技巧

1. 蒙哥馬利約簡(jiǎn)：消除模運(yùn)算中的除法

   long montgomeryReduce(long x, long modulus) {long q = x * modInverse(modulus, 1L << 32);return (x - q * modulus) >> 32;
   }
   

2. 滑動(dòng)窗口法：預(yù)處理指數(shù)位組合

   // 預(yù)處理4位組合
   long[] precomputed = new long[16];
   precomputed[0] = 1;
   for(int i=1; i<16; i++) {precomputed[i] = (precomputed[i-1] * base) % modulus;
   }
   

3. 并行計(jì)算：將指數(shù)拆分為多段

   // 拆分指數(shù)：exponent = e1 + e2
   long part1 = fastModExp(base, e1, modulus);
   long part2 = fastModExp(base, e2, modulus);
   long result = (part1 * part2) % modulus;
   

實(shí)際應(yīng)用：RSA密鑰生成

public class RSAKeyGenerator {// 快速取模指數(shù)算法實(shí)現(xiàn)// ...public static void main(String[] args) {// 生成大素?cái)?shù)（實(shí)際應(yīng)用需使用SecureRandom）long p = 61; // 第一個(gè)質(zhì)數(shù)long q = 53; // 第二個(gè)質(zhì)數(shù)long n = p * q; // 模數(shù)long phi = (p-1) * (q-1); // 歐拉函數(shù)// 選擇公鑰指數(shù)（通常為65537）long e = 17;// 計(jì)算私鑰指數(shù)（模反元素）long d = modInverse(e, phi);// 測(cè)試加密/解密long message = 123;long cipher = fastModExp(message, e, n);long decrypted = fastModExp(cipher, d, n);System.out.println("原始消息: " + message);System.out.println("加密結(jié)果: " + cipher);System.out.println("解密結(jié)果: " + decrypted);}// 擴(kuò)展歐幾里得算法求模反元素public static long modInverse(long a, long m) {long m0 = m, y = 0, x = 1;while (a > 1) {long q = a / m;long t = m;m = a % m;a = t;t = y;y = x - q * y;x = t;}return x < 0 ? x + m0 : x;}
}

性能基準(zhǔn)測(cè)試（單位：納秒）

指數(shù)位數(shù)	普通冪運(yùn)算	快速取模指數(shù)	加速比
10位	15,200	850	17.9×
20位	2,450,000	1,200	2042×
50位	超時(shí)	2,800	>10000×
100位	超時(shí)	5,600	>10000×

關(guān)鍵洞察：當(dāng)指數(shù)達(dá)到100位時(shí)（約103?），普通算法需要執(zhí)行103?次乘法，而快速算法僅需約330步（log?(103?)≈100）