encryption - 在RSA加密算法中，如果我们有N个，我们能找到P和Q吗？

Question

Totient(N)是(P-1)(Q-1)和(P-1)的乘积，(Q-1)取1后不会是素数，可以得到多个因数？这是真的吗？或者如果我们有 N 的全部，我们能找到 P 和 Q 吗？

标签： encryptionnumbersrsacomputation-theorynumber-theory

Answer 1

因为只有偶素数是 2，所以其余素数都是奇数。因此 $p-1$ 是一个偶数，它至少可以有 2 作为除数。

对于您的问题的第二部分；你所做的是玩方程式；

φ(n)=(p-1)(q-1)=pq-p-q+1=(n+1)-(p+q)

(n+1)-φ(n)=p+q

(n+1)-φ(n)-p=q

和 n=pq 来获得这个二次公式。

p2−(n+1−φ(n))p+n=0

有关更多详细信息和示例，请参阅；为什么在 RSA 中将 phi(n) 保密很重要？