Question

在 RSA 算法中，多个 d 是否可以与给定的 e、p 和 q 一起工作？为什么？

在 RSA 算法中，多个 d 是否可以与给定的 e、p 和 q 一起工作？（是否可能有 d 和 u s.t. ed = 1 mod φ(n) 和 eu = 1 mod φ(n)？）为什么？

Answer 1

不存在。

e的选取时，要求φ(n) 和 e互质。在模φ(n) 的情况下，一定存在且只存在一个数，是e的逆元。也就是说，不会存在u、s、t。。。

证明： 

假设对于一个数a，在模p下有两个不同的逆元 a' 和 a''：a*a'=a*a''=1(mod p)；

不妨先设 a' < a'' 且 a'' - a' =k；

由于 a ≠ 0 ，所以 k =0 (mod p).

所以 a’ 与 a''的值相等，即只有一个逆元。