# 1. Pollard Rho 的生日悖论基础中为什么随机采样能在 O(n^{1/4}) 期望时间内找到因子？ A 每个因子都很大 B 使用快速幂 C 需要遍历所有素数 D 最小素因子 p ≤ √n，生日悖论给出 O(√p) 步 ✓ 正确答案
# 2. Miller-Rabin 的错误率上界中每轮强伪素数占比不超过 1/4，取 k 轮后错误率不超过 4^-k，64 位内固定基底为何可确定性判定 A 数学上证明每轮错误率恒为 0 B 强伪素数的集合在该范围内已被穷举验证 ✓ 正确答案 C 每轮错误率上界为 1/2 D 64 位没有合数
# 4. Miller-Rabin 与 Solovay-Strassen 中为什么实践中几乎都用 Miller-Rabin（误差界差异与可证明性）？ A 1/2 B 1/4 ✓ 正确答案 C 1/8 D 1/16
# 5. BPSW 素性测试中 Miller-Rabin 基底 2 加 Lucas 序列为何至今无已知反例，作为工程默认组合 A 费马测试 + 埃氏筛 B Miller-Rabin 基底 2 + Lucas 强伪素数测试 ✓ 正确答案 C Solovay-Strassen + 二次探测 D 两个不同基底的 Miller-Rabin
# 6. Pollard p-1 算法为什么对安全素数失效，p-1=2q 只有小因子 2 与一个大素因子 q，不满足 B-光滑条件；这与 Pollard Rho 的生日悖论思路有何不同？ A p 太大 B p 是偶数 C p-1=2q 不满足 B-光滑条件（含大素因子 q） ✓ 正确答案 D 生日悖论不适用
# 8. Miller-Rabin 为什么能识别卡迈克尔数，卡迈克尔数满足费马测试但二次探测如何暴露其合数性，以 561 为例？ A 因为卡迈克尔数不是合数 B 因为二次探测在多个素因子模下无法同时满足 ∓1 条件 ✓ 正确答案 C 因为卡迈克尔数太大 D 因为卡迈克尔数是偶数
# 9. Miller-Rabin 确定性版本在 64-bit 范围内的 witness set。 A {2, 3, 5} B {2, 325, 9375, 28178, 450775, 9780504, 1795265022} ✓ 正确答案 C {2, 4, 8, 16} D {1, 2, 3}
# 10. Pollard Rho 分解 RSA 模数为什么不可行，对 512 位素因子期望约 O(2^128) 步，标准 RSA 模数为何只能用 NFS/ECM 而非 Pollard Rho 分解？ A Pollard Rho B Pollard p-1 C 数域筛法（NFS） ✓ 正确答案 D 试除法
# 11. Pollard Rho 与 Pollard p-1 的区别中为什么 p-1 依赖素因子减一的光滑性而 rho 依赖生日悖论，两者在分解 RSA 模数时的适用场景有何不同？ A 素因子本身光滑 B 生日悖论 C 素因子加一光滑 D 素因子减一（p-1）光滑 ✓ 正确答案
# 12. Pollard Rho 与 Miller-Rabin 的工程配合中大数分解的标准流程（判素→找因子→递归）如何实现？ A 还原模数 B 判断终止条件（n 是否为素数） ✓ 正确答案 C 计算 gcd D 找到因子
# 13. Pollard Rho 的常见优化中 Brent 版本（倍增步数）、倍增 gcd、避免每次迭代都取模的性能优化？ A 提高 gcd 正确性 B 减少内存 C 增加随机性 D 减少昂贵的 gcd 调用次数 ✓ 正确答案
# 14. Pollard Rho 的随机函数 f(x)=x^2+c 为什么会产生循环，Floyd 判圈与 Brent 判圈在因子发现上的差异？ A 检测更准 B 常数更小、更快 ✓ 正确答案 C 需要更多内存 D 不需要随机函数
# 15. Pollard Rho 的 Floyd cycle detection 与 birthday paradox。 A 生成随机数 B 检测随机序列中的碰撞 ✓ 正确答案 C 验证费马小定理 D 计算素数
# 16. Pollard Rho 在密码学中的角色中为什么它只能有效分解含小素因子的数（如共模攻击中两模数的 gcd），对标准 RSA 模数无能为力？ A 用 Pollard p-1 B 计算两模数的最小公倍数 C 用 BSGS D 计算两模数的最大公约数 gcd ✓ 正确答案
# 17. Miller-Rabin 的二次探测中为什么能筛除卡迈克尔数等伪素数？ A a^{n-1} ≡ 1 B 存在 r 使 a^{2^r d} ≡ -1（且 a^d ≢ 1） ✓ 正确答案 C a 是偶数 D n 是奇数
# 18. Pollard p-1 的 Stage 2 中为什么把光滑界从 B1 扩展到 B1-B2 区间能提高成功概率，与 Stage 1 的配合 A p-1 含两个大素因子 B p-1 有一个素因子在 (B1, B2] 区间的情形 ✓ 正确答案 C p 是素数 D 生日悖论
# 19. AKS 与 ECPP 中确定性素性证明如何工作，工程上为何仍以概率测试为主 A 概率测试不需要费马小定理 B 概率测试更快更简单，且错误率可做到任意小 ✓ 正确答案 C AKS 无法证明素性 D 概率测试错误率恒为 0
