分解算法ññN給定ññN,和和e,ddd
我有一個 RSA 公鑰（公共模數 $ N $ 和公共指數 $ e $ ) 和私有指數 $ d $ 的匹配私鑰。
我該如何計算 $ p $ 和 $ q $ , 的質數因子 $ N $ ?
算法
RSA 模數 $ N $ 給定任何非零倍數，可以分解大不同素數的乘積 $ f $ 的 $ \lambda(N) $ （在哪裡 $ \lambda $ 是Carmichael 函式），或 $ (N,e,d) $ 產生這樣的 $ f $ 作為 $ f\gets e,d-1 $ ， 如下：
- 表達 $ f $ 作為 $ 2^s,t $ 和 $ t $ 奇怪的
- 放 $ i\gets s $ 和 $ a\gets2 $
- 計算 $ b\gets a^t\bmod N $ ， 而如果 $ b=1 $ 然後
- 放 $ a $ 到下一個素數，並在 3 處繼續
- 如果 $ i\ne1 $ 然後
計算 $ c\gets b^2\bmod N $ ， 而如果 $ c\ne1 $ 然後
- 放 $ b\gets c $ ， 減少 $ i $ ，並在 4 處繼續
- 如果 $ b=N-1 $ 然後
- 放 $ a $ 到下一個素數，並在 3 處繼續
- 計算和輸出 $ p\gets\gcd(b-1,N) $ ， 和 $ q\gets N/p $ .
對於標準 RSA，其中 $ N $ 有兩個不同的因素，我們已經充分考慮了 $ N $ . 否則， $ p $ 或/和 $ q $ 不會是素數，只需從第 2 步重新執行算法替換 $ N $ 由任何仍然未分解的組件，直到所有的主要因素 $ N $ 已被拉出。
理由
在 RSA 上下文中， $ N $ 有不小的質因數，因此算法的 $ a $ 在第 3 步將保持足夠小， $ \gcd(a,N)=1 $ 將保持（如果沒有， $ a $ 將是一個因素 $ N $ 由審判庭發現；算法的一個簡單的修改額外處理 $ N $ 有這麼小的因素）。
對於任何有效的 RSA 三元組 $ (N,e,d) $ , 它認為 $ \left(a^e\right)^d\bmod N=a $ 對於任何整數 $ a $ 在 $ [0,n) $ （因為教科書 RSA 解密有效）。
因此對於任何 $ a $ 在算法中使用， $ a^{e,d-1}\bmod N=1 $ 成立，即 $ a^f\bmod N=1 $ 為了 $ f $ 步驟 1。
這 $ t $ 和 $ s $ 步驟 1 是唯一定義的，與 $ s>0 $ ， 和 $ \left(a^t\right)^{\left(2^s\right)}\bmod N=1 $ .
對於大多數 $ N $ ，第 3 步將很快找到一個 $ a $ 和 $ a^t\bmod N\ne1 $ . 論據：因為 $ N $ 是平方 自由, 根據 中國剩餘 定理, $ a $ 與 $ N $ 在第 3 步被拒絕當且 $ a^t\bmod p=1 $ 對於所有素數 $ p $ 劃分 $ N $ . 自從 $ t $ 是奇數，如果 $ a^t\bmod p=1 $ 為 $ a $ ， 然後 $ \tilde a^t\bmod p=p-1\ne1 $ 為了 $ \tilde a=-a\bmod p $ . 因此對於 $ a $ 與 $ N $ 在某個大區間內隨機選擇，機率 $ a^t\bmod p=1 $ 是 $ \le\frac12 $ . 這對於每個人來說都是獨立的 $ p $ ， 因此 $ a^t\bmod N\ne1 $ 有機率 $ \ge1-2^{-m} $ 在哪裡 $ m\ge2 $ 是因子的數量 $ N $ . 使用連續素數 $ a $ （而不是隨機的 $ a $ ) 在實踐中對於問題的隨機實例效果很好（我沒有證據，可能需要擴展黎曼假設）。
在第 4 步的每次迭代之前，它成立 $ 1<b<N $ ， 和 $ i\ge1 $ ， 和 $ b^{\left(2^i\right)}\bmod N=1 $ ; 因此至多之後 $ s-1 $ 第 4 步中的計算我們到達第 5 步 $ b\bmod N\ne1 $ 和 $ b^2\bmod N=1 $ .
步驟 5 排除案例 $ b=N-1 $ ，這在實踐中很少見（我正在尋找一個論點）。
因此在第 6 步， $ \gcd(b-1,N) $ 是一個重要的因素 $ N $ .
參考
最初的 RSA 論文中暗示了類似的算法：Ronald L. Rivest、Adi Shamir 和 Leonard Adleman，A Method for Gaining Digital Signatures and Public-Key Cryptosystems，CACM 1978；見第 IX-C 節的最後兩段。在STOC 1975 的訴訟程序中，它使用並引用了 Gary L. Miller 的Riemann’s Hypothesis and tests for primality中的素性檢驗證明。
Alfred J. Menezes、Paul C. van Oorschot 和 Scott A. Vanstone 的應用密碼學手冊，CRC Press 1997中有更詳細的說明；見第8.2.2 (i)節最後一段。
該答案的算法因使用增量素數而有所不同 $ a $ 而不是隨機的 $ a $ . 這使得算法具有確定性（而不是其執行時），並且在實踐中執行良好。順便說一句，步驟 4 中計算的模平方的數量通過使用 $ i $ 而不是額外的最後一格。
注意：更簡單的變化僅限於 $ b=a^t\bmod N $ 或者 $ b=a^{f/2}\bmod N $ ，但需要更多的測試 $ a $ 什麼時候 $ s $ 很大，偶爾會發生。一些理由假設 $ d=e^{-1}\bmod\varphi(N) $ 或者 $ e,d\equiv1\pmod{\varphi(N)} $ ，這在現代 RSA 中並不始終成立：對於FIPS 186-4，其機率小於 $ \frac1 3 $ ， 因為 $ d=e^{-1}\bmod\operatorname{lcm}(p-1,q-1) $ 是必須的。
對於（不同的）確定性多項式時間算法，請參閱JoC 2007中的 Jean-Sebastien Coron 和 Alexander May 的Deterministic Polynomial Time Equivalence of Computing the RSA Secret Key and Factoring。