在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）。