快速取模指数算法：密码学的核心引擎

算法原理：指数分解的魔法

快速取模指数算法基于指数二进制分解和模运算分配律：

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

计算步骤：

1. 将指数转换为二进制形式
2. 从最低位开始遍历二进制位
3. 当前位为1时累积结果
4. 每一步对底数进行平方模运算
5. 指数位右移（除以2）

算法演示：7¹³ mod 11 计算过程

最终结果：2

Java实现

public class FastModularExponentiation {
    
    /**
     * 快速取模指数算法
     * @param base 底数
     * @param exponent 指数
     * @param modulus 模数
     * @return (base^exponent) mod modulus
     */
    public static long fastModExp(long base, long exponent, long modulus) {
        if (modulus == 1) return 0; // 任何数模1都为0
        
        long result = 1;
        base = base % modulus; // 确保base小于模数
        
        while (exponent > 0) {
            // 检查指数最低位是否为1
            if ((exponent & 1) == 1) {
                result = (result * base) % modulus;
            }
            
            // 指数右移一位（相当于除以2）
            exponent = exponent >> 1;
            
            // 底数平方后取模
            base = (base * base) % modulus;
        }
        
        return result;
    }

    public static void main(String[] args) {
        // 示例1：计算 7^13 mod 11
        long result1 = fastModExp(7, 13, 11);
        System.out.println("7^13 mod 11 = " + result1); // 输出 2
        
        // 示例2：计算 1234567^1000000 mod 10007
        long result2 = fastModExp(1234567, 1000000, 10007);
        System.out.println("1234567^1000000 mod 10007 = " + result2); // 输出 8521
        
        // 示例3：RSA解密演示
        long cipher = 1394; // 密文
        long d = 77;       // 私钥指数
        long n = 3233;     // RSA模数
        long plain = fastModExp(cipher, d, n);
        System.out.println("RSA解密: " + cipher + "^" + d + " mod " + n + " = " + plain);
    }
}

密码学应用场景

1. RSA加密/解密

• 加密：ciphertext = plaintextᵉ mod n
• 解密：plaintext = ciphertextᵈ mod n

2. Diffie-Hellman密钥交换

• 双方计算：sharedSecret = (gᵃᵇ) mod p

3. 数字签名

• 签名生成：signature = messageᵈ mod n
• 签名验证：message = signatureᵉ mod n

算法优化技巧

1. 蒙哥马利约简：消除模运算中的除法

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

2. 滑动窗口法：预处理指数位组合

   // 预处理4位组合
   long[] precomputed = new long[16];
   precomputed[0] = 1;
   for(int i=1; i<16; i++) {
       precomputed[i] = (precomputed[i-1] * base) % modulus;
   }
   

3. 并行计算：将指数拆分为多段

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

实际应用：RSA密钥生成

public class RSAKeyGenerator {
    // 快速取模指数算法实现
    // ...
    
    public static void main(String[] args) {
        // 生成大素数（实际应用需使用SecureRandom）
        long p = 61; // 第一个质数
        long q = 53; // 第二个质数
        long n = p * q; // 模数
        long phi = (p-1) * (q-1); // 欧拉函数
        
        // 选择公钥指数（通常为65537）
        long e = 17;
        
        // 计算私钥指数（模反元素）
        long d = modInverse(e, phi);
        
        // 测试加密/解密
        long message = 123;
        long cipher = fastModExp(message, e, n);
        long decrypted = fastModExp(cipher, d, n);
        
        System.out.println("原始消息: " + message);
        System.out.println("加密结果: " + cipher);
        System.out.println("解密结果: " + decrypted);
    }
    
    // 扩展欧几里得算法求模反元素
    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;
    }
}

性能基准测试（单位：纳秒）

关键洞察：当指数达到100位时（约10³⁰），普通算法需要执行10³⁰次乘法，而快速算法仅需约330步（log₂(10³⁰)≈100）