在RSA加密算法中查找p和q

Question

如何在RSA加密算法中知道p和q时的因子为e，d和n。我试图搜索，但找不到任何来源。任何提示，参考或解决方案就足够了。

（e,n)和(d,n)分别n = pq是公钥和私钥

Answer 1

我发现了一个source written in german (page 12+13)，即描述了随机算法计算p和q

算法：。

1. 计算s = max { t : 2t | (ed-1) } and k = (ed-1)/(2s)
2. 选择在[2,n-1]
3. 计算g = gcd(a,n)
4. 如果g > 1 ⇒ g = p和q = n/g随机数a。
   为t = s-1, ... ,0代劳：
   1. g = gcd(ak ⋅ 2t, n)
   2. 如果g < n ⇒ g = p和q = n/g。
      别的选择一个新的随机数a在[2,n-1]并转到3.

如果选择a随机数（均匀分布）的概率找到p和q为1/2，所以它的预计在2次尝试后获得解决方案。

这个工作的证明与chinese remainder theorem有关。

备注：如果您已经私钥，则很可能是没有理由来计算的n的因素，因为应该不会超过一对密钥(e,d)到同一n。但是你可以使用这个算法来证明破坏RSA和n一样困难。 （RSA并不比保理更困难，因为如果您有p和q，您可以简单计算私钥d）。