每日算法 — 使用java实现快速幂：二进制分解与模运算加速

引言

快速幂（Exponentiation by Squaring）又称”平方求幂”，是将 O(n) 复杂度的幂运算优化为 O(log n) 的经典算法。其核心思想简单而优雅：利用指数的二进制表示，将幂运算拆解为一系列平方与乘法操作。该算法不仅本身极具教学价值，更是密码学（如 RSA）、组合数学、动态规划优化中的基础工具。

本文将用 Java 从零实现快速幂算法，从基础递归版、迭代优化版、矩阵快速幂到工程应用，完整呈现这一算法的设计与实现。

问题引入

计算 a^n 最直观的方法是连乘 n 次：

public static long powerNaive(long a, long n) {
    long result = 1;
    for (int i = 0; i < n; i++) {
        result *= a;
    }
    return result;
}

对于 n = 10^9 这种规模，需要数十亿次乘法，性能与数值范围均不可接受。快速幂将时间复杂度降低到 O(log n)，对 n = 10^9 仅需约 30 次操作。

核心思想：二进制分解

任何正整数 n 都可以唯一表示为二进制：

n = b_k × 2^k + b_{k-1} × 2^{k-1} + ... + b_1 × 2 + b_0

其中 b_i ∈ {0, 1}。由此：

a^n = a^(b_k × 2^k) × a^(b_{k-1} × 2^{k-1}) × ... × a^(b_0)
    = ∏ (a^(2^i))^(b_i)

只需要从 a^1 开始，逐步平方得到 a^2, a^4, a^8, …, a^(2^k)，再按二进制位累积结果。

递归实现

package com.algorithm.fastpower;

/**
 * 快速幂基础实现
 * 通过分治思想：a^n = (a^(n/2))^2 × (n 为奇数时再乘 a)
 */
public class FastPower {

    /**
     * 递归版快速幂：O(log n) 时间复杂度
     * @param a 底数
     * @param n 指数（非负整数）
     * @return a^n
     */
    public static long powerRecursive(long a, long n) {
        if (n < 0) throw new IllegalArgumentException("指数必须非负");
        if (n == 0) return 1;
        if (n == 1) return a;

        long half = powerRecursive(a, n / 2);
        long result = half * half;
        if (n % 2 == 1) {
            result *= a;
        }
        return result;
    }

    /**
     * 迭代版快速幂：避免递归栈开销
     * 通过遍历 n 的二进制位来累积结果
     */
    public static long powerIterative(long a, long n) {
        if (n < 0) throw new IllegalArgumentException("指数必须非负");
        if (n == 0) return 1;

        long result = 1;
        long base = a;
        long exp = n;

        while (exp > 0) {
            if ((exp & 1) == 1) {
                result *= base;
            }
            base *= base;
            exp >>= 1;
        }
        return result;
    }

    /**
     * 大整数快速幂（使用 BigInteger）
     * 适用于超出 long 范围的场景
     */
    public static java.math.BigInteger powerBigInteger(
            java.math.BigInteger a, long n) {
        if (n < 0) throw new IllegalArgumentException("指数必须非负");
        java.math.BigInteger result = java.math.BigInteger.ONE;
        java.math.BigInteger base = a;
        long exp = n;

        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = result.multiply(base);
            }
            base = base.multiply(base);
            exp >>= 1;
        }
        return result;
    }
}

模幂运算

计算 a^n mod m 是密码学的基础操作。如果先计算 a^n 再取模，数值会爆炸。必须将取模嵌入到每次乘法中。

package com.algorithm.fastpower;

import java.math.BigInteger;

/**
 * 模幂运算：a^n mod m
 * 关键技巧：每步乘法后立即取模，避免数值爆炸
 */
public class ModularPower {

