User: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:使用创建条目精灵建立的页面