篩選序列X2-nX2−nx^2-n辨識 b 平滑數
我目前正在對二次篩進行程式，並且有幾本文學書籍/論文，並將舉一個例子
$$ 1 $$對於我的問題： $$ 1 $$ J. Hoffstein、J. Pipher 和 H. Silverman的數學密碼學導論。 $$ 2 $$ R. Crandall 和 C. Pomerance 的質數。 $$ 3 $$ C. Pomerance的平滑數字和二次篩。 對數字進行因式分解 $ n $ 使用二次篩，我們正在尋找數字的乘積 $ x^2-n $ 給出一個完美的正方形。號碼 $ x^2-n $ 必須是 B 平滑的。我們也只看雅可比符號所在的素數 $ (\frac{n}{p}) = 1 $ , 所以我們可以解方程 $ a^2 \equiv n\ \textrm{mod}\ p $ 對於每個 $ p $ 和 $ 2 \leq p \leq B $ . 如果 $ p = 2 $ 只有一種解決方案，對於 $ p \gt 2 $ 要麼沒有解決方案，要麼有兩個解決方案。但在我們的例子中總是有 2 個解決方案，因為 $ n $ 是我們素數的二次餘數。
我現在將談到我的問題開始的地方。在
$$ 1 $$和$$ 3 $$是解釋在我們的序列中辨識 B 平滑數的篩步 $ x^2 - n $ . 我們正在尋找數字 $ x $ 在哪裡 $ p\ |\ (x^2- n) $ . 的價值觀 $ x $ 可以“很容易”找到 $ a^2 \equiv n\ \textrm{mod}\ p $ 即數字 $ x $ 是一致的 $ a_1 \textrm{ mod } p $ 或者 $ a_2 \textrm{ mod } p $ ( $ a_1, a_2 $ 是的根 $ a^2 $ ).
所以，我們從序列中的第一個數字開始 $ x^2-n $ 在哪裡 $ x \equiv a_1 \textrm{ mod } p $ 然後每個 $ p $ -th 條目可被除以 $ p $ . 我們從某個起點重新開始 $ x^2 -n $ 並尋找一個數字 $ x $ 為此 $ x \equiv a_2 \textrm{ mod } p $ 抓住。
現在我已經嘗試通過書中的一些範例來實現這一點，但它會停止獲取正確的條目 $ x $ :
在
$$ 1 $$是數字的例子 $ N = 9788111 $ . 此外，前 20 個 50 平滑的數字與因式分解一起列出 $ x^2 - n $ . 首先 $ x $ 是 $ x = \Big\lceil\sqrt{N}\Big\rceil = 3129 $ .
現在開始：
$ 3129^2 \equiv 2530 \textrm{ mod } 9788111 $
$ 3130^2 \equiv 8789 \textrm{ mod } 9788111 $
$ 3131^2 \equiv 15050 \textrm{ mod } 9788111 $
…
$ 4394^2 \equiv 9519125 \textrm{ mod } 9788111 $
直到這個數字一切正常。我的程序給出了正確的分解。如果我們用質數測試它 $ p = 7 $ 和根 $ a_1 = 2 $ 和 $ a_2 = 5 $ , 我們看到 $ 3131 \equiv 2 \textrm{ mod } 7 $ . 所以，我們可以劃分 $ 15050 $ 和 $ 7 $ .
但是列表中的下一個數字 50-smooth 不包含該過程：
$ 4425^2 \equiv 4403 \textrm{ mod } 9788111 $ 和 $ 4403 = 7 * 17 * 37 $
我們看到，那 $ 4403 $ 可以被 $ 7 $ . 這意味著 $ 4425 $ 必須一致 $ 2 \textrm{ mod } 7 $ 或者 $ 5 \textrm{ mod } 7 $ . **但事實並非如此。**這意味著，在某些時候我不能隻數數 $ x $ 和 $ p $ 得到序列中下一個可被整除的數 $ p $ . 我認為這是因為 $ x^2 - n $ 大於 $ n $ 自我在某些特定的 $ x $ 喜歡 $ 4425 $ :
$ 4425^2 - n = 19580625 - 9788111 = 9792514 > 9788111 $
所以，我的問題是在某些情況下是什麼原因 $ x $ 它不再起作用了？我該怎麼做才能重新開始計數過程 $ x $ 和 $ p $ 辨識有效的分割點 $ p $ .
語句*“分解一個數 $ n $ 使用二次篩，我們正在尋找數字的乘積 $ x^2−n $ 給出一個完美的正方形”* 是不正確的，這只是一個可能的更一般定義的一個子集：尋找數字的乘積 $ x^2-k\cdot n $ 給出一個完美的平方（通過將數字限制為適當平滑，對它們進行因式分解，並使用某種等價的高斯消元法來形成乘積，以使每個素數在其因式分解中的多重性都是偶數）。介紹 $ k $ 允許更多的搜尋自由（但在實踐中很少使用）。
參考中使用的QS的定義
$$ 1 $$與Wikipedia中的相同。它正在尋找形式的平滑 $ x^2\bmod n $ . 這屬於我給出的 QS 的更一般定義，因為 $ x^2\bmod n $ 是 $ x^2-k\cdot n $ 和 $ k=\Big\lfloor{x^2\over n}\Big\rfloor $ . 題中遇到的問題是使用的篩分算法發現 $ x $ 這樣 $ x^2-n $ 光滑；但當 $ x $ 超過 $ \sqrt{2n} $ , 篩分算法不再是篩分 $ x^2\bmod n $ .
解決此問題的選項
- 只篩 $ x^2-n $ ，包括超過 $ n $ ; 並使用 $ x^2-n $ 而不是 $ x^2\bmod n $ 其他地方。問題是，合適的密度 $ x $ 減少為 $ x $ 成長。此外，這不是大型的選擇 $ n $ , 因為即使是一小部分 $ (\sqrt2-1)\sqrt n $ 值太長了。
- 只篩 $ x^2-n $ ，但使用更大的因子基數。這會增加要找到的關係數量，但會更多地增加保留的平滑數量，以便更快地達到所需的關係數量。
- 篩 $ x^2-k\cdot n $ 對於幾個值 $ k $ . 例如：直到有足夠的平滑收集，並且對於 $ k $ 從 $ 1 $ 前進，過篩 $ x^2-k\cdot n $ 對於平滑，變化 $ x $ 從 $ \Big\lceil\sqrt{k\cdot n}\Big\rceil $ 至 $ \Big\lfloor\sqrt{k\cdot n+m}\Big\rfloor $ 對於一些界限 $ m $ . 匹配參考$$ 1 $$當界 $ m $ 被設定為 $ n $ . 這可以被視為一個過於幼稚的多重多項式二次篩。
- 篩選形式的整數 $ (a\cdot x+b)^2-n $ ， 和 $ (a,b) $ 選擇得當，尤其是這樣 $ (a\cdot x+b)^2-n $ 可以被 $ a $ （允許 $ a $ 作為一個因子，如果它不屬於因子基）。這就是實際使用的多重多項式二次篩的變體所做的。多個多項式允許保留在被篩分的未分解部分很小的區域中，因此找到平滑的速率不會變得非常小。與之前的解決方案相比，一個優點是用於篩選的因子基對於所有使用的多項式都是相同的，請參閱這個問題。
還有其他幾個獨立的 QS 優化；包含：
- 允許篩選的內容為陰性，並包括 $ p_0=-1 $ 在因子庫中。
- 實際因素 $ m\cdot N $ 對於一些小 $ m $ 選擇優化因子基礎的產量。