使用範圍內的因子打破 RSAñ−−√ñsqrt{N}
假設 RSA 質因數 $ p $ 是范圍 $ \sqrt{N} $ , 特別是它認為 $ |p-\sqrt{N}|<\sqrt[4]{N} $
我想證明 RSA 可以及時打破 poly(log N)
給出提示： $ N = pq = (\frac{p+q}2)^2 - (\frac{p-q}2)^2 $ ， 還 $ \frac{p+q}2 \approx \sqrt{N} $
$ \textbf{This is my approach:} $
首先，我們可以計算 $ \sqrt{N} $
從 $ |p-\sqrt{N}|<\sqrt[4]{N} $ 我們知道 $ p $ 只能是 $ 2 \sqrt[4]{N} $ 不同的價值觀，即任何在 $ {\sqrt{N}- \sqrt[4]{N}, …,\sqrt{N} + \sqrt[4]{N} } $
當然 $ \sqrt{N} $ 通常不是整數，但我們可以四捨五入
所以現在我們可以測試每個元素 $ p $ 在這個集合中，如果 $ p | N $ , 在這種情況下我們可以很容易地計算出另一個因子
如果我沒記錯的話，這種減少的蠻力將花費 $ \mathcal{O} ( \sqrt{N} ) $ ，這似乎與我們想要顯示的內容不匹配，例如 $ \mathcal{O} ( \sqrt{N} ) $ $ \not= $ 聚（log N）
雖然這可能不是您正在尋找的解決方案，但Coppersmith 定理提供了一個簡單的答案。
（一般）Coppersmith 定理指出：讓 $ f(x) $ 是一元單變數次數多項式 $ d $ 係數以正整數為模 $ n $ . 可以找到所有整數 $ x $ 這樣 $ |x| \le n^{\beta^2/d} $ 和 $ \gcd(f(x), n) \ge n^{\beta} $ （或者 $ f(x) = 0 \bmod b $ , $ b $ 一個未知的除數 $ n $ 大小的 $ \ge n^{\beta} $ ) 在時間多項式中 $ \log n $ 和 $ d $ .
現在我們有 $ |p - \sqrt{n}| < n^{1/4} $ . 環境 $ f(x) = x - \lfloor \sqrt{n} \rfloor $ , 這意味著有一個 $ x_0 $ 以絕對值為界 $ n^{\left(1/2\right)^2} = n^{1/4} $ 這樣 $ \gcd(x_0 - \lfloor \sqrt{n} \rfloor, n) \ge n^{1/2} $ （也就是說，一個因數 $ n $ )，這樣一個 $ x_0 $ 可以在多項式時間內找到 $ \log n $ .