一个数学问题，关于 RSA 里的 e 的问题。

理论上随便选都可以。但是随便选的作为幂有可能会导致计算量太大。
PEM 建议用 3 ，X.509 建议用 65537 ，PKCS#1 建议用两者之一。

数学上无所谓，代码里要用到中国剩余定理，那就只能选特定的 e

随便选的
https://en.wikipedia.org/wiki/65,537

65537 is commonly used as a public exponent in the RSA cryptosystem. Because it is the Fermat number Fn = 22n + 1 with n = 4, the common shorthand is "F4" or "F4".[3] This value was used in RSA mainly for historical reasons; early raw RSA implementations (without proper padding) were vulnerable to very small exponents, while use of high exponents was computationally expensive with no advantage to security (assuming proper padding).[4]

随便选，条件是 1 < e < λ(n) 并且 e 和 λ(n) 互质

@rabbbit 就这个条件完全搞不明白…… 究竟是要计算出来还是随便找个小于 φn 的质数。


@tool2dx 中国剩余定理？

不懂，我以为就是随便选了个质数。
看看这里，也许有帮助。

https://en.wikipedia.org/wiki/RSA_(cryptosystem)

e having a short bit-length and small Hamming weight results in more efficient encryption the most commonly chosen value for e is 216 + 1 = 65537. The smallest (and fastest) possible value for e is 3, but such a small value for e has been shown to be less secure in some settings.

谁能讲讲这个 small Hamming weight 的作用？

@rabbbit 哎，不仅数学不会，English 还不懂，咱果然不适合研究这么深奥的学问。

看了半天，我的理解是，一个小于 φn 且是相对小的数。
但是不知道这是不是正确的理解。

，

=
11
p=11 和

=
19
q=19 ，所以：


(

)
=
(


1
)
(


1
)
=
(
11

1
)
(
19

1
)
=
10
×
18
=
180
(n)=(p1)(q1)=(111)(191)=10×18=180

p = 11;
q = 19;
n = p * q;
phiN = (p - 1) * (q - 1);
e = 7;
GCD[e, phiN]

验证 7 和 180 互质性：
gcd(7,180)=1

@James2099 所以这个 7 究竟是怎么来的，是随便从小于 phiN 的质数里找一个呐，还是需要计算出来一个质数呐。

一般都先从 65537 ，如果 65537 不满足验证条件就从小的质数开始，比如 3 。

可以看一下这一节： https://datatracker.ietf.org/doc/html/rfc8017#section-3.1

写的很清楚：「一个有效的 RSA 公钥中，RSA 模数 n 是 u 个不同奇素数 r_i 的乘积，i = 1, 2, ..., u ，此处 u >= 2 ，而 RSA 公钥指数 e 是一个介于 3 和 n - 1 之间的整数，满足 e 与λ(n)的最大公约数为 1 ，其中λ(n) = r_1 - 1, ..., r_u - 1 的最小公倍数。按照惯例，前两个素数 r_1 和 r_2 也可以分别表示为 p 和 q 。」

@saranz
https://totct.com/article/modern-cryptography/

e 随便取的，比 n 小 并且与φn 互素就行了。
这种算法实际上没啥用，教科书式算法，你会发现 p 和 q 的位数稍微大一点就因数分解不出了。
如果我没记错的话，p = random_prime(2^(k/2))，这里的 k 到 270 左右就很难解了