二次篩：用素數篩分
我試圖理解二次篩算法。
目前我被困在篩分部分。
假設要分解的數字是 9788111。我決定尋找 50 個平滑因子。我的初始因子基數 (FB) = $ p_i $ = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47}.
我瀏覽了 FB 中的每個數字及其權力。
對於 FB 中的每個數字，我首先檢查是否 N 是二次殘差 mod 數字（即 Is N 是 QR $ \pmod {p_i} $ . 如果是，那麼我找到了根源。
對於 2，檢查 N 是否為 QR 很簡單 $ \pmod 2 $ . 您也可以將其擴展為 2 的冪。對於其他素數，您可以使用 Euler’s Criteria for Quadratic Residues 來檢查 N 是否為 QR $ \pmod {p_i} $ . 如果它是 QR，那麼您可以使用 Tonelli-Shanks 找到根，然後用該素數進行篩分。
我要什麼主力？對於當量 $ 5^2 $ ，我如何檢查是否 $ t^2 \equiv N \pmod {5^2} $ 有解決辦法嗎？在我嘗試查找根之前是否有任何測試或規則可以檢查？
對於小的素數，如 $ 5^2 $ ，如果 N 是 QR，可以手動查找檢查 $ \pmod {{p_i}^n} $ ，但你如何為更大的主要權力做到這一點？
回想一下（基本）二次篩需要找到一些 $ x $ 和 $ x^2-N $ 光滑的。為此，它添加了（縮放的，近似的）對數 $ p_i $ 對小除數 $ {p_i}^m $ 的 $ x^2-N $ 在索引中 $ x>0 $ 的一個數組。這個比較快，因為只有兩個 $ {p_i}^m $ 數組中的條目需要為每個 $ {p_i}^m $ .
為主要權力做什麼（即， $ {p_i}^m $ 為了 $ m>1 $ )?
懶惰和次優的選擇是在篩分階段忽略它們，通過較低的平滑門檻值和/或基礎中的更多素數來補償。
更好的選擇是解決 $ x^2\equiv N\pmod{{p_i}^m} $ , 然後篩選 $ {p_i}^m $ 正如我們所做的那樣 $ p_i $ . 對於奇數素數 $ p_i $ ，我們已經解決了 $ x\equiv N\pmod{p_i} $ ，說它有（兩個）解決方案 $ x_j\in[0,p_i) $ . （二）解決方案 $ x^2\equiv N\pmod{{p_i}^m} $ 在 $ [0,{p_i}^m) $ 是 $$ {x_j}^{({p_i}^{m-1})}\cdot N^{({p_i}^m - 2{p_i}^{m-1} + 1)/2}\bmod {p_i}^m $$