1. 定义#
φ(n):1∼n 中与 n 互质的数的个数,φ(1)=1。
- φ(10)=4:1、3、7、9
- n 是质数时,φ(n)=n−1
2. 通式#
分解 n=p1a1p2a2⋯pkak,则
φ(n)=n(1−p11)(1−p21)⋯(1−pk1)
只看有哪些不同的质因子,指数不影响结果。
- φ(60)=60×21×32×54=16
- φ(360)=360×21×32×54=96
- φ(11413)=φ(101×113)=11413×101100×113112=11200
特例:φ(pa)=pa−pa−1。
3. 欧拉定理#
若 gcd(a,n)=1:
aφ(n)≡1(modn)
p 为质数时(费马小定理):ap−1≡1(modp)。
≡ 就是余数相同:15≡1(mod7),因为 15 % 7 == 1。
扩展欧拉定理(降幂):b≥φ(n) 时,ab≡abmodφ(n)+φ(n)(modn)。
4. RSA 里的用法#
n=pq,φ(n)=(p−1)(q−1),ed≡1(modφ(n))
已知 n 和 φ(n) 可反推 p,q:
p+q=n−φ(n)+1,pq=n
例:n=11413, φ(n)=11200,则 p+q=214,解得 p,q=113,101。
φ(n) 泄露 = p,q 泄露 = 私钥泄露。
5. 易错点#
- φ(n)=n−1,除非 n 是质数
- 指数不影响 φ:φ(210)=512,不是 1023
- 积性只在互质时成立:φ(24)=φ(4)φ(6)
- 连乘时每个括号都要乘
- 求模逆要求 gcd(e,φ(n))=1