Просеивание решеток

Решетчатое просеивание - это метод нахождения гладких значений двумерного полинома в большой области. Он почти исключительно используется вместе с ситом числового поля . Первоначальная идея решетчатого сита пришла от Джона Полларда . ^[1]${\ Displaystyle f (а, Ь)}$

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

Для каждого q перечислите простые идеалы над q , факторизуя многочлен f (a, b) по${\ Displaystyle GF (q)}$

Для каждого из этих простых идеалов, которые называются «особыми » идеалами, постройте редуцированный базис решетки L, порожденной ; установить двумерный массив, называемый областью сита, равным нулю.${\ 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}} |}$

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

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

Лечение внутренней петли [ править ]

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

Ссылки [ править ]