每日算法 — 使用java实现Pollard-Rho：大整数因数分解与Floyd判圈优化

算法概述

Pollard-Rho算法是一种用于大整数因数分解的随机化算法，由John Pollard于1975年提出。其核心思想基于生日悖论：在有限集合中随机选取元素，碰撞发生的期望次数远小于集合大小。算法通过构造一个伪随机序列，利用Floyd判圈算法检测序列中的循环，从而找到大合数的一个非平凡因子。

Pollard-Rho特别适用于分解具有小因子的合数，时间复杂度约为O(n^{1/4})，远优于试除法的O(√n)。该算法是RSA密码分析、数论研究和现代密码学测试中的重要工具。

核心原理

生日悖论与碰撞检测

假设有一个函数f(x)在模n下生成伪随机序列。若n有一个因子p，则序列在模p下会比模n下更快进入循环。当x_i ≡ x_j (mod p)但x_i ≢ x_j (mod n)时，gcd(|x_i – x_j|, n)将给出n的一个非平凡因子。

Floyd判圈算法

使用两个指针（龟和兔），慢指针每次走一步，快指针每次走两步。若存在循环，两指针必在环内相遇。设序列为x_{i+1} = f(x_i)，检测条件为：
– 龟：x = f(x)
– 兔：y = f(f(y))
– 计算d = gcd(|x – y|, n)

多项式递推函数

通常选择f(x) = (x² + c) mod n，其中c为随机常数。若失败，更换c值重试。

Java完整实现

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

/**
 * Pollard-Rho大整数因数分解算法
 * 基于生日悖论和Floyd判圈算法
 */
public class PollardRho {

    private static final SecureRandom random = new SecureRandom();

    /**
     * 使用Miller-Rabin进行素性测试
     * @param n 待测试的大整数
     * @param certainty 测试轮数，越高越准确
     * @return true表示n可能是素数，false表示n是合数
     */
    public static boolean isProbablePrime(BigInteger n, int certainty) {
        return n.isProbablePrime(certainty);
    }

    /**
     * Pollard-Rho核心算法
     * 寻找n的一个非平凡因子
     * @param n 待分解的合数
     * @return n的一个因子（可能为n本身表示失败）
     */
    public static BigInteger pollardRho(BigInteger n) {
        // 处理偶数
        if (n.mod(BigInteger.TWO).equals(BigInteger.ZERO)) {
            return BigInteger.TWO;
        }

        // 随机选择起始值和多项式常数c
        BigInteger c = new BigInteger(n.bitLength(), random).mod(n.subtract(BigInteger.ONE)).add(BigInteger.ONE);
        BigInteger x = new BigInteger(n.bitLength(), random).mod(n);
        BigInteger y = x;
        BigInteger d = BigInteger.ONE;

        // Floyd判圈：x走一步，y走两步
        while (d.equals(BigInteger.ONE)) {
            // 龟：x = f(x) = (x^2 + c) mod n
            x = x.multiply(x).mod(n).add(c).mod(n);
            // 兔：y = f(f(y))
            y = y.multiply(y).mod(n).add(c).mod(n);
            y = y.multiply(y).mod(n).add(c).mod(n);

            // 计算gcd(|x - y|, n)
            d = x.subtract(y).abs().gcd(n);

            // 若d == n，说明本次参数选择失败，需要重新开始
            if (d.equals(n)) {
                return pollardRho(n);
            }
        }

        return d;
    }

    /**
     * 递归分解大整数
     * 将n分解为素因子的映射（因子->指数）
     * @param n 待分解的整数
     * @param factors 存储因子的映射
     */
    public static void factor(BigInteger n, java.util.Map<BigInteger, Integer> factors) {
        // 基础情况：n <= 1
        if (n.compareTo(BigInteger.ONE) <= 0) {
            return;
        }

        // 若n是素数，直接记录
        if (isProbablePrime(n, 20)) {
            factors.put(n, factors.getOrDefault(n, 0) + 1);
            return;
        }

        // 使用Pollard-Rho找到一个因子
        BigInteger divisor = pollardRho(n);

        // 递归分解两个部分
        factor(divisor, factors);
        factor(n.divide(divisor), factors);
    }

    /**
     * 对外接口：分解整数并返回因子列表
     * @param n 待分解的大整数
     * @return 素因子列表（含重复）
     */
    public static java.util.List<BigInteger> factorize(BigInteger n) {
        java.util.Map<BigInteger, Integer> factorMap = new java.util.HashMap<>();
        factor(n, factorMap);

        java.util.List<BigInteger> result = new java.util.ArrayList<>();
        for (java.util.Map.Entry<BigInteger, Integer> entry : factorMap.entrySet()) {
            for (int i = 0; i < entry.getValue(); i++) {
                result.add(entry.getKey());
            }
        }
        java.util.Collections.sort(result);
        return result;
    }

