二次篩選：是否有決定要篩選多少個數字的經驗法則？
在二次篩選算法中，我們首先確定一個 B，然後通過使用二次多項式進行篩選來尋找 B 平滑素因子。
我可以找到一些有助於弄清楚如何決定 B 的公式。
要將數字 N 分解，我們可以使用以下方法：
$ L = e^{\sqrt {\ln(N)ln(ln(N))}} $
$ B = L^{\frac {1}{\sqrt 2}} $
這可以粗略估計我們應該尋找哪些平滑數字。
但是，我無法找到任何公式或經驗法則來計算使用二次多項式篩選多少個數字。
如果不清楚我在說什麼，讓我使用QS 上的 Wikipedia 文章進行解釋。
在“基本篩的例子”的數據收集部分，它說如下：
開始篩選基礎中的每個素數，選擇篩選 Y(X) 的第一個 0 ≤ X < 100。
所以在這裡他們選擇生成一個包含 100 個 Y(X) 的列表進行篩選。是否有任何經驗法則或公式可以得出這個數字（在這種情況下為 100）？
在純二次篩中，我們需要找到比因子基中的素數更多的關係（等效地，平滑）。在此，我們計算小素數 $ p_i $ 使 $ N $ 二次餘數模 $ p_i $ ，而不是他們的權力。該計數也是（稀疏）關係矩陣中的列數，其中關係是線，用作線性代數階段的輸入。通常，比列多 5 行就足夠了。每個進一步的額外關係都會將失敗的機率降低兩倍。
這給出了停止篩分並開始線性代數的工作標準，但並沒有直接說明我們需要篩分多少整數。經驗法則和其他參數取決於許多事情，包括
至關重要的是，如果我們篩選一個 (QS) 或多個多項式 (MPQS/SIQS)。使用 QS，多項式經常會增長到過高的值，因此平滑變得稀有；然後，擴大篩子或重新使用它以在同一多項式上進一步篩分不會有太大幫助。
通過將通過篩選發現的因子的對數求和，我們不確定（或高度自信）的多項式策略值是否足夠平滑以滿足我們的目的。我們可以
- 忽略他們，甚至認為他們仍然可以 $ B $ -光滑的。
- 嘗試篩選出最高質數的小質數 $ B $ ，以及他們的權力，即使他們超過 $ B $ （換句話說，我們限制為 $ B $ -通過篩分步驟的多項式的平滑值）；這很簡單，並且是基本 (MP/SI)QS 的典型特徵。
- 嘗試小因素直到更高的限制 $ B’ $ （換句話說，我們篩選素數和素數冪 $ B<B’ $ , 並限制為 $ B’ $ -通過篩分步驟的平滑劑）。
- 此外，允許一個大素數因子 (PMPQS) 達到某個更高的限制，希望這些大素數的碰撞將使兩個原本不可用的關係產生一個新的可用關係（即沒有大素數，以便它適合有限數量的列矩陣）
- 另外允許兩個大素因數 (PPMPQS)。
篩選門檻值（用於篩選條目中累積的素數對數之和），這是拒絕之間的折衷 $ B $ -smooths，並且花費太多時間來嘗試考慮不會產生可用關係的候選人。
讓 QS 工作的建議：
首先做一些處理謙虛的事情 $ N $ 沒有篩陣！
- 使用因子基數 $ p_i $ 製造 $ N $ 二次餘數，達到某個極限 $ B $ . 首先在最優值的大邊犯錯更安全 $ B $ .
- 尋找 $ B $ -多項式值之間的平滑 $ t^2-N $ 和 $ t\gtrsim\left\lceil\sqrt N,\right\rceil $ 通過最基本的方式（例如審判部門）。找到比素數更多的平滑。
- 讓線性代數分解 $ N $ .
優化大多數（或所有）試驗部門 $ t^2-N $ 通過一個測試 $ t\bmod(p_i^k) $ 屬於兩個預先計算的值的集合。
在那個階段，瓶頸應該是通過嘗試完全分解許多 $ t^2-N $ 使用（優化的）試驗部門，大多數最終都不是 $ B $ -光滑的。引入篩陣列，其目的是（顯著地）減少平滑候選的數量，代價是錯誤地拒絕少數幾個（篩選主要冪有助於減少錯誤拒絕）。這允許增加 $ N $ （從而提高最優 $ B $ ).
一一介紹進一步的優化：
- 有 $ -1 $ 在因子庫中，這也是篩選 $ N-t^2 $ 為了 $ t\lesssim\left\lfloor\sqrt N,\right\rfloor $
- 簡單的“乘數”改進，其中因素 $ m,N $ 對於一些選定的小整數 $ m $ ，使得因子基數得到改善（具有相對較多的小素數）
- 使用多個多項式，這允許篩选和分解更小的候選者，因此更有可能 $ B $ - 平滑
- 瓶頸可能仍然是通過篩分測試的平滑因子的嘗試分解（取決於篩分門檻值和因子基的大小）；通過僅使用小素數的（優化的）試驗除法可以節省一些費用，然後是更好的方法，也許是 Pollard 的 rho 和素數測試，但它不會很快產生；這樣的測試對於大的素數改進是必要的。
- 一個然後是兩個大的主要改進（PMPQS 和 PPMPQS）。
優化瓶頸是什麼，並調整許多參數。最終，瓶頸應該是篩分。優化的實現在那裡付出了很多努力，技術和程式碼根據篩選的素數大小以及與 CPU 記憶體的互動而專門化。