Tamizado en celosía

El tamizado reticular es una técnica para hallar valores uniformes de un polinomio bivariado en una región grande. Se utiliza casi exclusivamente en combinación con el tamiz de cuerpos numéricos . La idea original del tamiz reticular surgió de John Pollard . ^[1]${\displaystyle f(a,b)}$

El algoritmo implica implícitamente la estructura ideal del cuerpo numérico del polinomio; aprovecha el teorema ^¿Cuál? de que cualquier ideal primo por encima de algún primo racional p puede escribirse como . Luego, se eligen muchos números primos q de un tamaño apropiado, generalmente justo por encima del límite de la base del factor , y se procede por ${\displaystyle p\mathbb {Z} [\alpha ]+(u+v\alpha )\mathbb {Z} [\alpha ]}$

Para cada q , enumera los ideales primos por encima de q factorizando el polinomio f(a,b) sobre${\displaystyle GF(q)}$

Para cada uno de estos ideales primos, que se denominan "especiales ", construya una base reducida para la red L generada por ; establezca una matriz bidimensional llamada región de tamiz en cero. ${\displaystyle {\mathfrak {q}}}$ ${\displaystyle \mathbf {x},\mathbf {y}}$${\displaystyle {\mathfrak {q}}}$

Para cada ideal primo en la base factorial, construya una base reducida para la subred de L generada por${\displaystyle {\mathfrak {p}}}$${\displaystyle \mathbf {x} _{\mathfrak {p}},\mathbf {y} _{\mathfrak {p}}}$${\displaystyle {\mathfrak {pq}}}$

Para cada elemento de esa subred que se encuentre dentro de una región de tamiz suficientemente grande, agregue a esa entrada.${\displaystyle \log |{\mathfrak {p}}|}$

Leer todas las entradas en la región del tamiz con un valor suficientemente grande

Para la aplicación del tamiz de campos numéricos, es necesario que ambos polinomios tengan valores suaves; esto se maneja ejecutando el bucle interno sobre ambos polinomios, mientras que la q especial se puede tomar desde cualquier lado.

Hay una serie de enfoques inteligentes para implementar el bucle más interno, ya que enumerar los elementos de una red dentro de una región rectangular de manera eficiente es en sí mismo un problema no trivial, y agrupar de manera eficiente las actualizaciones de una región de tamiz para aprovechar las estructuras de caché es otro problema no trivial. La solución normal para la primera es tener un orden de los puntos de la red definidos por un par de generadores elegidos de modo que la regla de decisión que lo lleva de un punto de la red al siguiente sea sencilla; la solución normal para la segunda es recopilar una serie de listas de actualizaciones de subregiones de la matriz más pequeñas que el tamaño de la caché de nivel 2, con el número de listas siendo aproximadamente el número de líneas en la caché L1 de modo que agregar una entrada a una lista sea generalmente un acierto de caché, y luego aplicar las listas de actualizaciones una a la vez, donde cada aplicación será un acierto de caché de nivel 2. Para que esto sea eficiente, debe poder almacenar una cantidad de actualizaciones al menos comparable al tamaño de la matriz de tamiz, por lo que esto puede ser bastante derrochador en el uso de memoria.