每日算法 — 使用java实现Miller-Rabin：概率性素数测试与二次探测定理

算法概述

Miller-Rabin素性测试是一种概率性算法，用于判断一个大整数是否为素数。由Gary Miller于1976年提出理论基础，Michael Rabin于1980年改进为实用的概率算法。该算法基于费马小定理的强版本，结合二次探测定理，可以在多项式时间内以任意高的概率判定素性。

与确定性素性测试（如AKS算法）相比，Miller-Rabin在实践中更为高效，已成为现代密码学、网络安全和大数运算库的标准组件。通过增加测试轮数，可将误判概率降至忽略不计的程度。

核心原理

费马小定理与伪素数

费马小定理：若p是素数，则对任意1 < a < p，有a^{p-1} ≡ 1 (mod p)。

但存在合数满足此条件（卡迈克尔数），因此费马测试不够可靠。

二次探测定理

若p是奇素数，则方程x² ≡ 1 (mod p)的解只有x ≡ 1和x ≡ -1 (mod p)。

将p-1写成d·2^s的形式，对随机底数a检验序列：
– a^d, a^{2d}, a^{4d}, …, a^{d·2^{s-1}} (mod p)

若p是素数，此序列要么首项为1，要么某处出现-1后全为1。

确定性底数选择

对于64位整数，测试底数a ∈ {2, 3, 5, 7, 11, 13, 17}即可保证绝对正确。对于大整数，每轮随机底数将错误概率降至≤1/4。

Java完整实现

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

/**
 * Miller-Rabin概率性素性测试
 * 基于二次探测定理的强伪素数检测
 */
public class MillerRabin {

    private static final SecureRandom random = new SecureRandom();

    // 对于64位整数，以下底数可保证确定性正确结果
    private static final long[] DETERMINISTIC_BASES_64 = {2, 3, 5, 7, 11, 13, 17};

    /**
     * 快速幂取模运算
     * 计算(base^exponent) mod modulus
     */
    private static long modPow(long base, long exponent, long modulus) {
        long result = 1;
        base = base % modulus;
        while (exponent > 0) {
            if ((exponent & 1) == 1) {
                result = mulMod(result, base, modulus);
            }
            base = mulMod(base, base, modulus);
            exponent >>= 1;
        }
        return result;
    }

    /**
     * 安全乘法取模，防止long溢出
     */
    private static long mulMod(long a, long b, long mod) {
        return BigInteger.valueOf(a).multiply(BigInteger.valueOf(b))
                .mod(BigInteger.valueOf(mod)).longValue();
    }

    /**
     * 对64位整数的确定性Miller-Rabin测试
     * 使用已知的最小底数集合，保证绝对正确
     * @param n 待测试的整数
     * @return true表示n是素数，false表示n是合数
     */
    public static boolean isPrime(long n) {
        // 处理小数字和偶数
        if (n < 2) return false;
        if (n == 2 || n == 3) return true;
        if ((n & 1) == 0) return false;

        // 将n-1写成d * 2^s的形式
        long d = n - 1;
        int s = 0;
        while ((d & 1) == 0) {
            d >>= 1;
            s++;
        }

        // 使用确定性底数进行测试
        for (long a : DETERMINISTIC_BASES_64) {
            if (a % n == 0) continue; // 底数与n相等时跳过

            long x = modPow(a, d, n);
            if (x == 1 || x == n - 1) continue;

            boolean witness = true;
            for (int r = 1; r < s; r++) {
                x = mulMod(x, x, n);
                if (x == n - 1) {
                    witness = false;
                    break;
                }
            }

            if (witness) {
                return false; // a是合数见证者
            }
        }

        return true;
    }

    /**
     * 大整数版本的Miller-Rabin测试
     * 使用BigInteger处理任意精度整数
     * @param n 待测试的大整数
     * @param k 测试轮数，轮数越多准确度越高
     * @return true表示n可能是素数，false表示n是合数
     */
    public static boolean isProbablePrime(BigInteger n, int k) {
        // 处理小数字
        if (n.compareTo(BigInteger.TWO) < 0) return false;
        if (n.equals(BigInteger.TWO) || n.equals(BigInteger.valueOf(3))) return true;
        if (n.mod(BigInteger.TWO).equals(BigInteger.ZERO)) return false;

        // 将n-1写成d * 2^s
        BigInteger d = n.subtract(BigInteger.ONE);
        int s = 0;
        while (d.mod(BigInteger.TWO).equals(BigInteger.ZERO)) {
            d = d.divide(BigInteger.TWO);
            s++;
        }

        // 进行k轮随机底数测试
        for (int i = 0; i < k; i++) {
            // 生成随机底数a，范围[2, n-2]
            BigInteger a;
            do {
                a = new BigInteger(n.bitLength(), random);
            } while (a.compareTo(BigInteger.TWO) < 0 || a.compareTo(n.subtract(BigInteger.TWO)) > 0);

            BigInteger x = a.modPow(d, n);
            if (x.equals(BigInteger.ONE) || x.equals(n.subtract(BigInteger.ONE))) {
                continue;
            }

            boolean continueOuter = false;
            for (int r = 1; r < s; r++) {
                x = x.modPow(BigInteger.TWO, n);
                if (x.equals(n.subtract(BigInteger.ONE))) {
                    continueOuter = true;
                    break;
                }
            }

            if (continueOuter) continue;
            return false; // 发现合数见证者
        }

        return true; // 通过所有测试，n可能是素数
    }

