Tamiz de Atkin - algoritmo para enumerar los puntos de la red.

Question

Recientemente, he estado trabajando para implementar el Sieve de Atkin con un rendimiento significativamente mejor que la versión encontrado en Wikipedia .

De la lectura del documento original ( http://www.ams.org/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf ), parece que el autor adopta un enfoque diferente al de Wikipedia: mientras que el código de Wikipedia intenta encontrar soluciones a cada forma cuadrática probando todos los valores posibles de x e y, el autor, en cambio, (véase la página 1026, Algoritmo 4.1-4.3 en el documento enlazado anteriormente) hace lo siguiente:

Si tratamos de cribar los primos a partir de los números del rango [L, L+B) (es decir, la progresión aritmética de los números B a partir de L), considera el anillo descrito por cada forma cuadrática (toma $4x^2 + y^2$ por ejemplo):

$60L \le 4x^2 + y^2 < 60L + 60B$

A continuación, proporciona un algoritmo que debería enumerar todas las triplas (x, y, k) para las que: $4x^2 + y^2 = 60k + \delta$

Mi pregunta se refiere a este algoritmo. Aunque el documento lo trata como tal, no es obvio para mí por qué tenemos la restricción (x mod 15, y mod 30), o cómo se eligen f y g - dice en la descripción del algoritmo:

Dados enteros positivos $\delta < 60$ , $f \le 15$ y $g \le 30$ tal que $\delta \equiv 4f^2 + g^2$ (mod 60), ...

¿Significa esto que podemos elegir simplemente un par concreto (f, g) para el que se cumpla la congruencia, o si existe más de un par hay que enumerar sobre todos los pares para generar todas las triplas (x, y, k)?

Answer 1

Para el algoritmo 4.1 $f,g,\delta$ son dadas, consideradas preestablecidas. Entonces, para el $f,g$ itera sobre todos los $x\equiv f \pmod{15}$ y $y\equiv g \pmod{30}$ que tengan el tamaño adecuado para el $[60L,60(L+B)]$ límites. Para cada uno de estos $(x,y)$ $$ 4x^2+y^2 = 4(15u+f)^2+(30v+g)^2 \equiv 4f^2+g^2 \equiv \delta \pmod{60} $$

Este algoritmo se utiliza para ejecutar el paso 2 del Algoritmo 3.1 y deberá realizarse una vez para cada $(f,g)$ que satisfagan $4f^2+g^2 \equiv \delta \pmod{60}$ para el $\delta$ . Para cada elección de $\delta\in \{1,13,17,29,37,41,49,53\}$ hay 16 posibilidades para $(f,g)$ que dan soluciones, por ejemplo, para $\delta=1$ tenemos que considerar $(f,g) \in \{(2,15),(3, 5),(3, 25),\ldots,(15, 29)\}$ .

Por tanto, a efectos del Algoritmo 4.1 $(f,g)$ se considera fija, pero a efectos de la criba, en el paso 2 del Algoritmo 3.1 donde se pregunta "Para cada $(x,y,k)$ " es necesario iterar sobre todos los pares adecuados para encontrarlos todos.