质数与因式分解
了解质数为何是公钥密码学的基础
质数与因式分解 是 CoddyKit 上的免费 Cryptology Academy 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Cryptology Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Cryptology Academy 课程共包含 4 节课。
欢迎
质数只能被 1 和自身整除。它们是乘法的基本构件，也是 RSA、Diffie-Hellman 及许多其他密码系统的基石。
定义与示例
质数包括：2、3、5、7、11、13、17、19、23、29……如果一个数的正因数只有 1 和它自身，那么它就是质数。按照约定，1 不是质数。
算术基本定理
每个大于 1 的整数都可以以唯一的方式分解为质数的乘积（因数顺序不同除外）。60 = 2² × 3 × 5。这种唯一性正是基于因数分解的密码学能够运作的原因。
试除法
def is_prime(n):
if n < 2: return False
for i in range(2, int(n**0.5)+1):
if n % i == 0: return False
return True
只需要检查到 √n——如果在 √n 以下没有找到因数，那么 n 就是质数。
埃拉托斯特尼筛法
要找出不超过 N 的所有质数：先列出 2..N 的所有数字。划去 2 的倍数，然后划去 3 的倍数、5 的倍数，以此类推。剩下的数字就是质数。运行时间为 O(N log log N)。
素性测试：Miller-Rabin
对于较大的数字（2048 位），试除法太慢。Miller-Rabin 是一种概率测试：运行 40 次后，出错概率小于 4^(-40)。
整数因数分解
给定 n = p × q，找出 p 和 q 是整数因数分解问题。如果 n 有 2048 位，目前已知的最佳算法需要执行 2^112 次运算——目前无法实际完成。
RSA 为何使用两个大质数
RSA 模数 n = p × q。知道 n 但不知道 p、q，就很难计算私钥。RSA 的安全性完全依赖于分解 n 的困难程度。
生成大质数
from sympy import randprime
p = randprime(2**1023, 2**1024) # random 1024-bit prime
做法：生成一个随机奇数，使用 Miller-Rabin 进行测试，重复此过程直到得到质数。
安全质数与强质数
安全质数 p = 2q+1，其中 q 也是质数。安全质数可以抵御针对 DH 的某些攻击。RSA 有时使用强质数来防止 Pollard 的 p-1 攻击。
质数间隔与无穷性
欧几里得在 300 BCE 证明了质数有无穷多个。孪生质数猜想（质数 p 和 p+2 有无穷多对）至今仍未得到证明。密码学永远不会用尽质数。
快速检查
RSA 为什么使用大质数？
回顾
您已经理解了质数和因数分解。接下来，我们将应用欧拉 φ 函数和 GCD——这是学习 RSA 前所需的最后几个数学工具。
常见问题解答
「质数与因式分解」课时是免费的吗？
是的 — 「质数与因式分解」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Cryptology Academy 课程的其余内容，请升级到 CoddyKit PRO。 Cryptology Academy 课程共包含 4 节课。
「质数与因式分解」这节课中我会学到什么？
了解质数为何是公钥密码学的基础 你通过在浏览器中直接运行的动手代码来练习 Cryptology Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Cryptology Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Cryptology Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「质数与因式分解」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Cryptology Academy 课中编写并运行代码吗？
能。每节 Cryptology Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 二进制与十六进制基础
- 模运算基础
- 质数与因式分解
- GCD、欧拉函数与数论入门