Number-Theory
是否有一種分解 N 的算法，它和這個一樣簡單，但速度更快？
我找到了一個簡單的半素數分解算法，您可以在分解半素數和 RSA 的可能影響（免付費牆）中了解它。
它基本上是這樣工作的：
- 你顛倒數字 $ N $ , 我們稱這個值 $ Ň $
- 你選擇一個整數， $ k $ （通常為 1，但也可以是其他值）
- 一個變數， $ Δ $ , 可以是平方根之間的任何整數值 $ N $ 和平方根 $ Ň $
然後，您計算四個值，如果有任何返回 1 以外的值，那麼您有一個主要因素：
- $ \gcd[N, (k × Ň) + Δ] $
- $ \gcd[N, (k × Ň) - Δ] $
- $ \gcd[N, (Δ × Ň) + k] $
- $ \gcd[N, (Δ × Ň) - k] $
使用此算法和 GMP 庫，它將在 3 秒內分解 18014417929109603。
我想知道是否有任何其他算法比這更快，但同樣容易實現？我知道 GNFS 是最快的，但實現起來也非常困難。
純屬胡說八道。用於選擇隨機 $ \Delta $ 之間 $ \sqrt{\min(N, Ň)} $ 和 $ \sqrt{\max(N, Ň)} $ 有太多的可能性讓它發揮作用。例如，每當第一個和最後一個數字 $ N $ 不同，你會得到類似的東西 $ \frac{1}{10} \cdot \sqrt N $ 可能性（確切的公式無關緊要）。
所以你可以替換第一個公式 $ \gcd[N, (k × Ň) + Δ] $ 和 $ k=1 $ 通過這個： $ \gcd[N, \Delta] $ . 全部嘗試 $ \Delta $ 之間 $ 1 $ 和 $ \sqrt N $ ，可能性的數量在某個小因素之內。
與除法相比，計算 $ \gcd(N, x) $ 優點是每次嘗試你都會嘗試所有的因素 $ x $ . 這很好，以防萬一 $ N $ 有一些小因素，在 RSA 的情況下肯定不是真的。
我認為連結算法對試用除法沒有優勢。嘗試所有素數 $ \sqrt N $ 可能更快，也會終止 $ N $ 是素數，並且有一個有限的時間。
總結：純屬胡說八道。