在二次篩中，為什麼要限制因子基數？
在二次篩中，當因式分解一個數字時 $ N $ ，許多描述和大多數實現選擇作為因子基的小素數集 $ p_j $ 小於某個界限 $ B $ 僅限於具有勒讓德符號 $ \left({N\over p_j}\right)=+1 $ .
為什麼將因子基數限制為素數 $ p_j $ 這樣 $ N $ 是二次餘數模 $ p_j $ ? 我想知道，因為：
- 維基百科對二次篩的介紹性描述沒有使用這種限制，並且有效；該限制是在一個例子中介紹的，沒有任何理由（在現在的文章中）。
- 這種限制大大降低了在因子基中具有所有因子的整數的密度，可以說使其更難找到 $ x $ 這樣 $ x^2\bmod N $ 具有因子基中的所有因子（或更一般地找到 $ (x,k) $ 和 $ x^2-k\cdot N $ 光滑的）。
- 包含與限制不匹配的因子的查找可以幫助成功分解；借用數學密碼學導論第 3.6 節中的例子，試圖分解 $ N=9788111 $ （通過篩分 $ x^2\bmod N $ 為了 $ x $ 開始於 $ \lceil\sqrt N\rceil $ ，通過與 Wikipedia 中相同的算法），找到 20 個平滑值 $ x^2\bmod N $ 為了 $ x>\sqrt N $ 其中被選中（通過高斯消元法） $$ \begin{align} 3129^2\bmod N&=2\cdot5\cdot11\cdot23\ 3313^2\bmod N&=2\cdot7^2\cdot17\cdot23\cdot31\ 3449^2\bmod N&=2\cdot5\cdot7^2\cdot11\cdot17\cdot23\ 4426^2\bmod N&=2\cdot3\cdot47^2\ 4651^2\bmod N&=3\cdot23\cdot31^3 \end{align} $$ 其中最後兩個關係會因因子基的限製而被消除，因為 $ \left({N\over 3}\right)=-1 $ ; 然而，通過取這些關係的乘積，我們發現 $$ (3129\cdot3313\cdot3449\cdot4426\cdot4651)^2-(2^2\cdot3\cdot5\cdot7^2\cdot11\cdot17\cdot23^2\cdot31^2\cdot47)^2 $$ 是的倍數 $ N $ ，從中發現 $ 2741 $ , 一個重要的因素 $ N $ , 通過計算 $$ \gcd(N,3129\cdot3313\cdot3449\cdot4426\cdot4651-2^2\cdot3\cdot5\cdot7^2\cdot11\cdot17\cdot23^2\cdot31^2\cdot47) $$
注意：出於問題的目的，請忽略包括的改進 $ -1 $ 在因子庫中；或/和允許使用一個或幾個大於界限的素數 $ B $ ; 或/和（除非相關）選擇考慮因素 $ m\cdot N $ 對於一個小的乘數 $ m $ .
我相信 Carl Pomerance（二次篩算法的發明者）在以下方面給出了很好的解釋：
Pomerance，C.（2008 年）。平滑數字和二次篩。在算法數論格、數域、曲線和密碼學中（第 69-81 頁）。劍橋：劍橋大學出版社。
以下引用來自第 72 頁。
“一個號碼 $ m $ 如果它的所有素因數都很小，則它是平滑的。具體來說，我們說 $ m $ 是 $ B $ - 如果它的所有主要因素都是平滑的 $ \le B $ . 第一個觀察結果是，如果我們的序列中的一個數字不是平滑的，那麼它不太可能被用於乘積為正方形的子序列中。確實，如果數 $ m $ 能被大素數整除 $ p $ , 那麼如果 $ m $ 要在平方子序列中使用，則必須至少有一個其他項 $ m’ $ 在也可以被整除的子序列中 $ p $ . （這個其他術語 $ m’ $ 或許 $ m $ 本身，也就是說，也許 $ p^2 | m $ .)**但鑑於 $ p $ 很大，是的倍數 $ p $ 將是少之又少，並找到這個伴侶 $ m $ 不會很容易。**所以，假設我們同意選擇一些切斷 $ B $ ，並從序列中丟棄任何不是 $ B $ -光滑的。”
$$ emphasis added $$
這與@fgrieu 給出的答案一致。