當模數為形式時打破 RSAñ=pq_ñ=pqN = pq和|q2-p||q2−p||q^2 - p|小的

我需要一些關於如何解決以下 RSA 問題的見解：

從 RSA 加密方案中，您知道生成 RSA 模數的算法 $ N $ 總是輸出形式的模數 $ N = pq $ 這樣的區別 $ q^2 $ 和 $ p $ 不大於 $ 2^8 $ 在絕對值。

我的問題是：我應該嘗試考慮因素嗎？ $ N $ ? 如果是這樣，我應該使用哪種方法？

這個問題有點相關。

編輯：

解決 $ q $ ， 我有這個 $ q $ 在平方根之間 $ p-2^8 $ 和平方根 $ p+2^8 $ .

注意： Ilmari Karonen 的方法幾乎在每個方面都優於我的方法：它很好地概括了更大的 $ \lvert q^2-p\rvert $ ，它更容易實現（沒有多項式分解），並且在計算量方面非常輕量級。

---

讓 $ p=q^2+\delta $ , 這樣 $ \lvert\delta\rvert\leq 2^8 $ . 因此，

$$ N=pq=(q^2+\delta)q=q^3+\delta q \text. $$ 所以 $ q $ 是多項式的根 $ f:=X^3+\delta X-N\in\mathbb Z[X] $ ，並且由於 $ \delta $ 從小集合中選擇 $ {-2^8,\dots,2^8} $ 你可以遍歷所有可能的值 $ \delta $ 並嘗試考慮 $ f $ 直到你找到 $ q $ . 例如，在 中sage，您可以使用以下程式碼：

R.<X> = ZZ[]
for d in range(-2**8, 2**8+1):
   xs = factor(X ** 3 + d * X - N)
   if xs[0][0].degree() == 1 and not N % xs[0][0][0]:
       print('q = {}'.format(-xs[0][0][0]))
       break

引用自：https://crypto.stackexchange.com/questions/41121