格子ふるい分け

格子ふるい分けは、広い領域にわたって二変量多項式の滑らかな値を見つけるための手法です。ほとんどの場合、数体ふるいと組み合わせて使用​​されます。格子ふるい分けの元々のアイデアは、ジョン・ポラードによるものです。^[1]${\displaystyle f(a,b)}$

このアルゴリズムは、多項式の数体のイデアル構造を暗黙的に考慮します。これは、ある有理素数pを超える任意の素イデアルは と書けるという定理「^{どれが？」}を利用します。次に、通常は因数基底の限界よりわずかに大きい適切なサイズの素数qを多数選び、次のように進めます。 ${\displaystyle p\mathbb {Z} [\alpha ]+(u+v\alpha )\mathbb {Z} [\alpha ]}$

各qに対して、多項式 f(a,b) を因数分解してqより上の素イデアルを列挙する。${\displaystyle GF(q)}$

「特殊」と呼ばれるこれらの素イデアルのそれぞれに対して、によって生成される格子 L の縮小基底を構築し、ふるい領域と呼ばれる 2 次元配列を 0 に設定します。 ${\displaystyle {\mathfrak {q}}}$ ${\displaystyle \mathbf {x} ,\mathbf {y} }$${\displaystyle {\mathfrak {q}}}$

因数基底の各素イデアルに対して、 Lの部分格子の簡約基底を構築し、次のように生成する。${\displaystyle {\mathfrak {p}}}$${\displaystyle \mathbf {x} _{\mathfrak {p}},\mathbf {y} _{\mathfrak {p}}}$${\displaystyle {\mathfrak {pq}}}$

十分に大きなふるい領域内にあるサブ格子の各要素を、そのエントリに追加します。${\displaystyle \log |{\mathfrak {p}}|}$

ふるい領域内の十分に大きい値を持つすべてのエントリを読み出す

数体ふるいの適用では、2 つの多項式の両方が滑らかな値を持つ必要があります。これは、両方の多項式に対して内部ループを実行することによって処理され、特殊 q はどちらの側からでも取得できます。

最も内側のループを実装するための巧妙なアプローチは数多くあります。長方形領域内の格子の要素を効率的にリスト化すること自体が簡単な問題ではなく、また、キャッシュ構造を利用するために篩領域への更新を効率的にバッチ処理することもまた簡単な問題ではないからです。最初の問題に対する通常の解決方法は、選択されたいくつかのジェネレータによって定義された格子点の順序付けを行い、ある格子点から次の格子点へ進む決定ルールが単純になるようにすることです。2 番目の問題に対する通常の解決方法は、レベル 2 キャッシュのサイズよりも小さい配列のサブ領域に対する更新のリストのシリーズを収集することです。リストの数はおおよそ L1 キャッシュの行数なので、リストにエントリを追加すると通常はキャッシュ ヒットになり、更新のリストを 1 つずつ適用すると、各適用がレベル 2 キャッシュ ヒットになります。これを効率的に行うには、少なくとも sieve 配列のサイズに匹敵する数の更新を保存できる必要があるため、メモリ使用量がかなり多くなる場合があります。