算法背景
整数因数分解是现代密码学的数学基础——RSA的安全性正是建立在大整数分解的计算困难性之上。Pollard’s Rho算法由John Pollard于1975年提出，是分解合数的经典概率算法，在数论研究、密码分析和信息安全领域具有重要地位。
配合Miller-Rabin素性测试，Pollard Rho可以在亚指数时间内分解大多数合数，是理解现代数论算法的绝佳入门案例。
核心思想
Pollard Rho基于生日悖论：在模 $n$ 的伪随机序列中，大约 $\sqrt{n}$ 步后会出现循环。利用Floyd判圈算法检测循环，若序列在模 $n$ 下碰撞，则其差与 $n$ 的最大公约数很可能给出 $n$ 的一个非平凡因子。
迭代函数通常取 $f(x) = (x^2 + c) \mod n$，$c$ 为随机常数。
Java实现：Miller-Rabin素性测试
import java.math.BigInteger;
import java.security.SecureRandom;
public class MillerRabin {
private static final SecureRandom RANDOM = new SecureRandom();
/**
* Miller-Rabin确定性测试 (适用于64位整数)
* 对于n < 3,317,044,064,679,887,385,961,981，测试前12个素数底即可确定
*/
private static final long[] WITNESSES_64 = {
2L, 3L, 5L, 7L, 11L, 13L, 17L, 19L, 23L, 29L, 31L, 37L
};
/**
* 快速幂取模: 计算 (base^exp) % mod
*/
public static long modPow(long base, long exp, long mod) {
long result = 1;
long b = base % mod;
while (exp > 0) {
if ((exp & 1) == 1) {
result = (__int128(result) * b) % mod; // 注意溢出
}
b = (__int128(b) * b) % mod;
exp >>= 1;
}
return result;
}
// 辅助: 模拟128位整数 (使用BigInteger)
private static long __int128(long a) { return a; }
/**
* Miller-Rabin单轮测试
* @return true 表示可能是素数, false 表示一定是合数
*/
public static boolean millerRabinTest(long n, long witness) {
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++;
}
long x = modPow(witness, d, n);
if (x == 1 || x == n - 1) return true;
for (int r = 1; r < s; r++) {
x = modPow(x, 2, n);
if (x == n - 1) return true;
if (x == 1) return false;
}
return false;
}
/**
* 确定性Miller-Rabin测试 (64位整数)
*/
public static boolean isPrime(long n) {
if (n < 2) return false;
for (long p : new long[]{2,3,5,7,11,13,17,19,23,29,31,37}) {
if (n % p == 0) return n == p;
}
for (long witness : WITNESSES_64) {
if (witness >= n) continue;
if (!millerRabinTest(n, witness)) return false;
}
return true;
}
public static void main(String[] args) {
long[] testNumbers = {2, 17, 91, 104729, 1000000007L, 1000000000039L};
for (long n : testNumbers) {
System.out.println(n + " is " + (isPrime(n) ? "prime" : "composite"));
}
}
}
Java实现：Pollard Rho因数分解
import java.math.BigInteger;
import java.security.SecureRandom;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
public class PollardRho {
private static final Random RANDOM = new SecureRandom();
private static final BigInteger TWO = BigInteger.valueOf(2);
/**
* 使用BigInteger的Pollard Rho算法
* 迭代函数: f(x) = x^2 + c (mod n)
*/
public static BigInteger pollardsRho(BigInteger n) {
if (n.mod(TWO).equals(BigInteger.ZERO)) {
return TWO; // 偶数直接返回2
}
if (n.isProbablePrime(20)) {
return n; // 素数直接返回
}
while (true) {
BigInteger c = new BigInteger(n.bitLength(), RANDOM);
BigInteger x = new BigInteger(n.bitLength(), RANDOM).mod(n);
BigInteger y = x;
BigInteger d = BigInteger.ONE;
while (d.equals(BigInteger.ONE)) {
// Floyd判圈: x走一步, y走两步
x = f(x, c, n);
y = f(f(y, c, n), c, n);
// d = gcd(|x-y|, n)
d = x.subtract(y).abs().gcd(n);
}
if (!d.equals(n)) {
return d; // 找到非平凡因子
}
// 若d==n，换随机参数重试
}
}
/** 迭代函数 f(x) = x^2 + c (mod n) */
private static BigInteger f(BigInteger x, BigInteger c, BigInteger n) {
return x.multiply(x).mod(n).add(c).mod(n);
}
/**
* 递归分解n的所有素因子
*/
public static void factor(BigInteger n, List<BigInteger> factors) {
if (n.equals(BigInteger.ONE)) return;
if (n.isProbablePrime(20)) {
factors.add(n);
return;
}
BigInteger divisor = pollardsRho(n);
factor(divisor, factors);
factor(n.divide(divisor), factors);
}
/**
* 分解并返回排序后的素因子列表 (含重复)
*/
public static List<BigInteger> factorize(BigInteger n) {
List<BigInteger> factors = new ArrayList<>();
factor(n, factors);
Collections.sort(factors);
return factors;
}
public static void main(String[] args) {
// 测试分解
BigInteger[] testNumbers = {
new BigInteger("91"), // 7 * 13
new BigInteger("8051"), // 83 * 97
new BigInteger("10403"), // 101 * 103
new BigInteger("1000000007"), // 素数
new BigInteger("10403").multiply(new BigInteger("8051")),
};
for (BigInteger n : testNumbers) {
System.out.println("\nFactoring: " + n);
List<BigInteger> factors = factorize(n);
System.out.println("Factors: " + factors);
// 验证
BigInteger product = BigInteger.ONE;
for (BigInteger f : factors) product = product.multiply(f);
System.out.println("Verification: " + product.equals(n));
}
}
}
Java实现：64位优化版本
public class PollardRho64 {
private static final java.util.Random RAND = new java.util.Random();
/**
* 64位Pollard Rho (使用long运算)
* 适用于n < 2^63 的合数分解
*/
public static long pollardsRho(long n) {
if ((n & 1) == 0) return 2;
if (n % 3 == 0) return 3;
long c = Math.abs(RAND.nextLong()) % (n - 1) + 1;
long x = Math.abs(RAND.nextLong()) % (n - 2) + 2;
long y = x;
long d = 1;
while (d == 1) {
x = (mulMod(x, x, n) + c) % n;
y = (mulMod(y, y, n) + c) % n;
y = (mulMod(y, y, n) + c) % n;
long diff = x > y ? x - y : y - x;
d = gcd(diff, n);
}
return d == n ? pollardsRho(n) : d;
}
/** 安全乘法取模: (a*b) % mod, 防止溢出 */
public static long mulMod(long a, long b, long mod) {
long result = 0;
a %= mod;
while (b > 0) {
if ((b & 1) == 1) {
result = (result + a) % mod;
}
a = (a << 1) % mod;
b >>= 1;
}
return result;
}
/** 欧几里得算法求GCD */
public static long gcd(long a, long b) {
while (b != 0) {
long temp = a % b;
a = b;
b = temp;
}
return a;
}
/**
* 完整分解n的所有素因子
*/
public static void factorAll(long n, java.util.List<Long> factors) {
if (n == 1) return;
if (isPrime(n)) {
factors.add(n);
return;
}
long d = pollardsRho(n);
factorAll(d, factors);
factorAll(n / d, factors);
}
/** 简单素性测试 */
private static boolean isPrime(long n) {
if (n < 2) return false;
if (n == 2 || n == 3) return true;
if ((n & 1) == 0) return false;
for (long i = 3; i * i <= n; i += 2) {
if (n % i == 0) return false;
}
return true;
}
public static void main(String[] args) {
long[] tests = {91, 8051, 10403, 1000003L * 1000033L};
for (long n : tests) {
java.util.List<Long> factors = new java.util.ArrayList<>();
factorAll(n, factors);
java.util.Collections.sort(factors);
System.out.println(n + " = " + factors);
}
}
}
应用：RSA模数分解演示
public class RSABreakDemo {
/**
* 演示如何使用Pollard Rho分解RSA模数
* 注意: 仅适用于小密钥，真实RSA-2048无法分解
*/
public static void main(String[] args) {
// 生成两个小素数 (演示用，真实RSA使用1024位以上大素数)
BigInteger p = new BigInteger("104729");
BigInteger q = new BigInteger("104743");
BigInteger n = p.multiply(q);
BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
System.out.println("RSA Demo Key:");
System.out.println("n = " + n);
System.out.println("p = " + p + " (secret)");
System.out.println("q = " + q + " (secret)");
// 使用Pollard Rho分解n
System.out.println("\nAttacking n with Pollard Rho...");
long start = System.currentTimeMillis();
BigInteger factor = PollardRho.pollardsRho(n);
long elapsed = System.currentTimeMillis() - start;
System.out.println("Found factor: " + factor + " in " + elapsed + "ms");
System.out.println("Other factor: " + n.divide(factor));
// 一旦分解n，即可计算私钥d
BigInteger e = new BigInteger("65537");
BigInteger d = e.modInverse(phi);
System.out.println("\nRecovered private key d = " + d);
}
}
算法对比与选型
| 算法 | 时间复杂度 | 适用场景 | 特点 |
|---|---|---|---|
| 试除法 | $O(\sqrt{n})$ | n < $10^{12}$ | 最简单，确定性强 |
| Pollard Rho | $O(n^{1/4})$ | $10^{12}$ < n < $10^{20}$ | 概率算法，实现简单 |
| ECM (椭圆曲线) | 亚指数 | 中等大小(20-60位) | 对中等素因子高效 |
| GNFS (数域筛) | $O(e^{(\log n)^{1/3}})$ | > $10^{100}$ | 目前最快，用于RSA-512等 |
| QS (二次筛) | 亚指数 | 80-100位 | GNFS的过渡方案 |
复杂度分析
| 指标 | 复杂度 |
|---|---|
| Pollard Rho期望时间 | $O(n^{1/4})$ 次模运算 |
| Floyd判圈空间 | $O(1)$ |
| Miller-Rabin单轮 | $O(\log n)$ 次模乘 |
| 完整因子分解(递归) | $O(n^{1/4} \cdot \log n)$ |
密码学意义
- 密钥生成: RSA要求选择足够大的素数，使Pollard Rho不可行
- 安全边界: RSA-2048的模数约617位，远超Pollard Rho能力
- 侧信道攻击: 实际攻击常利用实现漏洞，而非纯数学分解
- 量子威胁: Shor算法可在多项式时间内分解，推动后量子密码研究
进一步优化方向
- Brent判圈法: 替代Floyd判圈，减少模运算次数
- 参数选择: 动态调整多项式参数$c$，提高成功率
- 并行化: 多线程尝试不同参数，首个成功者返回
- ECM集成: 对找到的小因子先用ECM验证
Pollard Rho算法以优雅的数学思想和简洁的实现，成为因数分解领域的经典之作。理解其原理不仅能应对算法竞赛中的数论问题，更为深入现代密码学奠定了坚实基础。