    /**
     * 主程序：测试Pollard-Rho算法
     */
    public static void main(String[] args) {
        // 测试用例：已知因子的大合数
        BigInteger[] testCases = {
            new BigInteger("10403"),                    // 101 * 103
            new BigInteger("1000003"),                  // 大素数
            new BigInteger("9007199254740991"),        // 2^53 - 1 = 6361 * 69431 * 20394401
            new BigInteger("323"),                      // 17 * 19
            new BigInteger("8051"),                     // 83 * 97
        };

        System.out.println("===== Pollard-Rho大整数因数分解 =====\n");

        for (BigInteger n : testCases) {
            System.out.println("待分解数字: " + n);
            long startTime = System.currentTimeMillis();

            if (isProbablePrime(n, 20)) {
                System.out.println("结果: " + n + " 是素数");
            } else {
                java.util.List<BigInteger> factors = factorize(n);
                System.out.println("素因子分解: " + factors);

                // 验证分解结果
                BigInteger product = BigInteger.ONE;
                for (BigInteger f : factors) {
                    product = product.multiply(f);
                }
                System.out.println("验证乘积: " + product + " (正确: " + product.equals(n) + ")");
            }

            long endTime = System.currentTimeMillis();
            System.out.println("耗时: " + (endTime - startTime) + "ms\n");
        }

        // 性能测试：分解一个64位合数
        System.out.println("===== 性能测试 =====");
        BigInteger largeComposite = new BigInteger("18446744073709551617"); // 大合数
        System.out.println("分解大合数: " + largeComposite);
        long start = System.currentTimeMillis();
        java.util.List<BigInteger> largeFactors = factorize(largeComposite);
        long end = System.currentTimeMillis();
        System.out.println("因子: " + largeFactors);
        System.out.println("总耗时: " + (end - start) + "ms");
    }
}

算法优化策略

Brent判圈优化

Floyd判圈存在一个问题：龟兔间距可能很大，导致大量不必要的gcd计算。Brent优化记录兔子走过的步数，每次2的幂次步时重置乌龟位置，可减少约30%的模运算。

public static BigInteger pollardRhoBrent(BigInteger n) {
    if (n.mod(BigInteger.TWO).equals(BigInteger.ZERO)) return BigInteger.TWO;

    BigInteger y = new BigInteger(n.bitLength(), random).mod(n);
    BigInteger c = new BigInteger(n.bitLength(), random).mod(n.subtract(BigInteger.ONE)).add(BigInteger.ONE);
    BigInteger m = new BigInteger("100"); // 块大小
    BigInteger d = BigInteger.ONE;
    BigInteger r = BigInteger.ONE;
    BigInteger q = BigInteger.ONE;

    while (d.equals(BigInteger.ONE)) {
        BigInteger x = y;
        for (BigInteger i = BigInteger.ZERO; i.compareTo(r) < 0; i = i.add(BigInteger.ONE)) {
            y = y.multiply(y).mod(n).add(c).mod(n);
        }
        BigInteger k = BigInteger.ZERO;
        while (k.compareTo(r) < 0 && d.equals(BigInteger.ONE)) {
            BigInteger ys = y;
            BigInteger maxJ = m.min(r.subtract(k));
            for (BigInteger j = BigInteger.ZERO; j.compareTo(maxJ) < 0; j = j.add(BigInteger.ONE)) {
                y = y.multiply(y).mod(n).add(c).mod(n);
                q = q.multiply(x.subtract(y).abs()).mod(n);
            }
            d = q.gcd(n);
            k = k.add(m);
        }
        r = r.multiply(BigInteger.TWO);
    }

    if (d.equals(n)) return pollardRhoBrent(n);
    return d;
}

复杂度分析

应用场景

1. 密码学分析：测试RSA密钥强度，分解弱模数
2. 数论研究：研究整数的因子结构
3. 算法竞赛：处理大整数分解问题
4. 随机性测试：检验伪随机数生成器质量

总结

Pollard-Rho算法通过伪随机序列碰撞和Floyd判圈，巧妙地利用生日悖论实现了高效的大整数因数分解。其Java实现展示了BigInteger类在大数运算中的强大能力，以及递归分治在数论问题中的应用。理解此算法有助于深入掌握随机化算法设计和数论基础知识。