欧拉函数计算器

欢迎使用 欧拉函数计算器，这是一个全面的数论工具，可计算 φ(n)（欧拉 phi 函数），并提供分步质因数分解、交互式互质数网格可视化以及深度分析。无论您是在学习抽象代数、准备数学竞赛、研究 RSA 加密，还是探索同余运算，本计算器都能提供专业的计算结果和丰富的教育内容。

什么是欧拉函数？

欧拉函数 φ(n)，也称为 欧拉 phi 函数，用于统计从 1 到 n 之间与 n 互质（相对质数）的正整数个数。当两个数的最大公约数 (GCD) 等于 1 时，它们互质。

例如，φ(12) = 4，因为在从 1 到 12 的整数中，正好有四个数（1, 5, 7 和 11）与 12 互质。

乘积公式

计算 φ(n) 最有效的方法是使用 n 的 质因数分解。如果 \(n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}\)，则：

这意味着我们将 n 乘以 \((1 - 1/p)\)，其中 p 是 n 的每个不同质因数。指数的大小并不重要，只取决于不同的质数。

核心性质

欧拉定理

欧拉定理是使欧拉函数在密码学中变得至关重要的关键结果：

这是 费马小定理（n 为素数的特殊情况）的推广。它构成了 RSA 加密的数学基础。

如何使用本计算器

1. 输入一个正整数： 在输入框中键入 1 到 1,000,000 之间的任何值。
2. 使用快速示例： 点击示例按钮尝试经典值，如素数、合数或 RSA 风格的半素数。
3. 查看结果： 计算器将显示 φ(n)、质因数分解、互质比例和检测到的属性。
4. 探索互质网格： 对于 n ≤ 400 的情况，可以通过动画视觉网格查看哪些数字与 n 互质。
5. 查看趋势图： 观察 φ(k) 在 k = 1 到 min(n, 100) 范围内的变化。

RSA 加密联系

在 RSA 加密 中，欧拉函数起着核心作用：

1. 选择两个大素数 p 和 q。计算 n = p × q。
2. 计算 φ(n) = (p−1)(q−1)。
3. 选择与 φ(n) 互质的公钥指数 e，即 gcd(e, φ(n)) = 1。
4. 计算私钥指数 d，使得 e × d ≡ 1 (mod φ(n))。

RSA 的安全性依赖于在不知道 n 的因式分解的情况下计算 φ(n) 的难度。如果攻击者能高效计算 φ(n)，他们就能破解 RSA。

常见的 φ(n) 值

常见问题解答

什么是欧拉函数？

欧拉函数 φ(n)，也称为欧拉 phi 函数，用于统计从 1 到 n 之间与 n 互质（相对质数）的正整数个数。当两个数的最大公约数 (GCD) 为 1 时，它们互质。例如，φ(12) = 4，因为只有 1, 5, 7 和 11 与 12 互质。

如何计算欧拉函数？

计算 φ(n) 的步骤：(1) 求出 n 的质因数分解。(2) 应用乘积公式：对于 n 的每个不同质因数 p，φ(n) = n × ∏(1 − 1/p)。例如，φ(12) = 12 × (1−1/2) × (1−1/3) = 12 × 1/2 × 2/3 = 4。对于素数 p，φ(p) = p−1。对于素数幂 p^k，φ(p^k) = p^k − p^(k−1)。

为什么欧拉函数在 RSA 加密中很重要？

在 RSA 加密中，模数 n = p × q 是两个大素数的乘积。欧拉函数 φ(n) = (p−1)(q−1) 用于计算私钥：解密指数 d 必须满足 e × d ≡ 1 (mod φ(n))，其中 e 是公钥加密指数。如果没有 φ(n)（需要对 n 进行分解），计算 d 在计算上是不可行的。

什么是欧拉定理，它与欧拉函数有什么关系？

欧拉定理指出，如果 a 和 n 互质，则 a^φ(n) ≡ 1 (mod n)。这是费马小定理（适用于 n 为素数时）的推广。它是同余计算和密码学的基础，为 RSA 加密和高效的模幂运算提供了数学依据。

欧拉函数有哪些主要性质？

主要性质包括：(1) φ(1) = 1。(2) 对于素数 p：φ(p) = p−1。(3) 对于素数幂 p^k：φ(p^k) = p^(k−1)(p−1)。(4) 积性：如果 gcd(m,n) = 1，则 φ(m×n) = φ(m)×φ(n)。(5) 因数和性质：对于 n 的所有因数 d，Σ φ(d) = n。(6) 当 n > 2 时，φ(n) 始终为偶数。

两个数“互质”是什么意思？

如果两个整数 a 和 b 的最大公约数为 1，则称它们互质（也称为相对质数），这意味着它们没有共同的质因数。例如，8 和 15 互质，因为 gcd(8,15) = 1，尽管它们都不是素数。欧拉函数 φ(n) 精确计算了从 1 到 n 之间有多少个整数与 n 互质。

其他资源

• 欧拉函数 - 维基百科
• RSA 加密算法 - 维基百科
• 欧拉定理 - 维基百科