Rsa
兩個特定素數乘積的因式分解
請幫幫我。
考慮特定的素數 $ p = x^{d} + 1 $ 和 $ q = x^{e} + 1 $ 對於一些 $ x, d, e \in \mathbb{N} $ . 可以他們的產品 $ n = pq $ 比一般素數的乘積更快？換句話說，有沒有更適合這種情況的分解算法 $ p $ , $ q $ 比一般形式素數的最先進算法？
預先感謝您的回复。
換句話說，有沒有更適合這種情況的分解算法 $ p, q $ 比一般形式素數的最先進算法？
如果你知道 $ n $ 是形式 $ (x^d+1)(x^e+1) $ ，分解應該是微不足道的。
$ n = x^{d+e} + x^d + x^e + 1 \approx x^{d+e} $ （除非 $ x^d $ 或者 $ x^e $ 是小）。我們可以輕鬆瀏覽可能的值 $ \sqrt[d+e]{n} $ 對於各種可能的值 $ d+e $ , 並找到一個接近整數值的 $ x $ ; 這給了我們 $ x $ 和 $ d+e $ ; 此時，我們知道 $ n - (x^{d+e} + 1) = x^d + x^e $ ，從這裡開始，恢復 $ d $ 和 $ e $ 簡單。
如果（說） $ x^d $ 很小，然後簡單搜尋小因素（無論是蠻力還是如果你想花哨，ECM）將很快找到 $ x^d+1 $
還有其他策略來考慮因素 $ n $ 這種形式的底線：可能的值太少了 $ x, d, e $ 使這甚至有點困難。