题目理解

我们面对的是 RSA 加密系统的破解问题。给定：

• 公钥 $(N, e)$
• 密文 $c$

需要求出：

• 私钥 $d$
• 明文 $n$

---

RSA 算法回顾

密钥生成：

1. 选择两个大质数 $p$, $q$
2. 计算 $N = p \times q$
3. 计算 $r = (p-1)(q-1)$（欧拉函数）
4. 选择 $e$ 满足 $1 < e < r$ 且 $\gcd(e, r) = 1$
5. 计算 $d$ 满足 $ed \equiv 1 \pmod{r}$

加密：

$c \equiv n^e \pmod{N}$

解密：

$n \equiv c^d \pmod{N}$

---

破解思路

要破解 RSA，关键是要分解 $N$：

• 已知 $N = p \times q$
• 如果能够分解 $N$ 得到 $p$ 和 $q$
• 就能计算 $r = (p-1)(q-1)$
• 然后计算 $d \equiv e^{-1} \pmod{r}$
• 最后解密 $n \equiv c^d \pmod{N}$

---

Pollard's Rho 算法

对于大整数分解，我们使用 Pollard's Rho 算法：

算法原理：

利用生日悖论和Floyd循环检测来寻找因子。

算法步骤：

function pollard_rho(n):
    if n is even: return 2
    x = random(2, n-1)
    y = x
    c = random(1, n-1)
    d = 1
    
    while d == 1:
        x = (x*x + c) mod n
        y = (y*y + c) mod n
        y = (y*y + c) mod n  # y moves twice as fast
        d = gcd(|x - y|, n)
        if d == n: restart with new random values
    
    return d

---

扩展欧几里得算法

得到 $p$, $q$ 后，需要计算模逆元 $d \equiv e^{-1} \pmod{r}$：

使用扩展欧几里得算法解方程： [ ed + kr = 1 ] 其中 $d$ 就是我们要找的私钥。

---

快速幂模运算

最后解密时计算： [ n \equiv c^d \pmod{N} ] 使用快速幂算法避免直接计算大指数。

---

算法流程

1. 分解 $N$：使用 Pollard's Rho 找到 $p$, $q$
2. 计算 $r$：$r = (p-1)(q-1)$
3. 计算 $d$：解 $ed \equiv 1 \pmod{r}$
4. 解密 $n$：计算 $n \equiv c^d \pmod{N}$

---

复杂度分析

• Pollard's Rho：期望时间 $O(N^{1/4})$
• 扩展欧几里得：$O(\log N)$
• 快速幂：$O(\log d)$
• 对于 $N \leq 2^{62}$，完全可行

---

样例验证

输入：

3 187 45

分解过程：

• $N = 187$
• Pollard's Rho 找到 $p = 11$, $q = 17$
• $r = (11-1)(17-1) = 10 \times 16 = 160$
• 解 $3d \equiv 1 \pmod{160}$ 得 $d = 107$
• 解密：$45^{107} \equiv 12 \pmod{187}$

输出：107 12 ✓

---

优化和改进

1. 更高效的分解算法：对于更大的 $N$，可以使用 SQUFOF 或 ECM
2. 并行计算：同时运行多个 Pollard's Rho 实例
3. 预计算：对小质数进行试除后再用 Pollard's Rho

---

总结

本题的关键在于：

1. 理解 RSA 加密系统的数学原理
2. 掌握大整数分解算法（Pollard's Rho）
3. 熟练使用扩展欧几里得算法求模逆元
4. 使用快速幂进行模指数运算

这是一个典型的数论+密码学问题，考察了对数论算法和密码学原理的理解与应用能力。