每日算法 — 使用java实现费马小定理：快速幂模运算与素性测试

问题描述

费马小定理（Fermat’s Little Theorem）是数论中最基础且应用最广泛的定理之一，由法国数学家皮埃尔·德·费马于1640年提出。该定理陈述如下：

若 p 是素数，且整数 a 不是 p 的倍数（即 gcd(a, p) = 1），则 a^(p-1) ≡ 1 (mod p)。

这一定理在现代密码学（如RSA算法）、素性测试、模运算加速等领域有着核心地位。本文将用Java实现基于费马小定理的两大应用：快速幂模运算（也称模幂运算或二进制幂）和费马素性测试，并深入剖析其背后的数学原理与工程实现细节。

算法思路

1. 快速幂模运算（Binary Exponentiation）

直接计算 a^b mod m 在指数 b 很大时（如RSA中常见的1024位或2048位指数）会导致中间结果溢出且效率低下。快速幂算法利用指数的二进制表示，将时间复杂度从 O(b) 降到 O(log b)。

核心思想：将指数 b 分解为二进制形式。例如 b = 13 = 1101₂ = 8 + 4 + 1，则：

a^13 = a^8 × a^4 × a^1

在迭代过程中，不断将底数平方，并根据当前二进制位的值决定是否乘入结果。

2. 费马素性测试（Fermat Primality Test）

费马小定理的逆否命题给出了一个判断合数的有效方法：

若存在 a（1 < a < p），使得 a^(p-1) ≢ 1 (mod p)，则 p 一定是合数。

满足 a^(p-1) ≡ 1 (mod p) 的合数 p 称为以 a 为底的费马伪素数。为降低误判率，通常随机选取多个不同的底数 a 进行测试。若 p 通过了 k 次测试，则其为合数的概率不超过 1/2^k。

需要注意的是，存在一类特殊的合数——卡迈克尔数（Carmichael Number），它们能通过所有与自身互质的底数的费马测试。最小的卡迈克尔数是561 = 3 × 11 × 17。对于高可靠性场景，应使用Miller-Rabin素性测试替代。

3. 模逆元计算

由费马小定理，当 p 为素数时，a^(p-2) ≡ a^(-1) (mod p)。这意味着快速幂可以直接用于计算模逆元，在分数取模、组合数取模等问题中极为实用。

Java代码实现

import java.math.BigInteger;
import java.security.SecureRandom;
import java.util.ArrayList;
import java.util.List;

/**
 * 费马小定理应用：快速幂模运算、素性测试与模逆元
 */
public class FermatLittleTheorem {

    private static final SecureRandom RANDOM = new SecureRandom();

    /**
     * 快速幂模运算：计算 (base^exponent) % mod
     * 时间复杂度：O(log exponent)
     * 空间复杂度：O(1)
     *
     * @param base     底数
     * @param exponent 指数（非负）
     * @param mod      模数（正数）
     * @return base^exponent mod mod
     */
    public static long modPow(long base, long exponent, long mod) {
        if (mod == 1) return 0;
        if (exponent < 0) {
            throw new IllegalArgumentException("指数必须为非负数，如需负指数请使用模逆元");
        }

        long result = 1;
        long b = ((base % mod) + mod) % mod; // 处理负数底数
        long e = exponent;

        while (e > 0) {
            // 如果当前二进制位为1，将底数乘入结果
            if ((e & 1) == 1) {
                result = mulMod(result, b, mod);
            }
            // 底数平方，准备处理下一位
            b = mulMod(b, b, mod);
            e >>= 1; // 右移一位
        }

        return result;
    }

    /**
     * 安全的模乘法，防止long溢出
     * 使用BigInteger作为备选方案，或使用二进制拆分法
     */
    private static long mulMod(long a, long b, long mod) {
        // 如果不会溢出，直接计算
        if (a == 0 || b == 0) return 0;
        if (a <= Long.MAX_VALUE / b) {
            return (a * b) % mod;
        }
        // 大数时使用BigInteger
        return BigInteger.valueOf(a)
                .multiply(BigInteger.valueOf(b))
                .mod(BigInteger.valueOf(mod))
                .longValue();
    }

