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

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

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

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

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

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

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

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

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

Процедуры внутренней петли

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

использованная литература