Решетчатое просеивание

Решетчатое просеивание - это метод поиска гладких значений двумерного полинома. $f(a,b)$ над большим регионом. Он почти исключительно используется в сочетании с ситом числового поля . Первоначальная идея решетчатого сита принадлежит Джону Полларду .

Алгоритм неявно предполагает идеальную структуру числового поля многочлена; он использует теорему ^{Который из?} что любой простой идеал выше некоторого рационального простого числа p можно записать как $p\mathbb {Z} [\alpha ]+(u+v\alpha )\mathbb {Z} [\alpha ]$. Затем выбирают множество простых чисел q подходящего размера, обычно чуть выше предела факторной базы , и продолжают:

Для каждого q перечислите простые идеалы выше q, разложив многочлен f(a,b) по $GF(q)$

Для каждого из этих простых идеалов, называемых «особыми», ${\mathfrak {q}}$s, построить сокращенный базис $\mathbf {x} ,\mathbf {y}$ для решетки L, порожденной ${\mathfrak {q}}$; установить двумерный массив, называемый областью сита, равным нулю.

Для каждого простого идеала ${\mathfrak {p}}$ в факторной базе построить приведенный базис $\mathbf {x} _{\mathfrak {p}},\mathbf {y} _{\mathfrak {p}}$ для подрешетки L, порожденной ${\mathfrak {pq}}$

Для каждого элемента этой подрешетки, лежащего внутри достаточно большой ситовой области, сложим $\log |{\mathfrak {p}}|$ к этой записи.

Считайте все записи в области сита с достаточно большим значением.

Для применения сита числового поля необходимо, чтобы два полинома имели гладкие значения; это решается путем выполнения внутреннего цикла над обоими полиномами, в то время как специальный q может быть взят с любой стороны.

Лечение внутренней петли

Существует ряд умных подходов к реализации внутреннего цикла, поскольку эффективное перечисление элементов решетки в прямоугольной области само по себе является нетривиальной проблемой, а также эффективное группирование обновлений в решетчатой ​​области, чтобы воспользоваться преимуществами структур кэша. это еще одна нетривиальная проблема. Обычное решение первого состоит в том, чтобы порядок точек решетки определялся парой генераторов, выбранных так, чтобы правило принятия решения, которое переводило вас от одной точки решетки к другой, было простым; нормальное решение второго варианта — собрать серию списков обновлений в подобластях массива, размер которых меньше размера кэша уровня 2, при этом количество списков примерно равно количеству строк в кэше L1, так что добавление записи в список обычно является попаданием в кэш, а затем применение списков обновлений по одному, где каждое приложение будет попаданием в кэш второго уровня. Чтобы это было эффективно, вам необходимо иметь возможность хранить количество обновлений, по крайней мере, сопоставимое с размером ситового массива, поэтому это может быть довольно расточительным в использовании памяти.