    /**
     * 基础模幂：long 范围
     */
    public static long modPower(long a, long n, long m) {
        if (m == 1) return 0;
        if (n < 0) throw new IllegalArgumentException("指数必须非负");

        long result = 1;
        a = ((a % m) + m) % m;  // 处理负数底数
        long base = a;
        long exp = n;

        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = (result * base) % m;
            }
            base = (base * base) % m;
            exp >>= 1;
        }
        return result;
    }

    /**
     * 大整数模幂
     * BigInteger 的 modPow 已内部优化，但理解原理重要
     */
    public static BigInteger modPowerBig(BigInteger a, BigInteger n, BigInteger m) {
        if (m.signum() <= 0) throw new IllegalArgumentException("模数必须为正");
        if (n.signum() < 0) throw new IllegalArgumentException("指数必须非负");

        BigInteger result = BigInteger.ONE;
        BigInteger base = a.mod(m);
        int bitLength = n.bitLength();

        for (int i = 0; i < bitLength; i++) {
            if (n.testBit(i)) {
                result = result.multiply(base).mod(m);
            }
            base = base.multiply(base).mod(m);
        }
        return result;
    }

    /**
     * 蒙哥马利模幂：进一步优化大整数模运算
     * 核心思想：将普通乘法转换为蒙哥马利乘法，避开昂贵的除法
     */
    public static BigInteger montgomeryPower(BigInteger a, BigInteger n, BigInteger m) {
        if (m.signum() <= 0) throw new IllegalArgumentException("模数必须为正");

        // 蒙哥马利参数 R = 2^k > m
        int k = (m.bitLength() + 7) / 8 * 8 + 8;
        BigInteger R = BigInteger.ONE.shiftLeft(k);
        BigInteger Rinv = R.modInverse(m);
        BigInteger mNegInv = R.subtract(m.modInverse(R)).mod(R);

        // 转换 a 到蒙哥马利域
        BigInteger aMont = a.multiply(R).mod(m);
        BigInteger resultMont = R.mod(m);

        int bitLength = n.bitLength();
        for (int i = bitLength - 1; i >= 0; i--) {
            // result = result^2
            resultMont = montgomeryMul(resultMont, resultMont, m, R, mNegInv);
            if (n.testBit(i)) {
                resultMont = montgomeryMul(resultMont, aMont, m, R, mNegInv);
            }
        }

        // 转换回普通域
        return montgomeryMul(resultMont, BigInteger.ONE, m, R, mNegInv);
    }

    private static BigInteger montgomeryMul(BigInteger x, BigInteger y, 
                                              BigInteger m, BigInteger R, 
                                              BigInteger mNegInv) {
        BigInteger t = x.multiply(y);
        BigInteger u = t.multiply(mNegInv).and(R.subtract(BigInteger.ONE));
        BigInteger candidate = t.add(u.multiply(m)).shiftRight(R.bitLength() - 1);
        if (candidate.compareTo(m) >= 0) {
            candidate = candidate.subtract(m);
        }
        return candidate;
    }
}

矩阵快速幂

矩阵快速幂将快速幂思想扩展到矩阵乘法，用于加速递推关系（如斐波那契数列）。

package com.algorithm.fastpower;

import java.util.Arrays;

/**
 * 矩阵快速幂
 * 应用场景：递推关系加速，如斐波那契数列从 O(n) 优化到 O(log n)
 */
public class MatrixPower {

    /**
     * 2x2 矩阵乘法
     */
    public static long[][] multiply(long[][] a, long[][] b, long mod) {
        int n = a.length;
        long[][] result = new long[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                long sum = 0;
                for (int k = 0; k < n; k++) {
                    sum = (sum + a[i][k] * b[k][j]) % mod;
                }
                result[i][j] = sum;
            }
        }
        return result;
    }

    /**
     * 矩阵快速幂
     */
    public static long[][] matrixPower(long[][] base, long n, long mod) {
        int size = base.length;
        // 初始化为单位矩阵
        long[][] result = new long[size][size];
        for (int i = 0; i < size; i++) result[i][i] = 1;

        long[][] cur = base;
        long exp = n;

        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = multiply(result, cur, mod);
            }
            cur = multiply(cur, cur, mod);
            exp >>= 1;
        }
        return result;
    }

    /**
     * 应用 1：斐波那契数列 F(n) = F(n-1) + F(n-2)
     * 转移矩阵：[F(n)  ]   [1 1] [F(n-1)]
     *           [F(n-1)] = [1 0] [F(n-2)]
     */
    public static long fibonacci(long n, long mod) {
        if (n == 0) return 0;
        if (n == 1) return 1;

        long[][] base = {{1, 1}, {1, 0}};
        long[][] result = matrixPower(base, n - 1, mod);
        return result[0][0];  // F(n) = result[0][0]
    }

    /**
     * 应用 2：线性递推 a(n) = 2*a(n-1) + 3*a(n-2) + 5*a(n-3)
     * 转移矩阵为 3x3
     */
    public static long linearRecurrence(long n, long mod) {
        if (n == 0) return 1;  // 初始值 a(0)
        if (n == 1) return 2;
        if (n == 2) return 3;

        long[][] base = {
            {2, 3, 5},
            {1, 0, 0},
            {0, 1, 0}
        };
        long[][] result = matrixPower(base, n - 1, mod);
        return result[0][0];
    }
}

应用案例

