Eulers-Totient-Rechner

原理

欧拉函数 φ(n) 统计 1 到 n 中与 n 互素的整数个数。它是模运算的基石：欧拉定理 a^φ(n) ≡ 1 (mod n)（gcd(a,n)=1）是 RSA 公钥体制的核心引理。计算用公式 φ(n) = n·∏(1 − 1/p)，p 取遍 n 的素因子——试除分解后一步得出。

关键性质：素数 p 有 φ(p) = p−1；φ 是积性函数，gcd(m,n)=1 时 φ(mn) = φ(m)φ(n)；约数和恒等式「对 n 的每个约数 d，φ(d) 之和等于 n」（如 n = 12：φ(1)+φ(2)+φ(3)+φ(4)+φ(6)+φ(12) = 1+1+2+2+2+4 = 12）。

使用步骤

① 输入正整数 n；② 得到 φ(n)、比值与素因数分解；③ 比值 φ(n)/n 越小，n 的素因子越多越「光滑」。

计算示例

φ(100) = 40（100 = 2²×5²，100×1/2×4/5 = 40）；φ(97) = 96（素数）；φ(123456789) = 82260072（123456789 = 3²×3607×3803，φ = 6×3606×3802）。

注意事项

φ(n) 对偶数 n 总有 φ(2m) = φ(m)·[m 奇 ? 1 : 2]。RSA 中选 e 需 gcd(e, φ(n)) = 1；卡迈克尔函数 λ(n) 是使 a^k ≡ 1 对所有 a 成立的最小指数，与 φ(n) 不同（λ(8) = 2 而 φ(8) = 4）。

常见问题

Q：φ(n) 可以等于 φ(n+2) 吗？A：可以，n = 14 与 16 都给出 6（ Lehmer 猜想则断言 φ(n) | n−1 的合数解不存在，至今未决）。

Q：为什么 RSA 安全性与 φ 相关？A：已知 n = pq 时 φ(n) = (p−1)(q−1)，反过来由 φ(n) 与 n 可解出 p、q——计算 φ 等价于分解大数，这正是难题所在。