如果你问我，哪一种算法最重要？
我可能会回答"公钥加密算法"。
因为它是计算机通信安全的基石，保证了加密数据不会被破解。你可以想象一下，信用卡交易被破解的后果。
进入正题之前，我先简单介绍一下，什么是"公钥加密算法"。
一、一点历史
1976年以前，所有的加密方法都是同一种模式：
（1）甲方选择某一种加密规则，对信息进行加密；
（2）乙方使用同一种规则，对信息进行解密。
由于加密和解密使用同样规则（简称"密钥"），这被称为"对称加密算法"（Symmetric-key algorithm）。
这种加密模式有一个最大弱点：甲方必须把加密规则告诉乙方，否则无法解密。保存和传递密钥，就成了最头疼的问题。
1976年，两位美国计算机学家Whitfield Diffie 和 Martin Hellman，提出了一种崭新构思，可以在不直接传递密钥的情况下，完成解密。这被称为"Diffie-Hellman密钥交换算法"。这个算法启发了其他科学家。人们认识到，加密和解密可以使用不同的规则，只要这两种规则之间存在某种对应关系即可，这样就避免了直接传递密钥。
这种新的加密模式被称为"非对称加密算法"。
（1）乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。
（2）甲方获取乙方的公钥，然后用它对信息加密。
（3）乙方得到加密后的信息，用私钥解密。
如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。
1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。从那时直到现在，RSA算法一直是最广为使用的"非对称加密算法"。毫不夸张地说，只要有计算机网络的地方，就有RSA算法。
这种算法非常可靠，密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长RSA密钥是768个二进制位。也就是说，长度超过768位的密钥，还无法破解（至少没人公开宣布）。因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全。
下面，我就进入正题，解释RSA算法的原理。文章共分成两部分，今天是第一部分，介绍要用到的四个数学概念。你可以看到，RSA算法并不难，只需要一点数论知识就可以理解。
二、互质关系
如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。比如，15和32没有公因子，所以它们是互质关系。这说明，不是质数也可以构成互质关系。
关于互质关系，不难得到以下结论：
1. 任意两个质数构成互质关系，比如13和61。
2. 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10。
3. 如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。
4. 1和任意一个自然数是都是互质关系，比如1和99。
5. p是大于1的整数，则p和p-1构成互质关系，比如57和56。
6. p是大于1的奇数，则p和p-2构成互质关系，比如17和15。
三、欧拉函数
请思考以下问题：
任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）
计算这个值的方法就叫做欧拉函数，以φ(n)表示。在1到8之中，与8形成互质关系的是1、3、5、7，所以 φ(n) = 4。
φ(n) 的计算方法并不复杂，但是为了得到最后那个公式，需要一步步讨论。
第一种情况
如果n=1，则 φ(1) = 1 。因为1与任何数（包括自身）都构成互质关系。
第二种情况
如果n是质数，则 φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。
第三种情况
如果n是质数的某一个次方，即 n = p^k (p为质数，k为大于等于1的整数)，则
比如 φ(8) = φ(2^3) =2^3 - 2^2 = 8 -4 = 4。
这是因为只有当一个数不包含质数p，才可能与n互质。而包含质数p的数一共有p^(k-1)个，即1×p、2×p、3×p、...、p^(k-1)×p，把它们去除，剩下的就是与n互质的数。
上面的式子还可以写成下面的形式：
可以看出，上面的第二种情况是 k=1 时的特例。
第四种情况
如果n可以分解成两个互质的整数之积，
n = p1 × p2
则
φ(n) = φ(p1p2) = φ(p1)φ(p2)
即积的欧拉函数等于各个因子的欧拉函数之积。比如，φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24。
这一条的证明要用到"中国剩余定理"，这里就不展开了，只简单说一下思路：如果a与p1互质(a<p1)，b与p2互质(b<p2)，c与p1p2互质(c<p1p2)，则c与数对 (a,b) 是一一对应关系。由于a的值有φ(p1)种可能，b的值有φ(p2)种可能，则数对 (a,b) 有φ(p1)φ(p2)种可能，而c的值有φ(p1p2)种可能，所以φ(p1p2)就等于φ(p1)φ(p2)。
第五种情况
因为任意一个大于1的正整数，都可以写成一系列质数的积。
根据第4条的结论，得到
再根据第3条的结论，得到
也就等于
这就是欧拉函数的通用计算公式。比如，1323的欧拉函数，计算过程如下：
四、欧拉定理
欧拉函数的用处，在于欧拉定理。"欧拉定理"指的是：
如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立：
也就是说，a的φ(n)次方被n除的余数为1。或者说，a的φ(n)次方减去1，可以被n整除。比如，3和7互质，而7的欧拉函数φ(7)等于6，所以3的6次方（729）减去1，可以被7整除（728/7=104）。
欧拉定理的证明比较复杂，这里就省略了。我们只要记住它的结论就行了。
欧拉定理可以大大简化某些运算。比如，7和10互质，根据欧拉定理，
已知 φ(10) 等于4，所以马上得到7的4倍数次方的个位数肯定是1。
因此，7的任意次方的个位数（例如7的222次方），心算就可以算出来。
欧拉定理有一个特殊情况。
假设正整数a与质数p互质，因为质数p的φ(p)等于p-1，则欧拉定理可以写成
这就是著名的费马小定理。它是欧拉定理的特例。
欧拉定理是RSA算法的核心。理解了这个定理，就可以理解RSA。
五、模反元素
还剩下最后一个概念：
如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。
这时，b就叫做a的"模反元素"。
比如，3和11互质，那么3的模反元素就是4，因为 (3 × 4)-1 可以被11整除。显然，模反元素不止一个， 4加减11的整数倍都是3的模反元素 {...,-18,-7,4,15,26,...}，即如果b是a的模反元素，则 b+kn 都是a的模反元素。
欧拉定理可以用来证明模反元素必然存在。
可以看到，a的 φ(n)-1 次方，就是a的模反元素。
==========================================
好了，需要用到的数学工具，全部介绍完了。RSA算法涉及的数学知识，就是上面这些，下一次我就来介绍公钥和私钥到底是怎么生成的。
（完）
bigeagle 说：
建议公式用透明背景看着舒服些，mathjax更好～
// mod 作为运算符不该用斜体呀，强迫症犯了
2013年6月27日 22:35 | # | 引用
roywoo 说：
欧拉这位数学家真的很厉害
2013年6月27日 23:31 | # | 引用
Du 说：
峰哥的技术文章写的总是这么深入浅出，大赞
2013年6月28日 03:48 | # | 引用
小白 说：
记得看到说1024位也不安全了，估计已经或者接近被破解了。
而且政府和法院可以命令企业提供私钥的吧。
2013年6月28日 11:05 | # | 引用
danny 说：
快点出二！我正期待这类文章呢！
2013年6月28日 15:15 | # | 引用
Frank 说：
建议使用 MathJax，浏览器中显示数学公式会好看得多。样例： http://www.mathjax.org/demos/mathml-samples/。
2013年6月28日 21:53 | # | 引用
chaoc 说：
期待下一篇。楼主很专业。希望马上看到楼主的下一篇。
2013年6月29日 11:55 | # | 引用
米格 说：
很喜欢、很佩服你讲解技术的方式，深入浅出，娓娓道来。也很喜欢你的博客网站的风格，朴素但是有内容，非常实在。
顺便请教一下，你的博客是采用哪个平台呢？还是自己开发的？就像你的关于github和Jekll搭建博客的文章，你的博客也是按照这个方式组织的吗？
谢谢！
2013年6月30日 00:01 | # | 引用
稀饭 说：
＂这是因为只有当一个数不包含质数p，才可能与n互质。而包含质数p的数一共有p^(k-1)个，即1×p、2×p、3×p、...、p^(k-1)×p，把它们去除，剩下的就是与n互质的数。＂
虽然很容易推导，但是这句话这样说应该是有逻辑问题。前面是＂可能＂，后面是＂就是＂。
2013年7月 1日 00:45 | # | 引用
Jak Wings 说：
欧拉定理找本高等数学的书就能知道了，的确有点复杂，感觉不必在这里详细介绍，囧。
我以前也写过一篇简单的笔记：http://jakwings.is-programmer.com/posts/29107.html
公钥和私钥的来源简单来说就是下面这样吧，当然具体是怎么把它们复杂化我就不清楚了，希望下次你能详细讲到。:)
公钥：w, n
私钥：p, q, Φ(n), d
2013年7月 1日 12:08 | # | 引用
malasang 说：
深入浅出，我当时做网络安全的时候还专门研究了这个东西呢，现在忘了很多，不过看起来依然很亲切。
2013年7月 2日 13:15 | # | 引用
银色Blues 说：
早上查看微信,看到推荐的这篇文章.下午查询https相关知识,又来到博主这里,实在是太巧了.
谢谢楼主的分享,非常详细,很是受用.
2013年7月 5日 17:32 | # | 引用
Viko 说：
有点疑问
第五种情况中 “再根据第3条的结论，得到”使用第3条的条件应为“P(k1,1)为质数的某一个次方，且次幂大于1”，即P(k1,1)不是质数
但第五条的题设是“因为任意一个大于1的正整数，都可以写成一系列质数的积。”
则P(k1,1)为质数，与第三条的条件不符，不能用第三条吧？
2013年7月 5日 22:03 | # | 引用
Viko 说：
再看了一下感觉欧拉函数中第三条“k为大于1的整数”可以改为“k为大于或等于1的整数”
2013年7月 5日 22:19 | # | 引用
阮一峰 说：
To Viko:
谢谢指出，已经改过来了。
2013年7月 6日 06:44 | # | 引用
hilojack 说：
您好博主，对于第四种情况，我也有点疑问：
"由于a的值有φ(p1)种可能，b的值有φ(p2)种可能，则数对 (a,b) 有φ(p1)φ(p2)种可能，而c的值有φ(p1p2)种可能，所以φ(p1p2)就等于φ(p1)φ(p2)。"
这里我不太理解的是，9与8是互质的：
φ(8)有4种a可能：1 3 5 7
φ(9)有6种b可能:1 2 4 5 7 8
φ(8*9) = φ(72)真的有24(4*6)种c(对应[a,b])可能吗？
如果取a=3 b=2 而c=a*b=3*2=6 并非是8×9=72的互质数呀
2013年7月 9日 21:21 | # | 引用
holys 说：
风格是stylesheet决定的, 内容是作者的, 与平台何关呢?
2013年7月10日 15:40 | # | 引用
阮一峰 说：
To hilojack:
c 是（a，b）的函数，但不一定等于 a*b ，比如c可以等于2a+b。
2013年7月10日 18:46 | # | 引用
shyixiu 说：
我想请问，因为e和d都非常大，那对于加解密的幂运算取模是不是速度都很慢呢？
2013年7月11日 11:14 | # | 引用
软件局局长 说：
没完全看懂，看来我得再加强理论学习。
2013年7月17日 09:32 | # | 引用
xfq 说：
有点疑问
第三种情况中说“只有当一个数不包含质数p，才可能与n互质”，这个好理解，但是为什么把它们去除后，剩下的就是与n互质的数呢？
2013年7月22日 21:58 | # | 引用
huaxingmaster 说：
这个情况是针对n=p^k形式，n只包含质因子p，如果一个数不包含质因子p，那显然不会和n有共同的质因子，当然互质了
2013年8月16日 13:37 | # | 引用
赵三 说：
“因此，7的任意次方的个位数（例如7的222次方），心算就可以算出来”
7的222次方=7的2次方*7的（4*55）次方，下面该怎么算呢？谢谢~
2014年1月 2日 13:55 | # | 引用
any 说：
7的2次方个位数9, 7的（4*55）次方 个位数1（1^55） 9×1=9
2014年1月 2日 16:09 | # | 引用
gk 说：
我高等数学中没有这个欧拉定理啊，欧拉定理有很多。看了这篇文章我才知道费马小定理原来是欧拉定理中的特殊情况，真高端！
2014年2月18日 21:08 | # | 引用
zhangyuqin 说：
图片大多数挂掉了！
2014年3月 3日 11:15 | # | 引用
刘婷 说：
我是今年的应届毕业生，毕业论文就是关于RSA算法的，在网页上看到阮先生的这篇文章，受益匪浅。因为本身对于数学并不擅长，希望可以借鉴一下阮先生的这篇文章。希望能够得到您的许可。
2014年3月 5日 10:43 | # | 引用
Seraph256 说：
谢谢一峰！想了解 RSA 很长时间了，一直不得要领，今天看到了这篇文章和后续的（二），马上看完记笔记，醍醐灌顶，受益匪浅！
谢谢一峰！
2014年3月18日 17:02 | # | 引用
Dude 说：
现在都有人急着用2048了。当然量子计算机一出现RSA就是浮云了。
2014年5月13日 14:38 | # | 引用
Z10 说：
已经看晕了.
2014年7月 3日 10:44 | # | 引用
Z00 说：
公式图片好像都不显示了...
2014年10月15日 10:55 | # | 引用
C860 说：
你好，这篇文章的图片貌似都挂掉了，影响了阅读质量哦。
2014年10月17日 10:11 | # | 引用
Asn 说：
那如果该数不是某个质数的次方呢，即不符合第三种情况的条件呢？根据3和5推出的式子还成立么(。・д・。)。
PS：感谢博主的耐心解释~(・∀・)~
2014年10月18日 18:09 | # | 引用
王发康 说：
公式不显示啦~~~~
2014年11月24日 14:03 | # | 引用
Rigg在路上 说：
图挂啦~~
2014年11月26日 22:31 | # | 引用
Rigg在路上 说：
我有直觉，只要翻墙那些图就会出来
2014年11月27日 13:30 | # | 引用
Rigg在路上 说：
刚试了一下，翻墙后确实出来了
昨天晚上看到最后，最关键的地方，结果图全部都是X
现在才看到，有种非常不爽的感觉。
2014年11月27日 13:40 | # | 引用
亮黑色书脊 说：
用8192bit是不是丧心病狂的表现
2014年12月12日 06:09 | # | 引用
WT 说：
阮哥，为什么图片没有了
2015年1月24日 13:19 | # | 引用
clpszpp 说：
图片在这个网站上，http://chart.googleapis.com/chart，看到URL中的google你就知道为什么了
2015年2月 3日 18:07 | # | 引用
jeffyang 说：
>> 任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）
计算这个值的方法就叫做欧拉函数
--
>> 如果n是质数，则 φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。
这两处定义出入
2015年2月13日 22:05 | # | 引用
谢飞 说：
太棒了！很有心得！感谢分享！
2015年3月16日 06:01 | # | 引用
出体 说：
看了感觉可以 不错的文章
2015年3月18日 13:52 | # | 引用
eomer 说：
天朝上国！悲哀
2015年4月 1日 11:06 | # | 引用
adele 说：
欧拉定理的公式看不到了！_(:з」∠)_
2015年4月 2日 22:57 | # | 引用
小白 说：
看着看着就晕了的飘过
2015年4月 8日 15:25 | # | 引用
waldenpond 说：
发明非对称加密的科学家 好像甘道夫
2015年4月26日 09:11 | # | 引用
gxin 说：
果然需要翻墙才能看图片。好文章赞一个。
2015年5月25日 16:23 | # | 引用
冒菜 说：
下次再来继续看。。。
2015年6月 6日 10:04 | # | 引用
lenina 说：
今天在看到，原来早在1973年和RSA等效的算法已经被一个英国情报部门工作的数学家Clifford Cocks弄出来了，只是由于工作性质，知道1997年他的这部分工作才解密，4年后RSA三人才独立重新发明这个算法，还是Whitfield Diffie 和 Martin Hellman两个人的前期工作下（而这两人的“前期”工作也后于Clifford Cocks），这样Cocks的工作虽然没有直接带来革命，但作为一个数学家的成就，还有这个故事本身的趣味性，感觉都值得一提，如果阮先生以后要更新这篇文章或者RSA相关内容的不妨看看
2015年8月 3日 16:37 | # | 引用
钱俊 说：
看来你的文章，对RSA算法讲解很到位，准备在公司培训采用你的资料，谢谢你。
2015年8月22日 22:42 | # | 引用
N 说：
_(:зゝ∠)_ 看《离散数学》看到这里，不太明白，谢谢博主的文章
2015年9月29日 21:21 | # | 引用
Jasper 说：
条理很清晰，十分感谢！！
2015年10月 4日 16:09 | # | 引用
wuxinliulei 说：
图挂了
2016年1月21日 18:47 | # | 引用
gxy 说：
阮哥，既然这个私钥那么重要，那么在开发中怎样保护私钥呢？
2016年3月18日 14:35 | # | 引用
apple 说：
要翻墙可以把图片显示出来。。翻墙怎么办？自己想办法
2016年3月30日 09:37 | # | 引用
Hanse 说：
讲得真好，本来以为加密都是高大上的东西，原来核心原理并不复杂，再次感慨数学的神奇！
2016年4月22日 12:29 | # | 引用
冲浪板 说：
有人说量子计算机出现将使得它失效,可是他没想到,量子计算机同样可以出题目,它算出来的题目,它自己解起来要多久....
2016年5月 2日 17:40 | # | 引用
ddc 说：
有一个相关的问题，publickey 和 publickey token 是否有对应关系，或者通过某个工具可否查看两者是否匹配？
2016年5月15日 22:25 | # | 引用
jack 说：
第二种情况：
“而包含质数p的数一共有p^(k-1)个，即1×p、2×p、3×p、...、p^(k-1)×p，把它们去除，剩下的就是与n互质的数”
这里有错误，有p^(k-1)个质数是对的，但是1×p、2×p、...应该是p、p^2...
2016年5月30日 17:42 | # | 引用
acerpeanut 说：
包含质数p的数，也就是说p是这个数的因数。毫无疑问，p都是1*p, 2*p, 3*p的因数。所以原文并没有错。
2016年6月15日 10:13 | # | 引用
alert 说：
因为任意一个大于1的正整数，都可以写成一系列质数的积。
上面这句话是错的吧、
一个大于1的正整数7怎么写成一系列质数的积啊，1不是质数也不是合数
2016年8月27日 11:03 | # | 引用
Jerry 说：
写了太好了，比我们教授讲了清楚，哈哈
2016年10月26日 22:21 | # | 引用
陈玩玩 说：
这学期开了密码学的课程，正学到RSA这里，围观一峰大大的日志=w=
2016年11月27日 00:30 | # | 引用
赵兴君 说：
师兄，你好。后面部分你给出的算式是用图片表示的。但是我无法打开图片。我用过几部设备打开网页都是无法打开的。希望能得到师兄的帮助，谢谢师兄
2016年11月28日 09:54 | # | 引用
何怡 说：
好多图片看不见了=，=
马下来作者以后修复了重新看
2016年12月22日 13:53 | # | 引用
陈大东 说：
条理好清晰
配上图片 好容易理解
比起教科书好太多
感谢
2017年1月 7日 16:41 | # | 引用
陈大东 说：
想看到完整的公式
翻了墙还是看不到 图片
明明写得很好的
2017年1月 7日 17:17 | # | 引用
王超 说：
很烦躁，图片都看不到，哎
2017年3月31日 09:39 | # | 引用
CSHwang 说：
p^k / 2p = p^(k-1) / 2
p^(k-1)/2 不是整数，所以2p不是因数
2017年4月19日 09:06 | # | 引用
riophae 说：
感觉这句话：
这是因为只有当一个数不包含质数p，才可能与n互质
改为：
这是因为只有当一个数的因数不包含质数p，才可能与n互质
更明白一些
2017年5月19日 09:54 | # | 引用
lc 说：
最上面的图中大牛好像东邪黄药师
2017年5月31日 18:05 | # | 引用
萌 说：
有没有人能简单易懂的说一下这个的意义！
2017年8月11日 12:28 | # | 引用
kkkkk 说：
在了解RSA算法之前，还是要先了解一下如何求最大公约数的吧http://www.jianshu.com/p/bbca651ed5bb 欧几里得算法的应用：RSA的加密解密
2017年8月27日 12:49 | # | 引用
lake 说：
思路清晰，文笔简练，可惜图片load不到，峰哥要不试试七牛的服务吧
2017年11月13日 10:06 | # | 引用
Panda 说：
图片没有了
2017年12月27日 10:49 | # | 引用
a 说：
公式图片没有了，我在下面这里看的
https://www.cnblogs.com/hiflora/archive/2013/07/04/3171775.html
2018年1月29日 19:42 | # | 引用
Mark 说：
图片全挂了
2018年5月15日 10:17 | # | 引用
王 说：
m与n不互质时，m=kpq不行么，或者甚至说m=n这种情况呢。再或者说文中说以m=kp为例，如果k碰巧为q，那么“m与q必然互质”的说法不就不对了么？
2018年7月31日 13:35 | # | 引用
周海汉 说：
m必须小于n，否则会解密失败。
所以m也不会在k大于1时，等于kpq。
设m=kp, k必然小于q。由于q为质数，所以k必然和q互质。
2018年11月13日 18:15 | # | 引用
xzw 说：
1和2互质，那么2^φ(1)≡1(mod 1) 其中φ(1)=1，即得到 2^1%1=0 这与源等式不一致啊，为啥？
2018年12月12日 16:39 | # | 引用
江东小白板 说：
一峰哥 能否更新一下图片 图片显示不了
2019年6月 4日 00:19 | # | 引用
linw 说：
博主你好，你的博客图片都挂了，最近梯子限制得厉害，翻不了墙，能否修改一下
2020年3月29日 21:54 | # | 引用
RLWS 说：
7的4次方个位数一定是1理解了,但
7的任意次方的个位数（例如7的222次方），心算就可以算出来
为啥呢?
为啥呢?
为啥呢?
2020年4月 9日 14:34 | # | 引用
李京潼 说：
博客中的图片看不到了。。。
2020年5月 6日 17:46 | # | 引用
路人J 说：
因为根据定理可以得出7的220次方（200可以被4整除）个位数一定是1，然后再乘以7再乘以7，得到最后一位是9
2020年5月31日 21:28 | # | 引用
payne 说：
大佬，博客里的图片显示不出来了
2020年6月11日 10:11 | # | 引用
wind315 说：
文章中“3. 如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。”
这个不成立吧？比如，21，17，21就不是质数?还是我对这句话理解有误？？
2020年8月24日 16:11 | # | 引用
X_x 说：
21不是质数啊3、7。较大的数是质数，如果一个数小于它，那除了1以外，其他数不是和它互质吗
2020年8月28日 11:31 | # | 引用
Lotus 说：
切比雪夫，有兴趣看质数数论的不容错过
2020年9月16日 12:08 | # | 引用
robin 说：
文章中的图片都显示不出来，影响阅读和理解，希望阮大佬更新一下
2020年10月23日 15:16 | # | 引用
对饮 说：
最近在看《信息论》，可一拿起书，就看不进去，前几章好枯燥
2020年12月14日 17:40 | # | 引用
Learner 说：
有些重要的图片看不了了，希望老师可以更新一下
2021年6月14日 22:24 | # | 引用
暮光 说：
梯子可以看到图片
2021年6月30日 11:31 | # | 引用
图班龙格 说：
RSA算法原理（二）传送门：
//www.greatytc.com/blog/2013/07/rsa_algorithm_part_two.html
2021年9月30日 20:11 | # | 引用
cw 说：
已知 φ(10) 等于4，所以马上得到7的4倍数次方的个位数肯定是1。
70^20最后一位不是1啊
2021年10月12日 16:59 | # | 引用
dogtor doggo 说：
欧拉函数totient function的第四种情况，用容斥原理可以比较清楚点解释.
2022年2月18日 01:52 | # | 引用
lxq 说：
确实这里说法有问题，改成“如果一个数的因子包含质数p，那么就不与n互质”就好了，不过这里也没解释为什么“只有当一个数的因数不包含质数p，才会与n互质”
2022年4月10日 21:44 | # | 引用
若微fly 说：
看了很多关于私钥和公钥的文章，都一头无数。这篇是最清晰的，解决了我的困惑，谢谢！
2022年4月29日 13:52 | # | 引用
灰尘疾客 说：
作者大哥，文中一些图片链接挂了，我访问不了（网络环境：广东电信）
2023年9月 2日 17:39 | # | 引用
旅行者 说：
太厉害了，就是有些图看不了有些可惜。
2023年9月30日 16:11 | # | 引用