案例 1：斐波那契数列

package com.algorithm.fastpower;

import java.math.BigInteger;

/**
 * 斐波那契数列：递归与矩阵快速幂对比
 */
public class Fibonacci {

    public static void main(String[] args) {
        long n = 1000000000000L;  // 10^12

        // 矩阵快速幂：O(log n)
        long mod = 1_000_000_007L;
        long result = MatrixPower.fibonacci(n, mod);
        System.out.println("F(" + n + ") mod 10^9+7 = " + result);

        // 大整数场景
        BigInteger bigResult = fibonacciBig(BigInteger.valueOf(n));
        System.out.println("F(" + n + ") = " + bigResult.toString().substring(0, 50) + "...");
    }

    /**
     * 大整数斐波那契（无取模）
     */
    public static BigInteger fibonacciBig(BigInteger n) {
        if (n.equals(BigInteger.ZERO)) return BigInteger.ZERO;
        if (n.equals(BigInteger.ONE)) return BigInteger.ONE;

        BigInteger[][] base = {
            {BigInteger.ONE, BigInteger.ONE},
            {BigInteger.ONE, BigInteger.ZERO}
        };
        BigInteger[][] result = matrixPowerBig(base, n.subtract(BigInteger.ONE));
        return result[0][0];
    }

    private static BigInteger[][] matrixPowerBig(BigInteger[][] base, BigInteger n) {
        int size = base.length;
        BigInteger[][] result = new BigInteger[size][size];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                result[i][j] = (i == j) ? BigInteger.ONE : BigInteger.ZERO;
            }
        }

        BigInteger[][] cur = new BigInteger[size][size];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                cur[i][j] = base[i][j];
            }
        }

        BigInteger exp = n;
        while (exp.signum() > 0) {
            if (exp.testBit(0)) {
                result = multiplyBig(result, cur);
            }
            cur = multiplyBig(cur, cur);
            exp = exp.shiftRight(1);
        }
        return result;
    }

    private static BigInteger[][] multiplyBig(BigInteger[][] a, BigInteger[][] b) {
        int n = a.length;
        BigInteger[][] result = new BigInteger[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                BigInteger sum = BigInteger.ZERO;
                for (int k = 0; k < n; k++) {
                    sum = sum.add(a[i][k].multiply(b[k][j]));
                }
                result[i][j] = sum;
            }
        }
        return result;
    }
}

案例 2：RSA 加密核心

package com.algorithm.fastpower;

import java.math.BigInteger;
import java.security.SecureRandom;

/**
 * 简化版 RSA 加密演示
 * 核心：使用快速模幂实现加密/解密
 */
public class SimpleRSA {
    private final BigInteger n, e, d;

    public SimpleRSA(int keySize) {
        SecureRandom random = new SecureRandom();
        BigInteger p = BigInteger.probablePrime(keySize / 2, random);
        BigInteger q = BigInteger.probablePrime(keySize / 2, random);
        n = p.multiply(q);
        BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
        e = BigInteger.valueOf(65537);
        d = e.modInverse(phi);
    }

    /**
     * 加密：c = m^e mod n（快速模幂）
     */
    public BigInteger encrypt(BigInteger message) {
        return ModularPower.modPowerBig(message, e, n);
    }

    /**
     * 解密：m = c^d mod n（快速模幂）
     */
    public BigInteger decrypt(BigInteger ciphertext) {
        return ModularPower.modPowerBig(ciphertext, d, n);
    }

    public static void main(String[] args) {
        SimpleRSA rsa = new SimpleRSA(1024);
        BigInteger message = BigInteger.valueOf(123456789);

        long start = System.nanoTime();
        BigInteger cipher = rsa.encrypt(message);
        long encTime = (System.nanoTime() - start) / 1000;

        start = System.nanoTime();
        BigInteger decrypted = rsa.decrypt(cipher);
        long decTime = (System.nanoTime() - start) / 1000;

        System.out.println("原文: " + message);
        System.out.println("密文: " + cipher);
        System.out.println("解密: " + decrypted);
        System.out.println("加密耗时: " + encTime + " μs");
        System.out.println("解密耗时: " + decTime + " μs");
    }
}

案例 3：模逆元求解

费马小定理：当模数 m 是素数时，a 的模逆元 = a^(m-2) mod m。

package com.algorithm.fastpower;

import java.math.BigInteger;

/**
 * 模逆元的快速幂求解
 */
public class ModularInverse {

    /**
     * 费马小定理求逆元（要求 m 是素数）
     * a^(-1) ≡ a^(m-2) (mod m)
     */
    public static long inverseByPower(long a, long prime) {
        return ModularPower.modPower(a, prime - 2, prime);
    }

