试除法的大数困境：为什么几十位数就试不动了
试除法判断素数的最坏步数约为 √n；n 有 d 位时，这约等于 10^(d/2) 次候选除法，所以位数线性增加、工作量却指数爆炸——30 位还能勉强算，60 位就超过宇宙年龄。
A complete interactive classroom, not just a preview.
Start when you are ready to enter this Stage's 4 scenes and explore, respond, and learn as you go.
试除法判断大数时，工作量到底如何增长？为什么几十位数就慢到不可行？
判断 97 是否素数只需几步；判断一个 60 位数是否素数，用每秒一万亿次的试除也要超过宇宙年龄。
人们通常以为多一位数只是多花一点时间，但试除法的候选因子数会随位数指数爆炸。
一个可交互的位数—步数—时间滑块，直观展示 d 位数的试除步数约为 10^(d/2)。
大数场景不能用朴素试除，必须改用 Miller–Rabin 这类能绕过指数爆炸的素性检验。
- Miller–Rabin 的具体算法细节
- 确定性大数素性检验的证明
- 整数分解算法（ECM、数域筛法等）
- 并行计算优化细节
- 01一个 60 位数，试除法要多久？slideSlot 1Hook
从一个违反直觉的估算开始：简单朴素的试除法，判断大素数时竟然需要宇宙年龄量级的时间。
- 试除法是判断素数最直觉的方法
- 判断一个 60 位数最坏要检查约 10^30 个候选因子
- 即使每秒查一万亿个，也要超过宇宙年龄
Phenomenon判断一个 60 位数字是否素数，朴素试除需要检查约 10^30 个候选因子；即使每秒检查一万亿个，也要超过宇宙年龄。
Question为什么这样简单的算法，遇到大数会突然失效？
- 02直觉：多一位数，只是多试几个数？slideSlot 2Tension
让学习者预测 30 位到 60 位的工作量差距，并点破常见的“线性”直觉。
- n 增加一位，n 本身乘 10
- 很多人会以为工作量只增加 2～10 倍
- 实际增加的是 10 的 15 次方倍
Prediction如果从 30 位跳到 60 位，你可能会猜试除次数增加 2 倍或 10 倍左右。
Tempting intuition位数多一倍，查的数也只多一倍？
- 03拖动位数，看试除步数暴涨interactiveSlot 3Reveal
用滑块改变 n 的位数，观察最坏需要的候选因子数和同一台机器上的估算时间。
- 位数增加 10 位，试除次数约增加 10^5 倍
- 30 位约 10^15 次，60 位约 10^30 次
- 时间从 17 分钟冲到 300 亿年
Evidence滑块显示：d=30 时约 10^15 次，d=60 时约 10^30 次；同一台每秒 10^12 次的机器从 17 分钟变成超过宇宙年龄。
Conclusion造成“慢”的不是单次除法的速度，而是候选因子数量随位数指数膨胀。
Mechanism- 1试除法的退出条件是检查完所有 ≤√n 的候选因子
- 2n 有 d 位时 n≈10^d，所以 √n≈10^(d/2)，候选因子数也按 10^(d/2) 增长
- 3因此 d 每增加 10，步数乘 10^5；从 60 位开始完全不可行
- 04遇到大数，换一条路slideSlot 4Takeaway
把结论迁移到真实场景：现代素性检验为什么不用试除。
- 位数为 d 的 n，试除最坏需要约 10^(d/2) 次
- 几十位以上时，朴素试除不可能完成
- 现代算法用随机与数论结构绕过指数爆炸
Transfer当你要判断一个 100 位的 RSA 素数时，不要写从 2 到 √n 的循环；改用 Miller–Rabin 这类概率素性检验。
Expected inference用一小批随机底数的模幂测试，能在毫秒级给出“几乎确定”的答案，而不是靠 10^50 次试除。
Discussion threads for a Stage aren't available yet.
