欧拉函数

210 字
1 分钟
欧拉函数

1. 定义#

φ(n)\varphi(n):1∼n1 \sim n 中与 nn 互质的数的个数,φ(1)=1\varphi(1)=1。

  • φ(10)=4\varphi(10)=4:1、3、7、9
  • nn 是质数时,φ(n)=n−1\varphi(n)=n-1

2. 通式#

分解 n=p1a1p2a2⋯pkakn=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k},则

φ(n)=n(1−1p1)(1−1p2)⋯(1−1pk)\varphi(n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_k}\right)

只看有哪些不同的质因子,指数不影响结果。

  • φ(60)=60×12×23×45=16\varphi(60)=60\times\frac12\times\frac23\times\frac45=16
  • φ(360)=360×12×23×45=96\varphi(360)=360\times\frac12\times\frac23\times\frac45=96
  • φ(11413)=φ(101×113)=11413×100101×112113=11200\varphi(11413)=\varphi(101\times113)=11413\times\frac{100}{101}\times\frac{112}{113}=11200

特例:φ(pa)=pa−pa−1\varphi(p^a)=p^a-p^{a-1}。

3. 欧拉定理#

若 gcd⁡(a,n)=1\gcd(a,n)=1:

aφ(n)≡1(modn)a^{\varphi(n)}\equiv 1 \pmod n

pp 为质数时(费马小定理):ap−1≡1(modp)a^{p-1}\equiv 1 \pmod p。

≡\equiv 就是余数相同:15≡1(mod7)15\equiv 1 \pmod 7,因为 15 % 7 == 1。

扩展欧拉定理(降幂):b≥φ(n)b\ge\varphi(n) 时,ab≡ab mod φ(n)+φ(n)(modn)a^b\equiv a^{b\bmod\varphi(n)+\varphi(n)}\pmod n。

4. RSA 里的用法#

n=pq,φ(n)=(p−1)(q−1),ed≡1(modφ(n))n=pq,\qquad \varphi(n)=(p-1)(q-1),\qquad ed\equiv 1\pmod{\varphi(n)}

n = p * q
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)

已知 nn 和 φ(n)\varphi(n) 可反推 p,qp,q:

p+q=n−φ(n)+1,pq=np+q=n-\varphi(n)+1,\qquad pq=n

例:n=11413, φ(n)=11200n=11413,\ \varphi(n)=11200,则 p+q=214p+q=214,解得 p,q=113,101p,q=113,101。

φ(n)\varphi(n) 泄露 = p,qp,q 泄露 = 私钥泄露。

5. 易错点#

  • φ(n)≠n−1\varphi(n)\ne n-1,除非 nn 是质数
  • 指数不影响 φ:φ(210)=512\varphi(2^{10})=512,不是 1023
  • 积性只在互质时成立:φ(24)≠φ(4)φ(6)\varphi(24)\ne\varphi(4)\varphi(6)
  • 连乘时每个括号都要乘
  • 求模逆要求 gcd⁡(e,φ(n))=1\gcd(e,\varphi(n))=1

支持与分享

如果这篇文章对你有帮助,欢迎分享给更多人或打赏支持!

打赏
欧拉函数
https://helloblog.88800001.xyz/posts/six/
作者
Nikki
发布于
2026-10-19
许可协议
CC BY-NC-SA 4.0

评论区

Profile Image of the Author
Nikki
Hello, I'm Nikki.
公告
欢迎来到我的博客!这是一则示例公告。
分类
标签
站点统计
文章
6
分类
3
标签
3
总字数
15,829
运行时长
0 天
最后活动
0 天前
站点信息
构建平台
Cloudflare Workers
博客版本
Firefly v6.14.5
文章许可
CC BY-NC-SA 4.0