    public static BigInteger inverseByPowerBig(BigInteger a, BigInteger prime) {
        return ModularPower.modPowerBig(a, prime.subtract(BigInteger.TWO), prime);
    }

    public static void main(String[] args) {
        long a = 3, m = 7;
        long inv = inverseByPower(a, m);
        System.out.println(a + "^(-1) mod " + m + " = " + inv);
        System.out.println("验证: " + a + " × " + inv + " mod " + m + " = " + 
                          (a * inv) % m);
    }
}

性能基准

package com.algorithm.fastpower;

/**
 * 快速幂 vs 朴素幂运算性能对比
 */
public class PerformanceBenchmark {

    public static void main(String[] args) {
        // 测试 1：long 范围
        int[] exponents = {10, 100, 1_000, 1_000_000, 1_000_000_000};
        long base = 2;

        System.out.println("=== long 范围性能测试 ===");
        System.out.printf("%-12s %-15s %-15s %-10s%n", "指数 n", "朴素 (ms)", "快速幂 (ms)", "加速比");

        for (int n : exponents) {
            if (n > 62) break;  // 避免溢出

            long start = System.nanoTime();
            long r1 = powerNaive(base, n);
            long t1 = (System.nanoTime() - start) / 1_000_000;

            start = System.nanoTime();
            long r2 = FastPower.powerIterative(base, n);
            long t2 = (System.nanoTime() - start) / 1_000_000;

            System.out.printf("%-12d %-15d %-15d %-10.0f%n", n, t1, t2, 
                              t1 > 0 ? (double) t1 / Math.max(t2, 1) : 0);
        }

        // 测试 2：斐波那契
        System.out.println("\n=== 斐波那契性能测试 ===");
        long[] fibs = {1_000L, 100_000L, 1_000_000_000L, 1_000_000_000_000L};
        long mod = 1_000_000_007L;

        for (long n : fibs) {
            long start = System.nanoTime();
            long fib = MatrixPower.fibonacci(n, mod);
            long time = (System.nanoTime() - start) / 1_000_000;
            System.out.printf("F(%d) mod 10^9+7 = %d, 耗时 %d ms%n", n, fib, time);
        }
    }

    private static long powerNaive(long a, int n) {
        long result = 1;
        for (int i = 0; i < n; i++) result *= a;
        return result;
    }
}

复杂度分析

其中 M(k) 是 k 位数乘法的复杂度（k 位快速傅里叶变换可达 O(k log k)）。

工程实践要点

1. 处理负指数：a^(-n) = 1/a^n，非整数场景下不适用
2. 取模时机：每步乘法后立即取模，避免数值爆炸
3. 溢出防护：使用 BigInteger 处理大整数场景
4. 缓存结果：相同 (a, n) 组合的重复计算可缓存
5. SIMD 加速：现代 CPU 可并行多个模幂运算

扩展话题

快速乘

将 64 位整数乘法分解为多个 32 位乘法和加法，避免溢出。Karatsuba 进一步优化到 O(k^1.585)。

蒙哥马利乘法

避免昂贵的除法运算，将模运算转化为移位与加法。RSA 等密码学库普遍使用。

滑动窗口算法

通过预计算小幅度的幂（如 1, 2, 4, 8…）减少乘法次数。窗口大小通常为 4-7。

预计算与查表

对于固定底数（如 2 的幂），可预计算所有结果并查表，O(1) 返回。

应用场景

• RSA、Diffie-Hellman、ElGamal：公钥密码学
• 离散对数：Pollard Rho 等算法
• 斐波那契、组合数学：递推关系
• 概率算法：Miller-Rabin 素性测试
• 图论：邻接矩阵幂计算路径数
• 机器学习：Softmax 等指数运算
• 数值计算：矩阵指数 e^A

总结

快速幂是分治思想在数值计算中的经典应用。短短几行代码即可将 O(n) 优化为 O(log n)，其影响远超算法本身——它支撑着现代密码学与高性能计算的核心。掌握快速幂不仅能解决”求幂”问题，更能体会到分治、递推、二进制表示这些基础思想在工程中的强大威力。

参考资料

1. Knuth, D. E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley.
2. Menezes, A. J., et al. (1996). Handbook of Applied Cryptography. CRC Press.
3. Montgomery, P. L. (1985). Modular multiplication without trial division. Mathematics of Computation.
4. Crandall, R., & Pomerance, C. (2005). Prime Numbers: A Computational Perspective. Springer.