Algoritmo de tamizado cuadrático

Question

Estoy atascado con la etapa de cribado del algoritmo Quadratic Sieve. He leído un montón de artículos hasta este punto, pero no puedo encontrar ninguna guía de cómo elegir el intervalo de tamizado o cómo se hace el tamizado en realidad, porque lo que he visto hasta ahora es "elegimos un intervalo de tamizado" o "luego tamizamos alrededor de esto".
Esto es lo que he entendido y he hecho (siguiendo el documento de Contini):

1. Digamos que, para N = 90283, calculo el límite $B = e^{(\frac{1}{2} + o(1))(\sqrt{\ln n \ln \ln n})} = 44$ donde tomo $o(1) = 0.22$ (sólo una suposición al azar, supongo). ¿Cuál es la mejor manera de elegir un buen $o(1)$ ?

2. Entonces tomo $C = \lceil \sqrt{N}\rceil = 301$

3. Entonces, usando el Atkin Sieve obtengo una lista de primos $<B$ :

   $\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43\}$

4. Luego, calculando el símbolo de Jabobi (Legendre) para cada valor de la lista de primos, elijo los primeros no-residuos cuadráticos para obtener la base del factor:

   $\{2, 3, 7, 17, 23, 29, 37, 41\}$

5. Luego, utilizando el algoritmo Tonelli-Shanks, calculo las raíces modulares $\pm t$ , donde $t$ es una solución a $t^2 \equiv N \mod{p}$ con $p$ un primo de la base del factor.

6. Entonces obtengo dos matrices de soluciones $sol1 = t - C \mod p$ y $sol2 = - t - C \mod p$ con p's de la base del factor. y también obtener una matriz de logaritmos para p's $l_p = \ln p$ redondeado con cierta precisión, digamos dos dígitos decimales. ¿Cuál es una buena precisión?

   sol1 $= \{0, 0, 2, 13, 11, 26, 10, 28\} $

   sol2 $= \{0, 1, 5, 14, 8, 10, 17, 26\} $

   $l_p$ $= \{0.69, 1.1, 1.95, 2.83, 3.14, 3.37, 3.61, 3.71\}$

Ahora por lo que entiendo tengo que inicializar 'sieving_array' inicializado a 0's, digamos, al tamaño $ = 60$ elementos. Además, ¿cómo debo elegir el tamaño del intervalo de cribado? ¿Existe alguna fórmula similar al límite?

Entonces tengo que añadir los valores de $l_p$ a la matriz de cribado a las posiciones $sol1[j] + i * $ factor_base[j] y $sol1[j] + i *$ factor_base[j], donde $ 0 \le i \le $ tamaño y $ 0 \le j \le |$ factor_base $|$ . Y para la primera $p=2$ añadir $l_p$ sólo a las posiciones con sol1. Así obtengo esta lista (redondeada a dos dígitos decimales):

$\{1.79, 1.1, 2.64, 1.1, 1.79, 1.95, 1.79, 1.1, 3.83, 3.05, 8.77, 3.14, 3.74, 3.93, 3.52, 1.1, 3.74, 3.61, 1.79, 3.05, 0.69, 1.1, 1.79, 1.95, 1.79, 1.1, 9.72, 1.1, 5.5, 0.0, 6.57, 7.07, 0.69, 3.05, 4.93, 0.0, 1.79, 3.05, 0.69, 4.47, 3.74, 0.0, 1.79, 1.1, 2.64, 1.1, 1.79, 8.39, 4.62, 1.1, 0.69, 3.05, 1.79, 0.0, 10.49, 4.47, 0.69, 4.24, 3.74, 0.0\}$

Ahora, tengo que buscar entre los valores de la lista, y si algunos de ellos son al menos $\log(2x \sqrt N)$ esto significa polinomio $g(x)$ puede ser factorizado sobre la base de factores.

Mi pregunta principal es: ¿dónde está este $x$ ¿de dónde viene? Tengo esta lista de valores, pero ¿qué hago con ella? Si tengo un elemento en esta lista, por ejemplo $1.79$ - con lo que $x$ ¿tengo que compararlo? ¿Cómo puedo elegir un buen término de error? ¿Es $x$ posición de $1.79$ ? Si es así, ¿qué valor indica este $1.79$ es factorizable sobre la base de factores?

Answer 1

Su pregunta abarca mucho material, pero me centraré en su principal punto de fricción: la determinación de un punto de corte para su uso después del tamizado. Hay dos cuestiones que hacen que la elección del punto de corte sea problemática:

• Cada uno de los números del intervalo de la criba es, en realidad, un valor diferente, por lo que ningún punto de corte es ideal para todo el intervalo.
• En la práctica, nadie criba las potencias primarias, por lo que probablemente haya muchos números que puedan ser factorizados sobre la base de los factores sin llegar a la raíz cuadrada del número.

Si elige un límite mayor que la raíz cuadrada del número mayor, ninguno de los candidatos pasará la prueba y el cribado no tendrá sentido. Además, dado que se está añadiendo una estimación aproximada del logaritmo del factor, también se necesita cierta holgura para tener en cuenta, por ejemplo, un número compuesto por factores que se redondean hacia abajo. Por último, si el primo $p$ está en tu base de factores y no tamizas las potencias primarias $p^a$ se necesita aún más latitud para atrapar los números que no son libres de cuadrados.

Desde un punto de vista teórico, el cribado no es más que una optimización para evitar la división de prueba de todos los números del intervalo. Así que la elección del corte es en gran medida una decisión de implementación:

• Si eliges el punto de corte demasiado alto, perderás algunos números que pueden ser factorizados sobre la base del factor.
• Si eliges el punto de corte demasiado bajo, perderás mucho tiempo probando a dividir números que no pueden ser factorizados sobre la base del factor.

El valor ideal del corte depende, por tanto, de la rapidez del cribado y de la rapidez de la división del ensayo. La solución es probar una variedad de valores y ver lo que funciona mejor en su aplicación particular.