    /**
     * 基于费马小定理的素性测试（单次测试）
     *
     * @param n 待测试的数（n > 2）
     * @param a 测试底数（1 < a < n）
     * @return true表示n可能是素数，false表示n一定是合数
     */
    public static boolean fermatTest(long n, long a) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 == 0) return false;

        // 计算 a^(n-1) mod n
        long result = modPow(a, n - 1, n);
        return result == 1;
    }

    /**
     * 基于费马小定理的概率素性测试（多次迭代）
     *
     * @param n           待测试的数
     * @param iterations  测试轮数（建议10-20轮）
     * @return true表示n极可能是素数
     */
    public static boolean isProbablePrime(long n, int iterations) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 == 0) return n == 2;

        // 小素数快速筛查
        int[] smallPrimes = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
        for (int p : smallPrimes) {
            if (n == p) return true;
            if (n % p == 0) return false;
        }

        // 多次随机底数测试
        for (int i = 0; i < iterations; i++) {
            long a = randomInRange(2, n - 2);
            if (!fermatTest(n, a)) {
                return false; // 确定是合数
            }
        }

        return true; // 极可能是素数
    }

    /**
     * 计算模逆元：a^(-1) mod p
     * 基于费马小定理：当p为素数时，a^(-1) ≡ a^(p-2) (mod p)
     *
     * @param a 待求逆元的数
     * @param p 素数模数
     * @return a的模逆元
     */
    public static long modInverse(long a, long p) {
        if (a % p == 0) {
            throw new IllegalArgumentException("a必须是p的倍数之外");
        }
        long inv = modPow(((a % p) + p) % p, p - 2, p);
        // 验证
        if (mulMod(a, inv, p) != 1) {
            throw new ArithmeticException("模逆元不存在，请确认p为素数且a与p互质");
        }
        return inv;
    }

    /**
     * 计算组合数 C(n, k) mod p（p为素数）
     * 利用模逆元将除法转化为乘法
     */
    public static long nCrModPrime(long n, long k, long p) {
        if (k < 0 || k > n) return 0;
        if (k == 0 || k == n) return 1;

        // 分子：n * (n-1) * ... * (n-k+1)
        long numerator = 1;
        for (long i = 0; i < k; i++) {
            numerator = mulMod(numerator, (n - i) % p, p);
        }

        // 分母：k!，通过模逆元转化为乘法
        long denominator = 1;
        for (long i = 1; i <= k; i++) {
            denominator = mulMod(denominator, modInverse(i % p, p), p);
        }

        return mulMod(numerator, denominator, p);
    }

    /**
     * 生成指定范围内的随机整数 [min, max]
     */
    private static long randomInRange(long min, long max) {
        if (min > max) throw new IllegalArgumentException("min必须<=max");
        long range = max - min + 1;
        long random = Math.abs(RANDOM.nextLong()) % range;
        return min + random;
    }

    /**
     * 生成指定位数的大素数（基于费马测试）
     */
    public static BigInteger generateLargePrime(int bitLength, int certainty) {
        return BigInteger.probablePrime(bitLength, RANDOM);
    }

    // ==================== 主程序入口 ====================
    public static void main(String[] args) {
        System.out.println("===== 费马小定理应用演示 =====\n");

        // 演示1：快速幂模运算
        System.out.println("--- 1. 快速幂模运算 ---");
        long base = 7;
        long exp = 13;
        long mod = 100;
        System.out.printf("%d^%d mod %d = %d%n", base, exp, mod, modPow(base, exp, mod));
        System.out.printf("验证：Math.pow(7,13) mod 100 = %.0f%n", Math.pow(7, 13) % 100);

        System.out.println();

        // 大数测试
        System.out.println("--- 2. 大数快速幂 ---");
        long bigBase = 123456789;
        long bigExp = 987654321;
        long bigMod = 1000000007;
        long result = modPow(bigBase, bigExp, bigMod);
        System.out.printf("%d^%d mod %d = %d%n", bigBase, bigExp, bigMod, result);

        System.out.println();

        // 演示3：费马素性测试
        System.out.println("--- 3. 费马素性测试 ---");
        long[] testNumbers = {2, 17, 25, 97, 100, 561, 104729, 1000003};
        for (long num : testNumbers) {
            boolean isPrime = isProbablePrime(num, 10);
            System.out.printf("%d 可能是素数: %b%n", num, isPrime);
        }
        System.out.println("（注意：561是卡迈克尔数，费马测试可能误判为素数）");

        System.out.println();

        // 演示4：模逆元
        System.out.println("--- 4. 模逆元计算 ---");
        long a = 7;
        long p = 13;
        long inv = modInverse(a, p);
        System.out.printf("%d^(-1) mod %d = %d%n", a, p, inv);
        System.out.printf("验证：%d * %d mod %d = %d%n", a, inv, p, (a * inv) % p);

        System.out.println();

        // 演示5：组合数取模
        System.out.println("--- 5. 组合数取模 C(10, 3) mod 13 ---");
        long nCr = nCrModPrime(10, 3, 13);
        System.out.printf("C(10, 3) mod 13 = %d%n", nCr);
        System.out.printf("验证：10!/(3!*7!) = %d%n", 10 * 9 * 8 / (3 * 2 * 1));

        System.out.println();

        // 演示6：性能对比
        System.out.println("--- 6. 性能对比：快速幂 vs 朴素幂 ---");
        long testExp = 1000000000000L;
        long testMod = 1000000007;

        long start1 = System.nanoTime();
        long fastResult = modPow(2, testExp, testMod);
        long time1 = System.nanoTime() - start1;

        System.out.printf("快速幂计算 2^%d mod %d = %d%n", testExp, testMod, fastResult);
        System.out.printf("耗时: %.3f ms%n", time1 / 1_000_000.0);
        System.out.println("（指数高达10^12，朴素算法将无法在合理时间内完成）");
    }
}