    /**
     * 生成指定比特长度的大素数
     * @param bitLength 素数的比特长度
     * @param certainty 测试确定度（轮数）
     * @return 一个 probable 素数
     */
    public static BigInteger generatePrime(int bitLength, int certainty) {
        while (true) {
            BigInteger candidate = new BigInteger(bitLength, random);
            // 确保是奇数且最高位为1
            candidate = candidate.setBit(0).setBit(bitLength - 1);
            if (isProbablePrime(candidate, certainty)) {
                return candidate;
            }
        }
    }

    /**
     * 找出区间[start, end]内的所有素数
     */
    public static java.util.List<Long> findPrimesInRange(long start, long end) {
        java.util.List<Long> primes = new java.util.ArrayList<>();
        for (long i = Math.max(2, start); i <= end; i++) {
            if (isPrime(i)) {
                primes.add(i);
            }
        }
        return primes;
    }

    /**
     * 主程序：测试Miller-Rabin算法
     */
    public static void main(String[] args) {
        System.out.println("===== Miller-Rabin素性测试 =====\n");

        // 测试1：验证已知数字
        long[] testNumbers = {
            2, 3, 5, 17, 19, 97, 101, 103,  // 素数
            4, 9, 15, 21, 100, 121, 341,     // 合数
            561, 1105, 1729, 2465,           // 卡迈克尔数（费马测试会误判）
            104729,                          // 第10000个素数
            2147483647L,                     // 梅森素数2^31-1
        };

        System.out.println("--- 64位确定性测试 ---");
        for (long n : testNumbers) {
            boolean isPrime = isPrime(n);
            String type = isPrime ? "素数" : "合数";
            System.out.printf("%12d -> %s%n", n, type);
        }

        // 测试2：大整数概率测试
        System.out.println("\n--- 大整数概率测试 ---");
        BigInteger[] bigTests = {
            new BigInteger("10403"),                           // 合数
            new BigInteger("170141183460469231731687303715884105727"), // 梅森素数M127
            new BigInteger("1234567890123456789012345678901234567891"), // 大数
        };

        for (BigInteger n : bigTests) {
            long start = System.currentTimeMillis();
            boolean result = isProbablePrime(n, 20);
            long end = System.currentTimeMillis();
            System.out.println("数字: " + n);
            System.out.println("结果: " + (result ? "可能是素数" : "合数"));
            System.out.println("耗时: " + (end - start) + "ms\n");
        }

        // 测试3：生成大素数
        System.out.println("--- 生成512位素数 ---");
        long genStart = System.currentTimeMillis();
        BigInteger prime512 = generatePrime(512, 20);
        long genEnd = System.currentTimeMillis();
        System.out.println("生成耗时: " + (genEnd - genStart) + "ms");
        System.out.println("512位素数（前60位）: " + prime512.toString().substring(0, 60) + "...");
        System.out.println("验证: " + (isProbablePrime(prime512, 30) ? "通过" : "失败"));

        // 测试4：统计区间素数数量
        System.out.println("\n--- 区间素数统计 ---");
        java.util.List<Long> primes = findPrimesInRange(1, 1000);
        System.out.println("1-1000内的素数数量: " + primes.size() + " (理论值: 168)");
        System.out.println("前10个: " + primes.subList(0, 10));
    }
}

二次探测定理详解

对于奇素数p，设p-1 = d·2^s。对任意与p互素的底数a：

计算x_0 = a^d mod p
若x_0 ≡ 1 (mod p)，则通过测试
否则依次计算x_i = x_{i-1}² mod p，i = 1, …, s-1
若存在x_i ≡ -1 (mod p)，则通过测试
若都不满足，则a是合数见证者

此性质源于多项式x² ≡ 1 (mod p)在素数模下仅有±1两个解的特性。

复杂度分析

指标	复杂度	说明
单轮时间	O(log³ n)	使用快速幂，每次模乘O(log² n)
k轮总时间	O(k·log³ n)	k轮独立测试
错误概率	≤ 4^{-k}	每轮最多1/4误判率
空间复杂度	O(log n)	存储中间结果
64位确定性	O(1)	固定7个底数，绝对正确

应用场景

RSA密钥生成：生成大素数p和q用于模数n = pq
密码学协议：TLS/SSL握手、数字签名验证
素数筛法优化：快速剔除大范围内的合数
竞赛数学：处理大数素性判定问题
随机数生成：生成密码学安全的大素数种子

总结

Miller-Rabin算法通过二次探测定理将费马测试的可靠性提升到实用级别，是概率算法在数论中的经典应用。其Java实现展示了从64位确定性版本到任意精度大整数版本的完整演进，以及密码学中大素数生成的典型流程。掌握此算法是理解现代公钥密码体系的基础。

Tagged with: Miller-Rabin 二次探测密码学素性测试费马小定理