使用者:Realpaimon/晶格篩法

晶格篩法是一種在廣泛區域內尋找二元多項式$f(a,b)$的光滑數(smooth)的技術。它幾乎只與數域篩法一起使用。晶格篩法的最初想法來自約翰·波拉德。

該算法隱含地涉及多項式的數域理想結構；它利用了這個定理：任何位於某個有理素數$p$上面的素理想可以寫成$p\mathbb {Z} [\alpha ]+(u+v\alpha )\mathbb {Z} [\alpha ]$。然後，選擇適當大小的許多素數 q，通常略高於因子基限制，並按以下步驟進行：

對於每個$q$，通過對多項式$f(a,b)$ 在$GF(q)$上進行因式分解，列出位於$q$上方的素理想，這些被稱為「特殊$q$理想」 。

對於這些素理想，構造由${\mathfrak {q}}$生成的晶格$L$ 的約化基Lattice reduction${\textbf {x}},{\textbf {y}}$；將名為篩選區域的二維數組設置為零。

對於因子基中的每個素理想${\mathfrak {q}}$，構造由${\mathfrak {pq}}$生成的子晶格 L 的簡化基$\mathbf {x} _{\mathfrak {p}},\mathbf {y} _{\mathfrak {p}}$

對於位於足夠大的篩選區域內的該子晶格的每個元素，將$\log |{\mathfrak {p}}|$添加到該條目。

讀取所有篩選區域中值足夠大的條目。

對於數域篩法應用，兩個多項式都需要具有平滑的值；這通過同時運行內部循環來處理兩個多項式，而特殊$q$理想可以來自任一方。

最內部循環的處理方法

內部循環的處理方式有很多巧妙的方法，因為有效地列出矩形區域內格子元素本身就是一個不平凡的問題，而有效地批處理篩選區域的更新以利用緩存結構則是另一個不平凡的問題。解決第一個問題的常規方法是按照選定的兩個生成元定義晶格點的排序，使得從一個晶格點到下一個晶格點的決策規則變得直觀；解決第二個問題的常規方法是收集一系列更新列表，這些列表是小於二級緩存大小的數組子區域，列表數量大致等於 L1 緩存中的行數，因此向列表添加條目通常是緩存命中，然後逐個應用更新列表，每個應用都是二級緩存命中。為了使這些操作高效，您需要能夠存儲的更新數量至少與篩選數組的大小相當，因此這可能會消耗大量內存。

參考資料

Category:使用創建條目精靈建立的頁面