代码运行结果示例

===== 费马小定理应用演示 =====

--- 1. 快速幂模运算 ---
7^13 mod 100 = 7
验证：Math.pow(7,13) mod 100 = 7

--- 2. 大数快速幂 ---
123456789^987654321 mod 1000000007 = 547654805

--- 3. 费马素性测试 ---
2 可能是素数: true
17 可能是素数: true
25 可能是素数: false
97 可能是素数: true
100 可能是素数: false
561 可能是素数: true
104729 可能是素数: true
1000003 可能是素数: true
（注意：561是卡迈克尔数，费马测试可能误判为素数）

--- 4. 模逆元计算 ---
7^(-1) mod 13 = 2
验证：7 * 2 mod 13 = 1

--- 5. 组合数取模 C(10, 3) mod 13 ---
C(10, 3) mod 13 = 12
验证：10!/(3!*7!) = 120

复杂度分析

扩展思考

1. 卡迈克尔数的检测：对于需要100%准确率的场景，应使用基于二次探测定理的Miller-Rabin测试。该测试将卡迈克尔数的误判概率从100%降到了可控范围。

2. RSA中的应用：RSA密钥生成需要两个大素数 p 和 q。Java的 BigInteger.probablePrime() 内部即使用Miller-Rabin测试，其本质与费马测试同源但更加鲁棒。

3. Lucas定理：对于素数 p，Lucas定理提供了一种将大组合数 C(n, k) mod p 分解为若干小组合数乘积的方法，在竞赛编程中极为常用。

4. 欧拉定理推广：费马小定理是欧拉定理的特例。欧拉定理指出，当 gcd(a, n) = 1 时，a^φ(n) ≡ 1 (mod n)，其中 φ(n) 是欧拉函数。当 n 为素数时，φ(n) = n - 1，即退化为费马小定理。

总结

费马小定理虽表述简洁，却蕴含着数论与算法设计的深刻思想。快速幂的二进制分解技巧不仅适用于模运算，也是矩阵快速幂、多项式快速幂等高级算法的基石。费马素性测试尽管存在卡迈克尔数这一理论漏洞，但其简洁的实现和高效率使其在教学和许多实际场景中仍具价值。理解这一定理，将为后续学习RSA加密、Miller-Rabin测试和更高级的数论算法打下坚实基础。