GCD、欧拉函数与数论入门
将 GCD 和欧拉函数应用于实际密码学问题
GCD、欧拉函数与数论入门 是 CoddyKit 上的免费 Cryptology Academy 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Cryptology Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Cryptology Academy 课程共包含 4 节课。
欢迎
GCD 和欧拉 φ 函数是 RSA 以及许多其他公钥系统中的重要工具。让我们通过示例掌握它们。
最大公因数（GCD）
GCD(a, b) 是能够同时整除 a 和 b 且不产生余数的最大整数。GCD(12, 8) = 4。如果 GCD(a, m) = 1，我们就说 a 和 m 互质。
欧几里得算法
GCD(a, b) = GCD(b, a mod b)，基本情况为 GCD(a, 0) = a。
GCD(48, 18)：
= GCD(18, 12)
= GCD(12, 6)
= GCD(6, 0) = 6
Python：import math; math.gcd(48, 18) → 6
扩展欧几里得算法
扩展版本可以找出满足 ax + by = GCD(a,b) 的整数 x、y。当 GCD(a,m)=1 时，x 就是 a 关于 m 的模逆元。这正是 RSA 计算私钥的方式。
欧拉 φ 函数
φ(n) 统计从 1 到 n 中与 n 互质的整数个数。φ(10) = 4，因为 {1, 3, 7, 9} 与 10 互质。对于任意质数 p，φ(p) = p-1。
乘积的欧拉函数值
对于 RSA：n = p×q（p、q 为质数）。φ(n) = φ(p)×φ(q) = (p-1)(q-1)。
示例：p=5，q=11：φ(55) = 4×10 = 40。
这就是因数分解 n 会破解 RSA 的原因——它会暴露 φ(n)。
欧拉定理
如果 GCD(a,n)=1：a^φ(n) ≡ 1 (mod n)。这是 RSA 解密的数学基础：M = C^d mod n，因为 e×d ≡ 1 (mod φ(n))。
在 RSA 中计算 d
选择 e = 65537（常见的 RSA 公钥指数）。使用扩展欧几里得算法计算 d = e^(-1) mod φ(n)。验证 e×d mod φ(n) == 1。
Python 中的欧拉函数
def totient(n):
from math import gcd
return sum(1 for i in range(1, n+1) if gcd(i, n) == 1)
# Fast for n=p*q:
def rsa_totient(p, q):
return (p-1)*(q-1)
Carmichael λ 函数
现代 RSA 使用 Carmichael λ 函数 λ(n) = lcm(p-1, q-1)，而不是 φ(n)。它提供了一个更小但等价的模数。PKCS#1 v2 和 NIST 都推荐使用 λ(n)。
实际应用总结
GCD：验证 e 与 φ(n) 是否互质。扩展欧几里得算法：计算私钥 d。欧拉函数：确定模幂运算所使用的指数群。这三者都会用于每次 RSA 密钥生成。
快速检查
对于 p=7、q=11 的 RSA，φ(n) 是多少？
回顾
太棒了！GCD、欧几里得算法和欧拉函数现在都已经成为您的工具。接下来，我们将学习 XOR 和按位运算——它们是对称密码的构建基础。
常见问题解答
「GCD、欧拉函数与数论入门」课时是免费的吗？
是的 — 「GCD、欧拉函数与数论入门」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Cryptology Academy 课程的其余内容，请升级到 CoddyKit PRO。 Cryptology Academy 课程共包含 4 节课。
「GCD、欧拉函数与数论入门」这节课中我会学到什么？
将 GCD 和欧拉函数应用于实际密码学问题 你通过在浏览器中直接运行的动手代码来练习 Cryptology Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Cryptology Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Cryptology Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「GCD、欧拉函数与数论入门」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Cryptology Academy 课中编写并运行代码吗？
能。每节 Cryptology Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 二进制与十六进制基础
- 模运算基础
- 质数与因式分解
- GCD、欧拉函数与数论入门