Curiosity

筛法在加密系统里如何生成候选质数

厘清确定性 Eratosthenes/分段筛与概率 Miller–Rabin 测试在小候选池与强素数生成中的分工,理解真实加密库在密钥生成阶段付出的真实代价,以及为何筛法不会消失。

Before you enter

A complete interactive classroom, not just a preview.

Start when you are ready to enter this Stage's 7 scenes and explore, respond, and learn as you go.

Scenes

14 min

Estimated

Content language: zh-CN

Created by

MathClue

Start this Stage

Remix into your version

Sign-in may be required to play

What happens inside

01从一道开放问题开始slide
Question
展示一把新生成的 RSA 公钥指纹,提出驱动问题:这个大数字是怎么被确认成质数的?
- RSA/DH 密钥生成依赖大质数,但 n 位数的质数并不显然
- 驱动问题:筛法如何在加密系统里被用来生成候选质数?代价和边界是什么?
02先猜再算:你会怎么处理这堆候选?interactive
Prediction
给出一个长度从 8 位到 1024 位可调的候选池,让学习者选择'暴力试除'、'Eratosthenes 筛'或'先筛后概率测试',观察耗时与残留候选数。
- 学习者需要在动手前做出取舍判断
- 切换候选池规模和候选数量,直观看到不同方法在 √n 前的分叉
- 调动直觉,为下一步真正的证据做铺垫
03证据:真实候选池的代价曲线slide
Evidence
用一张时间-候选规模对照图(数据驱动的示意图)展示 Eratosthenes 筛、暴力试除、概率测试三种策略在不同候选池规模下的耗时。
- 候选池规模小时,试除反而更便宜
- 候选池增长到几万以上时,筛法迅速拉开优势
- 概率测试始终稳定在多轮模幂的水平
- 真实 OpenSSL/OpenSSH 风格实现采用'筛 + Miller–Rabin'的串联
04两步组合:筛掉合数,再拍板质数slide
Explanation
解释经典 Eratosthenes 筛为何只能在小范围内直接使用,以及分段筛 (segmented sieve) 如何把 100KB 内存变成能筛十亿候选的工具;再讲 Miller–Rabin 测试如何用模幂与欧几里得小步快跑,让误判率降到 2⁻⁸⁰。
- Eratosthenes 筛的空间复杂度 O(n) 决定它无法直接装下 n 位质数
- 分段筛:用 √n 之内的素数当尺子,在窗口内逐段划掉合数
- Miller–Rabin 测试基于 Fermat 检验与强伪证分离,每轮误判 ≤ 1/4
- 独立选取多个底,40 轮后误判 ≈ 2⁻⁸⁰,可以放心当质数使用
05适用边界:什么时候筛法反而拖后腿?slide
Boundary
讨论当候选池远小于 √n、或候选只需要一两个质数时,直接用确定性 Lucas/Proth/APRCL 测试或概率 Miller–Rabin 反而更便宜;再补充强素数需求 (p−1 与 p+1 都有大因子) 如何让筛后的二次挑选更麻烦。
- 候选池小、位数大:筛法'挖不来',直接上概率测试
- 需要强素数对抗 Pollard p−1 攻击时,筛出来的候选还要再被二次过滤
- AKS、ECPP 等确定性证明在 1024 位以上仍是学术级开销
- 边界小结:筛法用于'缩小候选池',而非'判定质数'
06迁移:换一个场景,你还会用筛法吗?quiz
Transfer
学习者在读完解释后,面对一个新场景(批量生成 100 个 256 位随机质数)做出方法选择,验证他们是否理解筛法的边界。
- 把已学步骤迁移到不同规模的问题
- 理解'什么时候用筛,什么时候直接上概率测试'是真实工程判断
07回到一开始:RSA 公钥是这样诞生的slide
Resolution
串联所有发现,直接回答驱动问题:筛法是公钥密码生成流水线的'预筛选'环节,它把不可能逐个验证的候选池压到可处理规模,再交给概率素性测试签发最终结果。
- 筛法 = 候选池压缩器,不是质数判官
- 代价:每生成一个 2048 位强素数大约是数十毫秒到几百毫秒的可观测开销
- 边界:候选池规模足够大、'能用内存换时间'时最值得使用
- 现代 OpenSSL/BoringSSL/GnuPG 都仍依赖这一组合,没有替代方案